Cheolsoo is a cryptographer in ICPC(International Cryptographic Program Company). Recently, Che- olsoo developed a cryptographic algorithm called ACM(Advanced Cryptographic Method). ACM uses a key to encrypt a message. The encrypted message is called a cipher text. In ACM, to decrypt a cipher text, the same key used in the encryption should be applied. That is, the encryption key and the de- cryption key are the same. So, the sender and receiver should agree on a key before they communicate securely using ACM. Soon after Cheolsoo finished the design of ACM, he asked its analysis on security to Younghee who is a cryptanalyst in ICPC. Younghee has an interest in breaking cryptosystems. Actually, she developed many attacking meth- ods for well-known cryptographic algorithms. Some cryptographic algorithms have weak keys. When a message is encrypted with a weak key, the message can be recovered easily without the key from the cipher text. So, weak key should not be used when encrypting a message. After many trials, she found the characteristic of weak keys in ACM. ACM uses a sequence of mutually distinct positive integers (N1, N2, . . . , Nk) as a key. Younghee found that weak keys in ACM have the following two special patterns: There are four integers Np,Nq,Nr,Ns(1 ≤ p < q < r < s ≤ k) in the key such that (1) Nq > Ns > Np > Nr or Nq < Ns < Np < Nr For example, the key (10, 30, 60, 40, 20, 50) has the pattern in (1); ( , 30, 60, , 20, 50). So, the key is a weak key in ACM. But, the key (30, 40, 10, 20, 80, 50, 60, 70) is not weak because it does not have any pattern in the above. Now, Younghee wants to find an efficient method to determine, for a given key, whether it is a weak key or not. Write a program that can help Younghee. Input The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case starts with a line containing an integer k, the length of a sequence repressenting a key, 4 ≤ k ≤ 5, 000. In the next line, k mutually distinct positive integers are given. There is a single space between the integers, and the integers are between 1 and 100,000, both inclusive. Output Print exactly one line for each test case. Print ‘YES’ if the sequence is a weak key. Otherwise, print ‘NO’. Sample Input 3 6 10 30 60 40 20 50 8 30 40 10 20 80 50 60 70 4 1 2 20 9
2/2 Sample Output YES NO NO