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".


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 seperated integers denoting A[i]. (0 <= A[i] <= N)


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


0 1
1 1 


  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
P_Quantum: 2014-01-21 21:30:58

Easy one..!!

Rishav Goyal: 2014-01-18 20:15:18

i like such problems which are less implemented based! lazy abit

Rishabh Dugar: 2014-01-18 18:13:56

tutorial stuff

Rajat Goyal: 2014-01-14 19:48:19

easy one

Mitch Schwartz: 2014-01-14 19:48:19

@Kajan Talreaj, I hid your comment because you asked for spoilers when I had just left a comment not to do that. If the problem setter unhides your comment, that's fine (I think he should have final word here), but this behavior is becoming very commonplace on SPOJ and it really shouldn't be; I would like to discourage it. The forum is there for debugging help, etc. I know it's been overrun by spam at the moment; I'll try to talk to admins to see if there's some plan to take care of that.

---> I agree with you completely.

Last edit: 2014-01-14 11:25:52
Mitch Schwartz: 2014-01-14 19:48:19

@ALOK KUMAR: If you think there is something unclear in the statement, specify it. Explaining the test cases beyond what is in the problem statement is generally a spoiler, and how can anyone explain the question when we don't know which part you are not understanding?

ALOK KUMAR: 2014-01-14 19:48:19

will anyone explain the test cases and also the question

Bhavik: 2014-01-14 19:48:19

problem asks for validity of an array ...

Last edit: 2014-01-12 19:46:53
anurag garg: 2014-01-14 19:48:19


Last edit: 2014-01-13 14:52:45

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