You have n stacks of blocks. The i-th stack contains hi blocks and it's height is the…
- User
You have n stacks of blocks. The i-th stack contains h_i 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 ≤ 10^4) — 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 h_i (0 ≤ h_i ≤ 10^9) — starting heights of the stacks.
It's guaranteed that the sum of all n does not exceed 10^4.
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
Note
In the first test case there is no need to make any moves, the sequence of heights is already increasing.
In the second test case we need to move one block from the first stack to the second. Then the heights become 0 1.
In the third test case we could move one block from the first stack to the second and then from the second to the third, which would make the heights 3 4 5.
In the fourth test case we can't make a move, but the sequence is not increasing, so the answer is NO.
In the fifth test case we can only make one move (from the second to the third stack), which would make the heights 0 0 1. Both 0 1 0 and 0 0 1 are not increasing sequences, so the answer is NO.
Assistant
We need to determine if we can make heights strictly increasing (h1 < h2 < ... < hn) by repeatedly moving a block from stack i to stack i+1 (i from 1 to n-1) any number of times. We can move only from i to i+1, not in reverse. We can make as many moves as we want, as long as each move reduces the count of source stack by 1 and increases the destination by 1. Stacks can become zero. We cannot move from stack i if it has zero blocks.
We need to see if there exists a sequence of moves (which is essentially redistributing blocks forward) that results in a strictly increasing sequence. This is a known Codeforces problem "Strange Blocks" or similar? Actually there is problem "Increasing by Modulo"? No. This is "Make it Increasing" maybe? But we have only forward moves.
Observations: Since we can only move blocks to the right, the total number of blocks remains constant. The final heights must sum to the same total as initial sum. Also they must be strictly increasing positive? Actually heights can be zero? The final sequence must be strictly increasing, so h1 < h2 < ... < hn. They are heights (non-negative integers). So it's possible that h1 = 0, h2 = 1, etc. But they must be strictly increasing, so if n>1, we can have zero and then positive? Yes, 0 < 1 is allowed. However, we need to ensure we can achieve such a sequence by moving blocks right.
Essentially, we need to assign final heights a_i such that a_1 < a_2 < ... < a_n, all are non-negative integers, and sum a_i = total = S. Also, we need to be able to achieve these final heights via moves only to the right. When moving only to right, the condition to achieve a configuration from initial is that for each prefix i, the total blocks in the first i stacks cannot increase beyond what we have initially? Actually moving blocks to the right reduces earlier stacks and adds to later stacks. So for each prefix, the total number of blocks in the first i stacks can only decrease or stay same? Let's think: When we move a block from stack j to stack j+1, if j <= i, then moving from j to j+1 where j+1 may be > i or <= i. Cases:
- If we move a block from stack j where j <= i, and the destination j+1 <= i, then the total in prefix i remains unchanged (since we moved within the prefix).
- If we move from stack j <= i to j+1 > i, then the total in prefix i decreases by 1.
- If we move from stack j > i, it doesn't affect prefix i.
Thus, prefix sums can only decrease (or stay same). So for any final configuration (a_1,...,a_n) achievable from initial (h_1,...,h_n) by moving blocks only right, we must have for all k from 1 to n:
sum_{i=1}^{k} a_i <= sum_{i=1}^{k} h_i.
Because we cannot increase the total blocks in the first k stacks. This is a necessary condition. Is it also sufficient? In such linear transfer problems (like "pouring water" only to the right), I think yes: if we have prefix sums non-increasing (i.e., final prefix sums <= initial prefix sums), and total sum equality holds for k=n (which it does because total sums are equal), then we can achieve by a greedy algorithm: process from left to right, maintaining a surplus that we can shift rightwards. Actually we can think: we have initial h_i. We want final a_i. We can only move right. So we can simulate: for i from 1 to n-1, we can move any excess from stack i to i+1. Starting with current values = h_i. For i=1, we can only move from 1 to 2. After moving, the value at 1 becomes whatever we need; but we cannot increase stack 1. So condition for stack 1: we must have a_1 <= h_1? Actually we can only move blocks out of stack 1, not into it. So we can reduce stack 1, but cannot increase it. So we need a_1 <= h_1. More generally, because moves only go right, each stack i can only receive from left and give to right. Wait, they can receive from i-1 (since moves from i-1 to i are allowed) but cannot receive from right. So they can increase from the left. So stack i can be increased by incoming moves from i-1, and decreased by outgoing moves to i+1. So final a_i can be greater than h_i if we receive from left, or less than h_i if we give to right. However, there is a global constraint: for each prefix, the total sum cannot increase. But individually, a_i can be > h_i if enough came from left. For example, initial [1,0] can become [0,1] by moving one from 1 to 2, so a_1=0 <= h_1=1, a_2=1 > h_2=0.
Thus, the condition is exactly that for all k, sum_{i=1}^{k} a_i <= sum_{i=1}^{k} h_i, with equality for k=n. This is necessary and sufficient (since we can always achieve by transferring deficits rightwards, essentially like a flow). This is reminiscent of the concept of majorization or that the initial vector dominates the final in terms of prefix sums.
Therefore, the problem reduces to: can we choose strictly increasing nonnegative integers a_i such that sum a_i = S, and for all k, prefix sums of a are <= prefix sums of h?
We need to determine existence. We can think of constructing the "best" possible increasing sequence that respects the prefix constraints and sum equality.
Alternatively, we can think in terms of a greedy strategy: We need to make heights strictly increasing. Since we can only move right, we can simulate from left to right, making each stack as high as possible while preserving the ability to make later stacks strictly increasing and not violating total sum.
Given that moving blocks only right, we can always reduce the left stacks and add to right. So to achieve strictly increasing, we'd like to have the final heights as high as possible on the right? Actually we need to satisfy increasing order, so a_i must be at least i-1 (if we start from 0) maybe minimal increasing sequence? But we can also have larger numbers.
Goal: Determine if there exists any strictly increasing sequence (a_i) with nonnegative integers, such that for each k, sum_{i=1}^{k} a_i <= P_k where P_k = sum_{j=1}^{k} h_j (initial prefix sums), and total sum = P_n.
Since total sum is fixed, condition sum a_i = P_n is automatically satisfied if we meet all prefix inequalities and the last one is equality? Actually we need to enforce sum a_i = P_n. Since for k=n, we require sum_{i=1}^{n} a_i <= P_n. But we also need equality because we cannot lose blocks. But note that we also have the ability to not move some blocks? Actually total sum is conserved, so final sum must equal P_n. So we require sum a_i = P_n. So the condition is: For k=1..n-1, prefix sums of a must be <= P_k, and for k=n, they must be equal to P_n.
So this is exactly the condition for a sequence a to be reachable.
Now we need to know if there exists a strictly increasing sequence of nonnegative integers satisfying these constraints.
We can treat this as constructing a_i greedily from left to right while ensuring that we can still assign the remaining blocks to later stacks so that they can be strictly increasing and total sum matches.
Alternatively, we can think of the minimal possible prefix sums for a strictly increasing sequence with given total sum? But total sum is fixed.
We can attempt to construct the lexicographically smallest increasing sequence that satisfies the constraints? Or we can check feasibility by trying to assign as little as possible to early stacks to leave enough for later stacks, but we also need strictly increasing.
Maybe we can derive a necessary and sufficient condition directly from the initial h_i.
Consider that we can move blocks right arbitrarily. So we can think of a process: starting from left, we can decide how many blocks to keep in stack i, and pass the rest to the right. The final height of stack i will be: after receiving from left, we may also give some to right. Actually the process is: We can simulate making the sequence increasing by ensuring that after processing stack i, the remaining blocks (those to the right plus any we moved forward) can be arranged to make increasing.
There is known editorial for Codeforces problem 1744B? Actually problem might be "Increasing" from Codeforces Round #827? I recall problem: "We have n piles, can move a stone from i to i+1. Can we make piles strictly increasing?" I think I've seen a solution: iterate from left to right, maintain a "cumulative" value. The condition is that after processing, we need to have enough to make later stacks at least i+something.
Let's derive.
Let final heights a_i (strictly increasing nonnegative integers). Since total sum fixed, the maximum possible a_i? Not needed.
We can think of building from left to right: we need a_1 < a_2 < ... < a_n. Without constraints, we can set any increasing sequence as long as sum = S. With the prefix constraints, we must have that the cumulative sum up to i is <= P_i. Since we need sum = S, the prefix constraints are essentially that we cannot assign too many blocks to early stacks.
Thus, the most restrictive is that we cannot have early stacks too high. So to maximize the chance of having an increasing sequence, we should keep early stacks as low as possible (subject to increasing property) so that we have more blocks for later stacks to achieve the increasing gap.
But also note that the increasing condition forces a_i >= a_{i-1}+1. So the minimal possible sequence (nonnegative) given n is: let a_1 be some integer x, then a_2 >= x+1, a_3 >= x+2, ..., a_n >= x+(n-1). So the minimal total sum for a given starting value x is nx + (0+1+...+n-1) = nx + n(n-1)/2. Since a_i are integers, the minimal sum for any strictly increasing nonnegative sequence is when we set a_i = x + i - 1 (with i from 1). Actually that yields the minimal sum for given starting x. Because to minimize sum for given start, we set as low as possible increments.
Thus, given total sum S, the maximum possible starting x is determined by S >= n*x + n(n-1)/2, so x <= floor((S - n(n-1)/2)/n). But we don't need to choose x; we need to see if there exists any increasing sequence satisfying prefix constraints.
Perhaps we can define a_i in terms of the remaining blocks. Another approach: Since we can only move right, we can think of it as we want to "push" blocks to the right to create increasing steps. Let's simulate a greedy algorithm: Process from left to right, maintaining a current height value for the previous stack, and we have a certain number of blocks available from the current stack plus any carried over? Actually we have a pool of blocks that we can allocate to stacks as we go.
Consider that we start with h_1. We need to decide final a_1. a_1 must be at most h_1? Not necessarily, because we could receive from left? But there is no left. So a_1 cannot be increased from incoming moves because no stack before 1. However, we could move some blocks from stack 1 to stack 2, but that would reduce a_1. So a_1 can only be <= h_1 (since we can only remove from stack 1). So a_1 <= h_1. Also a_1 must be nonnegative.
Now after we set a_1, we will have some surplus from stack 1: h_1 - a_1 that we can move to stack 2. Then stack 2 initially has h_2, plus we receive the surplus from stack 1, giving it a total of h_2 + (h_1 - a_1). However, we may also move some of that to stack 3. So the effective amount available for stack 2 to assign as its final height (before moving to right) is h_2 + (h_1 - a_1). And we need to assign a_2 such that a_2 > a_1, and a_2 <= that available amount (since we can only move out from stack 2, not receive from right). Actually we could also move some of it to stack 3, so a_2 can be at most the total amount that reaches stack 2 (i.e., h_2 + surplus from left). More precisely, the final height a_2 is whatever remains after we possibly move some to the right; it can be at most the total that arrives (since we can always discard? No, we cannot discard blocks; we must keep all blocks somewhere. So the sum of final heights is fixed. So after we decide a_2, we will move the rest to stack 3. So the condition is: we need to choose a_2 such that a_2 >= a_1+1, and also a_2 <= total available at stack 2 (which is h_2 + (h_1 - a_1)). Then the surplus moved to stack 3 is (h_2 + (h_1 - a_1)) - a_2.
Proceed similarly. At stack i, we have available = h_i + surplus from previous (i.e., from left). Then we choose a_i such that a_i >= a_{i-1}+1, and a_i <= available. Then surplus to next = available - a_i.
At the last stack n, we have available = h_n + surplus from n-1. Since there is no next, we must have a_n = available (i.e., we cannot move out, so all remaining must become a_n). And we need a_n > a_{n-1}. Actually a_n must be strictly greater than a_{n-1}, and also it equals available. So we need to check if we can choose a_i for i=1..n-1 satisfying those constraints, and then automatically a_n is determined and must be > a_{n-1}.
So the existence can be determined by a greedy approach: we want to maximize chance of success, so we should choose a_i as small as possible (subject to > a_{i-1}) to leave more for later stacks. Because later stacks need to be strictly increasing and need to accommodate the leftover. So the optimal strategy to check feasibility: set a_1 as small as possible? But a_1 must be <= h_1. The smallest a_1 is 0 (nonnegative). However, we also need eventually a_n > a_{n-1} and total sum fixed. If we set a_1 too low, we might cause a later stack to be impossible because we may not have enough to satisfy strictly increasing? Actually setting a_1 lower gives more surplus to later stacks, which should help. But there's a catch: if we set a_1 very low, then a_2 must be at least a_1+1, which is low, so also low. That consumes little from the available, leaving more for later. That seems beneficial. The only potential problem is if the final a_n ends up too small? But a_n is forced to be whatever is left. Since total sum is fixed, setting earlier stacks lower leaves more for later, making a_n larger, which is good because we need a_n > a_{n-1}. So we should minimize each a_i as much as possible. However, we also need to ensure that at each step we can pick a_i that is at most available. The minimal possible a_i given previous is a_{i-1}+1. So we should attempt to set a_i = a_{i-1}+1, provided that this value is <= available. If it's > available, then we cannot achieve because we need at least a_{i-1}+1 but we don't have enough blocks. If it's <= available, we set it to exactly a_{i-1}+1 (the smallest) to preserve maximum flexibility. Then surplus = available - (a_{i-1}+1). Continue.
At the last stack, after setting a_{n-1} = something, we have available_n = h_n + surplus_{n-1}. Then we set a_n = available_n (since we must use all). Then we need to check if a_n > a_{n-1}. If yes, then we have a valid increasing sequence. If not, it's impossible? Could there be a different choice earlier (not minimal) that makes a_n > a_{n-1} even if minimal fails? Suppose with minimal choices, a_n <= a_{n-1}. That means the total sum is too low to support a strictly increasing sequence given the prefix constraints? But could increasing some earlier a_i (i.e., using more blocks earlier) reduce a_n further, making it even smaller, so that would not help; it would make a_n even smaller. So that would worsen the inequality. Alternatively, could increasing earlier a_i make a_n larger? Wait, if we take more blocks earlier, that reduces surplus sent to later, so a_n becomes smaller, not larger. Actually surplus to later = available - a_i. If we increase a_i, we reduce surplus to later, so a_n becomes smaller. So making earlier stacks larger makes later stacks smaller, which makes it harder for a_n to be > a_{n-1}. Conversely, making earlier stacks smaller leaves more for later, making a_n larger and possibly satisfying a_n > a_{n-1}. So the optimal to satisfy a_n > a_{n-1} is to minimize earlier a_i as much as possible. So if the minimal greedy fails (i.e., a_n <= a_{n-1}), then no other choice can succeed because any other choice would make a_n smaller or equal? Let's check: Suppose we increase some a_i above the minimal, then the surplus to later decreases, which could affect a_{i+1} choices? But we could also increase a_{i+1} perhaps? However, a_n is the final sum of all remaining. Since total sum is fixed, increasing any a_i (for i < n) reduces the sum left for later stacks, thus a_n will be exactly total sum - sum_{i=1}^{n-1} a_i. So maximizing a_n requires minimizing sum of earlier a_i. So indeed the maximal possible a_n occurs when we minimize sum of a_1..a_{n-1} subject to the constraints (a_i >= a_{i-1}+1, a_i <= available_i). But careful: The available_i depends on previous choices because surplus from previous changes. If we choose a_i larger, then surplus to next is smaller, which affects the maximum allowed a_{i+1}? Actually the constraint for a_{i+1} is that it must be <= available_{i+1} which equals h_{i+1} + surplus_i. If we increase a_i, surplus_i decreases, so available_{i+1} decreases, potentially forcing a_{i+1} to be lower than it could be otherwise. This could actually force a_{i+1} to be lower, which might reduce sum of earlier even more? But a_{i+1} also must be > a_i. If we increase a_i, then the minimal a_{i+1} becomes larger (since it must be > a_i). So there's a trade-off. However, we suspect that the greedy minimal at each step (taking a_i = max(a_{i-1}+1, ?) Actually the minimal feasible a_i given the history is not necessarily a_{i-1}+1 if that is less than or equal to available; but if we set a_i higher, then a_{i+1} minimal also higher, so the total sum of early may increase. It seems that to maximize a_n, we want to minimize the sum of a_1..a_{n-1}. To minimize that sum, we want each a_i as low as possible, but also we must respect the later constraints that a_{i+1} > a_i and a_{i+1} <= available_{i+1}. Setting a_i low allows a_{i+1} to be low as well. So indeed the globally minimal sum for the first n-1 stacks, given the prefix availability constraints, is achieved by the greedy that sets each a_i as low as possible (i.e., the minimum allowed value that maintains increasing). However, we need to verify that this greedy does not inadvertently violate later constraints in a way that forces a later a_j to be impossible to choose (i.e., the minimal a_i may cause available_{i+1} to be larger, which is good). Actually if we set a_i lower, surplus_i is larger, so available_{i+1} is larger, giving more room for a_{i+1}. So lower a_i never hurts feasibility in terms of providing more blocks for later. The only potential issue is that we must ensure a_{i+1} > a_i. If we set a_i very low, the condition a_{i+1} > a_i is easier to satisfy. So the greedy of setting a_i to the minimal possible (which is either a_{i-1}+1, but also we cannot exceed available; but minimal is max( a_{i-1}+1, ??? Actually the lower bound is a_{i-1}+1 to maintain increasing. The available provides an upper bound. So the minimal feasible a_i is a_{i-1}+1, provided that this <= available. If it's > available, then it's impossible no matter what we do because we cannot achieve a_i >= a_{i-1}+1 with the blocks we have. So that would be a direct NO.
Thus, the algorithm:
For each test case:
- Let surplus = 0.
- Let prev = -1? Actually we need a_{i-1}. For i=1, we have no previous, but we need a_1. We'll set a_1 as low as possible? Minimal a_1 is 0 (since nonnegative). However, we could also set a_1 to some other value <= h_1. To maximize later, we should set a_1 as low as possible: 0. But is 0 always allowed? a_1 must be nonnegative and <= h_1. So we can set a_1 = 0. However, we need to consider if a_1=0 might cause later a_2 to be at least 1. That's fine. But is there any scenario where setting a_1=0 could cause a problem? It seems beneficial. But wait, consider the case where h_1 is 0. Then a_1 must be 0 (since can't be negative and can't be >0 because we have no blocks to put there). So a_1=0 is forced. So indeed minimal a_1 is 0. So we can set a_1 = 0 if h_1 >= 0, which it is. But is there any scenario where setting a_1=0 could cause later impossible due to some other constraint? Not really: if we set a_1=0, we have more surplus for later. The only potential issue is if we later need a_1 to be larger to allow a_2 to be larger? But we want a_2 as small as possible, so no.
But careful: The final sequence must be strictly increasing. Starting with a_1=0 is fine. However, if we set a_1=0, we might later have to have a_2 > 0. That's fine.
But is a_1 allowed to be 0? The problem says heights are number of blocks, and stacks can have 0 blocks. So yes, 0 is allowed.
Thus, we can adopt the following:
Initialize 'carry' = 0? Actually we simulate with "available" at each stack i: available = h_i + (carry from previous). Then we set a_i = max(prev+1, 0?) But for i=1, prev is undefined. We can set minimal a_1 = 0 (or maybe we could set to some larger value? But to maximize later, we set to 0). But must ensure a_1 <= available. Since available at i=1 is h_1 (carry initially 0). So we need 0 <= h_1, which holds. So set a_1 = 0.
But wait: Is it always permissible to set a_1 = 0? Consider if we have n=1. Then we need strictly increasing sequence of one element? For a single stack, "strictly increasing" trivially holds because there's no pair. So any height is okay. We can set a_1 = h_1 (since we cannot move blocks out? Actually we could move from stack 1? There's no i+1, so cannot move. So final height must equal h_1. So for n=1, we can always make it increasing (since a single element is trivially increasing). So answer is YES. Our greedy: for i=1, set a_1=0? But then at last stack (which is also first), we have to set a_1 = available = h_1 because no next? Actually the rule for last stack is different: we must consume all remaining. In our process for i from 1 to n-1 we choose a_i, and at i=n we set a_n = available. So for n=1, we are at last stack directly. We need to check if we can have a_1 = h_1 (since no moves) and it is strictly increasing by definition. So we must treat n=1 separately, or our greedy algorithm should handle last step specially: for i=1..n-1 we choose minimal a_i; for i=n, a_n = available. For n=1, we would go to the last step directly and set a_1 = h_1. That would be fine, and we need to check if a_1 is strictly increasing? It's always ok. So we can handle n=1 by not doing the minimal assignment for i=1 if it's the last. But if we apply the same minimal assignment for i=1 when n>1, we set a_1=0? Is that always valid? Let's test with examples.
Example 1: h = [1,2] (n=2). Our algorithm: i=1 (not last because n=2, so we set a_1 minimal: 0 (since <= h_1=1). Then surplus = h_1 - a_1 = 1. Then i=2 (last): available = h_2 + surplus = 2+1=3. Set a_2 = 3. Check if a_2 > a_1? 3 > 0 => YES. So output YES. But is this achievable? Starting from [1,2], we can move the block from stack 1 to stack 2, resulting in [0,3], which is strictly increasing? 0 < 3, yes. So it works. But is [0,3] allowed? Yes. So answer YES. In the sample, answer is YES. So our method gives YES.
Example 2: [1,0]. Our algorithm: a_1 = 0 (<=1). surplus = 1. i=2: available = 0+1=1, a_2=1. Check 1 > 0 => YES. So YES. Sample says YES.
Example 3: [4,4,4]. Our algorithm: a1 = 0 (<=4). surplus = 4. i=2: available = 4+4=8. Since i=2 not last (n=3), we need to set a_2 minimal: must be > a1, so at least 1. Can we set a2=1? It must be <= available (8). So set a2=1. surplus = 8-1=7. i=3: available = h3 + surplus = 4+7=11. a3 = 11. Check a3 > a2? 11 > 1 => YES. So YES. But is that achievable? We need to check if we can get [0,1,11] from initial [4,4,4]? Total sum 12. [0,1,11] sum =12. Prefix constraints: sum1:0<=4 ok; sum2:1<=8? Actually initial prefix sums: 4,8,12. Final prefix sums:0,1,12. So 1<=8 ok, 12=12 ok. So should be achievable. But can we actually get 11 in third stack? Moves: we can move blocks from stack1 to stack2 and stack3, and from stack2 to stack3. To get 11 in stack3, we need to move many blocks. Starting with [4,4,4], we can move all 4 from stack1 to stack2? Actually we can only move from i to i+1. To move a block from stack1 to stack3, we must first move it to stack2, then from stack2 to stack3. So we can route blocks. It seems possible: e.g., move 4 from stack1 to stack2: [0,8,4]; then move 7 from stack2 to stack3: [0,1,11]. That works. So YES. Sample says YES.
Example 4: [0,0]. Our algorithm: a1 = 0 (<=0). surplus = 0. i=2 (last): available = 0+0=0, a2=0. Check a2 > a1? 0 > 0? false. So NO. Sample says NO. Good.
Example 5: [0,1,0]. n=3. Our algorithm: a1 = 0 (<=0). surplus = 0. i=2 (not last): available = h2 + surplus = 1+0=1. We set a2 minimal: must be > a1, so at least 1. Check 1 <= available (1) => set a2=1. surplus = available - a2 = 0. i=3 (last): available = h3 + surplus = 0+0=0. a3=0. Check a3 > a2? 0 > 1? false. So NO. Sample says NO. Good.
Example 6: four 1e9. Our algorithm: a1 = 0 (<=1e9). surplus = 1e9. i=2: available = 1e9 + 1e9 = 2e9. Set a2 = 1 (since >0). surplus = 2e9 -1 = 1999999999? Actually 2e9 -1. i=3: available = 1e9 + surplus = 1e9 + (2e9-1) = 3e9 -1. Set a3 = a2+1 = 2? But need to ensure <= available, yes 2 <= 3e9-1. So set a3=2. surplus = available -2 = 3e9 -3. i=4: available = 1e9 + surplus = 1e9 + (3e9-3) = 4e9 -3. a4 = available. Check a4 > a3? 4e9-3 > 2 => YES. So YES. Sample says YES.
Thus, this greedy algorithm matches the sample outputs.
But is there any case where setting a1=0 is not optimal? Suppose h1 is very small, e.g., h1=0. Then a1 must be 0. So no choice. If h1>0, we could set a1>0. Could setting a1>0 ever enable a solution when a1=0 fails? As argued, a1=0 gives the maximum possible surplus to later, which is beneficial. However, consider the case where we need to keep the sequence strictly increasing, and maybe a1=0 forces a2 to be at least 1, which might be too high? But 1 is minimal positive integer. If a1=0 and we set a2=1, that's as low as possible for a2. If we set a1=1, then a2 must be at least 2, which is higher. That would consume more from available early, leaving less for later. So if a1=0 fails because later we cannot satisfy a_n > a_{n-1}, then a1=1 would also fail because it gives even less to later. So a1=0 is optimal.
But wait: Could there be a scenario where a1=0 is not allowed because we cannot have a1=0 even though h1>0? Actually we can have a1=0 by moving all blocks from stack 1 to stack 2. That's allowed if we can move blocks (since we can move any number from stack 1 to stack 2, as long as we don't need to keep any). So yes, a1=0 is achievable as long as we have enough moves? Moves are unlimited, so we can always move all blocks from stack 1 to stack 2. So it's valid.
But what about the condition that we need to move blocks one by one? That's fine; we can move all.
Thus, the greedy algorithm with a1 set to 0 seems correct.
But we must be careful: For i from 1 to n-1, we set a_i = max( a_{i-1}+1, ??? Actually the minimal we can set is a_{i-1}+1, but also we cannot set a_i lower than that because of increasing condition. However, is it possible that a_{i-1}+1 is less than 0? No, it's positive if a_{i-1} >=0. So fine.
But there is also a lower bound: a_i must be at least 0? Actually a_i could be 0 if a_{i-1} is -1? No, a_i >=0 anyway, but since a_{i-1}+1 > a_{i-1} >=0, it's >=1 for i>=2. So it's fine.
Now, we also need to ensure that a_i <= available. So condition: for each i from 1 to n-1, we need a_{i-1}+1 <= available_i. If not, then impossible.
At the last stack, we need available_n > a_{n-1}. That is, available_n >= a_{n-1}+1.
Note that available_n = total sum - sum_{i=1}^{n-1} a_i, because we used all blocks up to n-1 and passed the rest to n. So condition available_n > a_{n-1} is equivalent to total sum - sum_{i=1}^{n-1} a_i > a_{n-1} => total sum > sum_{i=1}^{n-1} a_i + a_{n-1} = sum_{i=1}^{n} a_i? Wait careful: a_n = available_n. So condition a_n > a_{n-1} means available_n > a_{n-1}. Since total sum = sum_{i=1}^{n-1} a_i + available_n, condition is sum_{i=1}^{n-1} a_i + available_n = S, so available_n = S - sum_{i=1}^{n-1} a_i. So condition: S - sum_{i=1}^{n-1} a_i > a_{n-1} => S > sum_{i=1}^{n-1} a_i + a_{n-1}. This is not automatically satisfied; it's the check.
Alternatively, we can compute directly.
Thus, the algorithm is:
For each test case:
- Read n, array h[1..n].
- If n == 1: print YES (since any single element is strictly increasing).
- Else:
- Initialize prev = 0? Actually we need to store a_{i-1}.
- Let carry = 0 (surplus from previous).
- For i from 1 to n-1:
- available = h[i] + carry.
- min_needed = (i == 1) ? 0 : (prev + 1). But careful: For i=1, we set a1 = 0? But is 0 always allowed? Let's check if a1=0 is always feasible: we need a1 <= available (which is h1). Since h1 >= 0, it's fine. So we set a1 = 0. But wait: what if n=1? Already handled. So for n>1, we can set a1=0.
- However, is there any case where a1=0 leads to later failure but a1>0 could succeed? As argued, no, because a1>0 uses more blocks early, leaving less for later, making final condition harder. So a1=0 is the best.
- But we must confirm that we can always set a1=0 regardless of h1? Yes, because we can move all blocks from stack 1 to stack 2. But what if n=2 and we set a1=0, then a2 = h1 + h2. That yields a strictly increasing sequence if h1+h2 > 0? Actually need a2 > 0. If h1+h2 > 0, then a2 >0, so 0 < a2, ok. If h1+h2 =0, then a2=0, not >0 => NO. That's correct: if both stacks are zero, cannot make increasing. So it's fine.
- So we set a_i = (i==1) ? 0 : (prev + 1), but we also must ensure a_i <= available. If a_i > available, then impossible => NO.
- Then carry = available - a_i.
- Set prev = a_i.
- After loop, for last stack i = n:
- available = h[n] + carry.
- If available > prev, then YES else NO.
But wait: In the loop for i from 1 to n-1, we set a_i = minimal. But is it always valid to set a_i = 0 for i=1? Let's test a scenario: n=2, h = [0, 0]. a1 = 0 <= available=0 ok. carry = 0. Then last: available=0, prev=0, condition available > prev? 0 > 0 false => NO. That's correct.
Another scenario: n=2, h = [0, 5]. a1=0 <=0 ok, carry=0, last: available=5, prev=0, 5>0 => YES. Indeed we can have [0,5] from [0,5] (no moves needed) which is increasing.
Now, consider n=3, h = [5,0,0]. Can we make increasing? Let's test: total sum =5. Need strictly increasing a1 < a2 < a3. The greedy: a1=0 (<=5) carry =5. i=2: available =0+5=5. a2 = prev+1 = 1 (since a1=0). 1<=5 ok. carry = 5-1=4. prev=1. i=3: available = 0+4=4. Check available > prev? 4>1 => YES. So algorithm says YES. Is that achievable? Starting [5,0,0], we can move blocks: move 4 from stack1 to stack2? But we need to get a final [0,1,4]? Let's see: we want a1=0, a2=1, a3=4. Sum=5. Prefix constraints: sum1:0<=5; sum2:1<=5? 1<=5 ok; sum3:5=5. Is it achievable? We need to move blocks from 1 to 2 and from 2 to 3. Steps: from stack1, we can move some to stack2. To get a2=1, we need stack2 to end with 1. We have h2=0. So we need to move exactly 1 block from stack1 to stack2. Then stack1 becomes 4. Then from stack2, we need to move some to stack3 to achieve a2=1 and a3=4. After moving 1 to stack2, stack2 has 1. We need final a2=1, so we cannot move away from stack2? Actually we need final a2=1, so we must not move any from stack2 to stack3. But then stack3 remains 0, so a3=0, not 4. Alternatively, we could move more from stack1 to stack2, then from stack2 to stack3. Suppose we move all 5 from stack1 to stack2: [0,5,0]. Then we need a2=1 and a3=4. So we need to move 4 from stack2 to stack3, leaving stack2 with 1, stack3 with 4. That works: [0,5,0] -> move 4 from stack2 to stack3 gives [0,1,4]. So yes, it's achievable. So algorithm correct.
Consider n=3, h = [2,0,1]. Total=3. Greedy: a1=0 (<=2) carry=2. i=2: available=0+2=2, a2 = prev+1=1 (<=2) carry=1, prev=1. i=3: available=1+1=2, check > prev? 2>1 => YES. So algorithm says YES. Can we achieve? Target: [0,1,2] sum=3. Prefix constraints: sum1:0<=2; sum2:1<=2; sum3:3=3. Achieve? Start [2,0,1]. Want final [0,1,2]. Need to move: from stack1, we need to move 2 to stack2 (since final a1=0). After moving 2 to stack2, we have [0,2,1]. Then we need a2=1, a3=2. So we need to move 1 from stack2 to stack3 to get [0,1,2]. That works. Good.
Consider n=3, h = [1,0,0]. Total=1. Greedy: a1=0 (<=1) carry=1. i=2: available=0+1=1, a2=1 (prev=0 => 1) <=1, carry=0, prev=1. i=3: available=0+0=0, check > prev? 0>1? No => NO. So algorithm says NO. Is it possible to get strictly increasing? We need a1<a2<a3, all nonnegative integers, sum=1. The only possibilities for three numbers strictly increasing are (0,1,2) sum=3; (0,1,? Actually minimal strictly increasing triple: the smallest nonnegative increasing sequence is 0,1,2 sum=3 >1. With sum=1, it's impossible because we need at least 0+1+2=3 if all three distinct. But we could have some zeros? They must be strictly increasing, so a1 < a2 < a3. If a1=0, a2>=1, a3>=2 => sum>=3. If a1= -1? No, heights can't be negative. So indeed impossible. So NO correct.
Consider n=3, h = [0,2,0] total=2. Greedy: a1=0 <=0, carry=0. i=2: available=2+0=2, a2=1 (prev=0 => 1) <=2, carry=1, prev=1. i=3: available=0+1=1, check >1? 1>1? No => NO. So algorithm says NO. Is there a way? Need a1<a2<a3, sum=2. Minimal sum for three increasing is 3. So impossible. So NO correct.
Consider n=3, h = [0,0,2] total=2. Greedy: a1=0 <=0, carry=0. i=2: available=0+0=0, a2 = prev+1=1, but 1 <=0? false -> NO. So algorithm says NO. Is it possible? Need a1<a2<a3. With total 2, impossible as above. So NO.
Thus, the greedy algorithm seems to work.
But we need to be absolutely sure that setting a1=0 is always optimal when n>1. Let's attempt to find a counterexample where setting a1=0 fails but some a1>0 works.
Suppose we have n=2, h=[1,0] total=1. Our greedy: a1=0, carry=1, last: available=0+1=1, prev=0 -> 1>0 => YES. So works.
Suppose n=2, h=[0,0] total=0: greedy gives NO. Could a1>0 help? a1>0 would require a1 <= h1=0 impossible. So no.
Suppose n=2, h=[2,0] total=2: greedy gives a1=0, a2=2 -> YES. Could a1=1 work? a1=1 <=2, then carry=1, a2=1? But a2 must be > a1, so a2 at least 2. But available for stack2 is h2+carry=0+1=1, so a2=1 not >1? Actually need a2 >1, but max is 1, so fails. So only a1=0 works. So greedy optimal.
Now n=3, h = [3,0,0] total=3. Greedy: a1=0, carry=3; i=2: available=0+3=3, a2=1, carry=2, prev=1; i=3: available=0+2=2, check 2>1 => YES. So yields YES with final [0,1,2] sum=3. That's minimal increasing triple. Could any other a1 work? a1=1: then need a2>1 => at least 2. For i=2: available = h2 + (h1-a1) = 0 + (3-1)=2. a2 min = 2, so set a2=2 ( <=2 ), carry=0; i=3: available = h3 + carry = 0+0=0, a3=0, check a3>2? false. So fails. a1=2: then a2>=3, but available = 0+(3-2)=1, insufficient. So only a1=0 works.
Consider a more subtle case: Suppose the greedy fails because at some intermediate step, a_i (minimal) > available, but maybe if we had set a previous value higher, the available at that step would be different (since carry from previous changes). Could raising a_{i-1} increase available at step i? Actually available_i = h_i + carry_{i-1}, and carry_{i-1} = (h_{i-1} + carry_{i-2}) - a_{i-1}. So if we increase a_{i-1}, carry_{i-1} decreases, thus available_i decreases. So increasing a_{i-1} reduces available_i, making it even harder to satisfy a_i >= a_{i-1}+1. So if minimal a_{i-1} leads to a_i > available_i, then any larger a_{i-1} would make available_i even smaller and also require a_i to be at least a_{i-1}+1 which is even larger. So it would be even more impossible. So failure at step i (a_i needed > available_i) is definitive.
What about the final condition? Greedy sets a_i minimal, so sum_{i=1}^{n-1} a_i is minimized, thus a_n = S - sum_{i=1}^{n-1} a_i is maximized. So if even with maximal a_n we have a_n <= a_{n-1}, then for any other choices, a_n would be smaller or equal, and a_{n-1} would be at least as large? Actually if we increase some early a_i, sum_{i=1}^{n-1} a_i increases, so a_n decreases. Also a_{n-1} could be larger. So the inequality a_n > a_{n-1} would be even less likely. So if greedy fails final condition, no other assignment can succeed.
Thus, the greedy algorithm with a1=0 (for n>1) gives necessary and sufficient condition.
But wait: Could there be a scenario where we need to set a1 to a value greater than 0 because a1=0 is not allowed? Is a1=0 always allowed? Yes, as argued we can always move all blocks from stack1 to stack2, so a1 can be 0. However, is it always allowed to set a1=0 and also ensure later stacks can get enough? That's what we are checking.
But consider n=2, h=[0,0]. a1=0 allowed? a1=0 <= h1=0, yes. So fine.
Thus, the algorithm seems correct.
But let's double-check with edge cases. n=1: always YES because a single element is trivially increasing. Our loop for i=1 to n-1 would not run; we need to handle last stack. For n=1, we can simply print YES.
Now, what about n=100, h_i up to 1e9, sum n across test cases <= 1e4. So O(n) per test case is fine.
We must also consider that the greedy may cause overflow when computing available (which could be up to sum of h_i, up to n * 1e9 = 100e9 = 1e11, which fits within 64-bit integer (signed 64-bit up to 9e18). So we can use 64-bit (long long in C++).
Thus, implement:
For each test case:
- read n.
- read vector h (n).
- if n == 1: print "YES".
- else:
- long long carry = 0;
- long long prev = 0; // a_{i-1}
- bool possible = true;
- for i from 0 to n-2 (0-indexed) (i.e., stacks 1 to n-1):
- long long available = h[i] + carry;
- long long ai;
- if i == 0: // first stack ai = 0; // minimal
- else: ai = prev + 1;
- if (ai > available) { possible = false; break; }
- carry = available - ai;
- prev = ai;
- if possible:
- long long last_available = h[n-1] + carry;
- if (last_available > prev) then YES else NO.
- else: NO.
But we need to confirm that for i=0 (first stack), we set ai=0. Is there any scenario where we need to set ai to a value >0 because later constraints might require a certain minimum? As argued, it's optimal to set it as low as possible. So we set 0.
But wait: What if h[0] = 0? Then ai=0 is forced. That's fine.
What if h[0] is positive but we set ai=0, we pass all blocks to the right. That's fine.
Thus, algorithm seems solid.
Let's test with a few more cases manually.
Case: n=3, h = [1, 100, 0]. total=101. Greedy: a1=0, carry=1; i=2: available=100+1=101, a2 = prev+1 = 1, carry=100, prev=1; i=3: last_available = 0+100=100, check > prev? 100>1 => YES. So YES. Is it achievable? We need [0,1,100] sum=101. Prefix constraints: 0<=1; 1<=101? Actually initial prefix sums: 1,101,101. Final: 0,1,101. All okay. So achievable. Indeed, move 1 from stack1 to stack2? Actually we need final a2=1, so we can move 0 from stack1? Wait a1=0 so we move all 1 from stack1 to stack2, making stack2=101, then move 100 from stack2 to stack3 to get stack2=1, stack3=100. Works.
Case: n=3, h = [5, 0, 5] total=10. Greedy: a1=0, carry=5; i=2: available=0+5=5, a2=1, carry=4, prev=1; last: available=5+4=9, check >1 => YES. So YES. Final [0,1,9] sum=10. Prefix constraints: 0<=5, 1<=5, 10=10. Achievable? Move 5 from stack1 to stack2 (making [0,5,5]), then move 4 from stack2 to stack3 (making [0,1,9]). Works.
Case: n=3, h = [2, 1, 0] total=3. Greedy: a1=0, carry=2; i=2: available=1+2=3, a2=1, carry=2, prev=1; last: available=0+2=2, check >1 => YES. So YES. Final [0,1,2]. Achievable: Move 2 from stack1 to stack2: [0,3,0]; move 2 from stack2 to stack3