PERMPATT - Check 1324
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: | 1s-6.325s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |