GSSQUNCE - Sequence

Supervin likes counting. In this problem, he invites you to count together

Supervin defines an increasing sequence is a non-empty sequence {a1,a2,…ap} such that for all i < p, ai < ai+1

Supervin defines a decreasing sequence is a non-empty sequence {b1,b2,…bq} such that for all i < q, bi > bi+1

Supervin has a sequence {c1,c2,…cn} and he wants to divide the sequence into two sequences. Supervin requires that one of the sequences is an increasing sequence, while the other one is a decreasing sequence. Supervin may rearrange the numbers in his sequence before dividing it.

You are given the initial sequence that Supervin has. You have to determine whether Supervin can divide the sequence according to his condition.

Input

The first line consist of integer T, the number of cases (at most 20 each input file)

T cases follow. Each cases has :

Line 1 : Integer N, the number of integers in Supervin’s sequence.

Line 2 : N space-separated integers indicating Supervin’s sequnce.

Output

The output should contain T lines. The i-th line contains the output "YES" if Supervin can divide the i-th sequence as desired or "NO" if Supervin can't divide the i-th sequence as desired.

Example

Input:

1

5

2 4 5 3 2

Output: YES


Explanation :

For example, he can divide the sequence to :

Increasing sequence : {2,3,4}

Decreasing sequence : {5,2}

Constraints

1 ≤ N ≤ 50 000

Each number in Supervin’s sequence is a non-negative integer less than 1 000 000 000


Added by:jonathanirvings
Date:2012-08-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Jonathan Irvin Gunawan

hide comments
2012-08-16 19:22:16 Buda IM (retired)
he can REARRANGE numbers, keep that in mind
2012-08-16 09:02:43 Francky
0.5s in Python ?
2012-08-16 09:01:14 Jonathan Irvin Gunawan
yes, my second solution works under 0.5s, so I decided to reduce it back to 2s.
I'm really sorry about this.
2012-08-16 08:53:05 Francky
Nice little problem.
I did my best in Python3, and still TLE. It could be fine to let it possible.
Edit : With Py2, it was AC.
Edit : Hey, You changed twice the time limit, with 3s, I had AC, and now, back to 2s, second rejudged I got TLE !!!

Last edit: 2012-08-16 08:58:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.