GSSQUNCE - Sequence

no tags 

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


hide comments
NISHANT RAJ: 2014-03-26 22:13:42

tutorial stuff ...
--ans(Francky)--> Moved ;-)

Last edit: 2014-03-26 22:20:20
Jumpy: 2014-03-26 19:33:17

@joud Zouzou u r right

Nitin Sharma: 2014-03-15 19:22:22

Both the sequences should be non-empty !! Watch out for constraints.

Shivam: 2014-02-15 10:39:40

please add to tutorial..... silly question...

Satyaki Upadhyay: 2013-10-23 13:42:21

can be sequence consist of only one integer or should there be atleast 2?

Suyash Garg: 2013-09-17 00:18:32

move it to the tutorial section

joud zouzou: 2013-09-02 13:04:58

One integer can be a decreasing sequence and increasing sequence right? or it should contain more than 1 element?

auror: 2013-08-20 14:00:50

give some test cases

BLANKRK: 2013-07-09 16:29:41

too eazy...


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