Shifting Stacks （递增思想特例化）

time limit per test1 second

memory limit per test256 megabytes

You have n stacks of blocks. The i-th stack contains hi blocks and it’s height is the number of blocks in it. In one move you can take a block from the i-th stack (if there is at least one block) and put it to the i+1-th stack. Can you make the sequence of heights strictly increasing?

Note that the number of stacks always remains n: stacks don’t disappear when they have 0 blocks.

Input

First line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n (1≤n≤100). The second line of each test case contains n integers hi (0≤hi≤109) — starting heights of the stacks.

It’s guaranteed that the sum of all n does not exceed 104.

Output

For each test case output YES if you can make the sequence of heights strictly increasing and NO otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Example

input

6

2

1 2

2

1 0

3

4 4 4

2

0 0

3

0 1 0

4

1000000000 1000000000 1000000000 1000000000

output

YES

YES

YES

NO

NO

YES

题目分析我们可以知道0，1，2.……n是最小的递增整数，所以我们可以判断用数列的和比较。

具体操作看代码。

听懂了记得给个赞鼓励一下，码字不易，用爱发电。

上ac代码。

有事你就q我；QQ2917366383

学习算法

  #include<iostream>
  using namespace std;
  int n,b;
  int main()
  {
    int a[150000];
    int t;
    cin>>t;
    while(t--)
    {
        long long sum1,sum2;
      b=sum1=sum2=0;
      cin>>n;
      for(int i=1;i<=n;i++) 
      cin>>a[i];
      for(int i=1;i<=n;i++)
      {
        sum1+=a[i];
        sum2+=(i-1);//0,到i-1的和 
        if(sum1<sum2)
        {
        cout<<"NO"<<endl;
          b=1;
          break;
        }
      }
      if(!b)
      cout<<"YES"<<endl;
    }
  }