Melody

Time limit1sMemory limit1024 MB

Summary

Given counts a_1 to a_N for notes 1 to N, decide whether a sequence starting at note 1 can visit each note a_i times, moving to an adjacent note at each step.

Level: Medium6 of 10
Topics: Math, Graph, Prefix sum
Solved: No attempts yet

Problem

Seonghyeon, who likes composing, wants to make a melody using only $N$ notes. The notes are numbered from $1$ to $N$ . Arranging all $N$ notes in the order you want makes a melody.

Seonghyeon wants to build the melody under these rules.

The first note of the melody must be note $1$ .
To keep the melody natural, note $x$ must be followed by note $x-1$ or note $x+1$ .
The melody must contain notes $1,2,\cdots ,N$ $a_1,a_2,\cdots ,a_N$ times respectively.

Given $a_1,a_2,\cdots ,a_N$ , determine whether a melody that satisfies the rules above can be made.

Input

The first line contains the number of test cases $T(1\le T\le 200\, 000)$ .

The first line of each test case contains an integer $N(1\le N\le 200\, 000)$ .

The second line of each test case contains integers $a_1,a_2,\cdots ,a_N(1\le a_i\le 10^9)$ separated by spaces.

The sum of $N$ over all test cases is at most $200\, 000$ .

Output

For each test case, print YES if a melody that satisfies the rules can be made, and NO otherwise.

Examples1

Example 1

Input

8
2
2 1
4
1 2 3 4
1
1
3
1 2 3
5
1 2 2 2 1
10
1 1 1 1 1 1 1 1 1 1
6
2 3 1 2 3 2
6
3 4 2 3 4 2

Expected output

YES
NO
YES
NO
YES
YES
NO
YES