KURUK14 - GENIE SEQUENCE

A Genie Sequence is a sequence in which every element indicates the number of elements present before or after it. Given an array of numbers, find whether you can form a Genie sequence or not.

Input

First line contains a single integer T, the number of test cases. It is followed by T cases each of which contains two lines. First line of each test case contains a single integer N. The next line contains N integers separated by a single space.

Output

For each test case output a single line containing "YES" (without quotes) if it is possible to form a genie sequence or "NO" (without quotes) if it is not possible.

Constraints

1 <= T <= 20

2 <= N <= 1000

1 <= ai <= 1000

Example

Input:
1
4
1 3 3 2

Output:
YES

Explanation for the test case:

The Genie sequence is {3, 1, 2, 3}. The first element '3' in the sequence indicates that three numbers are after it, the 2nd element '1' indicates that one number if before it, the 3rd element '2' indicates that two elements are before it and the last element indicates that three elements are before it. So the answer is YES.


Added by:785227
Date:2014-01-31
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 JAVA PERL PYTHON PYTHON3
Resource:Kurukshetra Onsite Programming Contest

hide comments
2021-12-27 05:20:49
hint: use map, try out some of your own examples and try to get the logic.
Remember if there is a number >= n, the answer will be NO.

Last edit: 2021-12-27 05:21:34
2021-06-09 08:59:14
Great problem for using Hash map
2021-04-07 14:05:25
Reminds me of frequency distribution table of class 10 , nostalgia :D
2020-03-19 12:28:56
Why 1 1 2 3 4 gives NO?
It should be 1 2 3 4 1 so YES isn't it?
2020-01-16 12:04:04
Easy, Done in O(n) in 2nd go.
This is a good one. plz try it once before seeing the solution.
2019-12-14 06:37:24
lengthy but got it accepted :D
2017-09-12 19:22:47
Using O(n) should be the main motive behind solving this question.
2017-09-06 22:10:22
I do four walks through the sequence to determine the answer
There are auxiliary walks also
With auxiliary walks there are 9 walks overall
(including getting input)
So the algorithm is O(n) space and time complexity
2017-08-25 21:41:41
do it in O(n) just see backward and forwardshift for each element in array
good problem.AC in 2nd go
2017-08-22 18:25:13
Good Problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.