Description

称一个长度为 $n$ 的数列 $a$ 为增减数列，满足：

1. $1\le a_i\le k$

2. $a_i=a_{i-1}\pm1(i>1)$

不保证 $a_1=1$

已知一个数列中每种数的数量，求它是否可能是增减数列。

Format

Input

第一行一个整数 $T(T\le10^5)$，表示 $T$ 组数据。

对于每组数据：

第一行一个数 $k$。

第二行 $k$ 个数 $c_1,c_2,\dots,c_k(a_i>0)$。

$c_i$ 表示数字 $i$ 的数量。

$\sum a_i\le10^9$

$\sum k\le 5\times10^5$

Output

每个询问一行，可能输出 YES，不可能输出 NO。

Samples

3
3
1 2 1
3
1 3 1
3
1 4 1

YES
YES
NO

Limitation

数据 2: $2,1,2,3,2$ 是其中一种可能的数列。