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.


hide comments
sk128: 2021-04-02 06:50:25

I humbly request the problem setters to mention that YES , Yes and yes will be treated differently.

[NG]: Unless stated otherwise, outputs in SPOJ problems have to follow the specification exactly.

Last edit: 2021-04-02 11:46:11
vivek_prime: 2021-01-22 17:41:29

Easy question
Think about this case -
Two persons and both of them having same height then find what should be the valid array

mrdevesh_00: 2019-12-18 23:00:05

VERY EASY AC IN ONE GO!!!!

wolfie10: 2019-05-17 20:48:58

the logic is fairly simple and straightforward..test cases are deceptive.. :P

silentknight16: 2019-02-18 18:47:04

Tricky ;)

be1035016: 2018-01-18 16:32:41

easy 1

kotal_kahn: 2017-07-22 17:47:39

why it is showing the wrong answer even though my logic is correct

Shivam Gupta: 2017-03-14 12:29:13

Don't think too much, its a trick question

gajalchouhan: 2017-03-08 09:03:15

please anyone can give me some another example when the print is coming " no".

Anuj Arora: 2016-08-17 22:27:26

Move this to tutorial


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