PERMPATT - Check 1324

no tags 

Given a permutation P[1...n] of {1,2,...n}, you should output if the permutation contains a pattern of the form 1324. That is, do there exist indices  1 <= i1 < i2 < i3 < i4 <= n such that  P[i1] < P[i3] < P[i2] < P[i4]. For example, P = 6 8 5 4 9 3 7 2 1 10 contains one: the indices 1, 2, 7, 10 correspond to the sequence  6 8 7 10 which is a 1324 pattern.

Input

First line contains T, the number of test cases

Each of the next T lines contains n (1 <= n <= 100000), followed by n integers, representing a permutation of [1,2,..,n].

SUM( n * log2(n)) over all test cases <= 108. Do not assume anything else about the number of test cases or their distribution.

Output

Output T lines, one per test case: "yes"(without quotes) if the permutation contains a 1324 pattern or "no" (without quotes) otherwise.

Warning: Huge I/O

Example

Input:
2
10 6 8 5 4 9 3 7 2 1 10
10 5 3 4 7 9 10 8 6 2 1

Output:
yes
no


Added by:konqueror
Date:2010-07-23
Time limit:0.564s-6.325s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET