SPCU - Gopu and Validity of Arrangement

N persons are standing in a line. Height of each person is between 1 and N and height of each person is distinct. 

You are  given an array A where A[i] denotes how many persons are there before the i_th person having heights greater than the height of the ith person. For a person i, all the persons from 1 to i - 1 are considered to be before him. eg, For person 2, person 1 is considered before him.

You have to find out whether this array can be valid for some arrangement of persons. If you can uniquely do so then output "YES" Otherwise output "NO".

Input

First line contains T : number of test cases. (1 <= T <= 20).

For each test First line contains an integer n. (1 <= N <= 10^5)

Next line contains n space separated integers denoting A[i]. (0 <= A[i] <= N)

Output

For each test case, output "YES" or "NO" according to answer.

Example

Input:
2
2
0 1
2
1 1 Output: YES
NO

Explanation

For the first test case, [2, 1] is a valid case, First person has height 2, second person has height 1. 

For the second test case, no valid test case exists.


Added by:praveen123
Date:2014-01-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge

hide comments
2016-06-17 12:04:19
One of the easiest question I have ever solved! :P :D
2016-04-13 18:34:15 utkarsh538
easy question,just find the logic.
2015-12-27 11:49:28
Its amazing how a matter of time impacts your performance in coding. 3 months ago, I got 5-6 WA's on this, and today it took me 5 minutes to solve this. I am laughing at myself from 3 months ago.. :D
2015-10-31 05:19:32 rahul_verma
don't care of test case take your own test case
2015-08-25 09:55:05 Sarthak Taneja
My 250th ... :D
2015-08-08 10:51:12 MishThi
Easy ques. But, beware of the white spaces in some of the test cases.. :P
2015-07-17 00:39:05 hrishabh
Easy one...!!
Ac in first go :)
Aftr a long time :D
2015-06-30 21:19:38 mrx
Lol, confidence booster :P
2015-04-02 20:22:20 Dhruv k14
AC in 1st go after a reaaaallly long time,seriously needed that confidence :)
2015-01-04 00:23:01 Sahil Dua
Very easy one.
But how can I improve timing, any clue? I got AC in 0.39s

EDIT: Fast I/O with cin.tie(NULL) and passed in 0.01 ;)

Last edit: 2015-01-04 01:39:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.