Remove and Add
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 1800
Tags: *special, greedy

You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ integers.

You goal is to make is strictly increasing. To achieve that, you perform each of the following operations exactly once:

- first, remove any element;
- second, select any number of elements (possibly, none or all $$$n-1$$$) and add $$$1$$$ to them.

Note that you are not allowed to rearrange the elements of the array.

For the resulting array $$$a'$$$, $$$a'_1 < a'_2 < \dots < a'_{n-1}$$$ should hold. Determine if it's possible to achieve that.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of elements of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print YES if it's possible to remove one element and add $$$1$$$ to some elements (possibly, none or all), so that the array becomes strictly increasing. Otherwise, print NO.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, you can remove the third element and add $$$1$$$ to the second and the last element. $$$a'$$$ will become $$$[4, 5, 6]$$$, which is strictly increasing.

In the second testcase, there is no way to perform the operations, so that the result is strictly increasing.

In the third testcase, you can remove either of the elements.

In the fourth testcase, you are already given a strictly increasing array, but you still have to remove an element. The result $$$a'$$$ can be $$$[1, 3]$$$, for example.

Example input:
8
4
4 4 1 5
5
4 4 1 5 5
2
10 5
3
1 2 3
3
2 1 1
4
1 1 1 1
4
1 3 1 2
5
1 1 3 3 1

Example output:
YES
NO
YES
YES
YES
NO
YES
YES

Editorial:
Consider the problem with no removal operation. You are allowed to increase some elements by $$$1$$$, and you are asked to determine if you can make the array strictly increasing.
This can be solved with a simple greedy. Process elements one by one. If some element is smaller than the previous one, you definitely can't. If it's equal, you have to increase it by $$$1$$$. If it's greater, it's optimal to not change it. You are allowed to not change it, and this will give more freedom to later elements.
How can a removal help? Well, if the process completes as is, then it doesn't matter. You can remove any element, and the array will remain strictly increasing.
Otherwise, it gets stuck at some point: some element is smaller than the previous one. The idea is that it's enough to only consider removing one of these two elements. The solution would be to try both options and run the algorithms with no removals on both of them. If any succeeds, then the answer is YES. If neither does, the answer is NO.
Why are they enough? Obviously, removing anything to the right of them won't help, they will still fail the algorithm. The next step is to realize that the former of the two elements have to be increased by $$$1$$$ in the algorithm. Moreover, before the increase, it had to be equal to the latter one. If any of these things don't hold, nothing will get fixed. Why was that element increased then? The element before it was equal to it. Thus, removing the former element will leave an element equal to the latter one. And not removing it will also leave an element equal to the latter one. Thus, it's never more optimal to remove anything to the left of these elements.
Overall complexity: $$$O(n)$$$ per testcase.