Weakness in an Encryption Algorithm

Time limit2sMemory limit128 MB

Summary

Given a sequence, decide if four indices p<q<r<s exist forming a specific interleaved value pattern, requiring an efficient algorithm beyond brute force for n up to 5000.

Level: Medium7 of 10
Topics: Binary search, Array, Divide and conquer, Brute force
Solved: No attempts yet

Problem

Suppose a sequence A[1], A[2], ..., A[n] is encrypted. A certain encryption algorithm has a weakness: for some sequence shapes, the original sequence cannot be recovered uniquely.

Given a sequence, determine whether it has this weakness.

Choose four distinct indices p, q, r, s such that 1 <= p < q < r < s <= n. The sequence has the weakness if at least one of the following conditions holds.

A[q] < A[s] < A[p] < A[r]
A[q] > A[s] > A[p] > A[r]

Input

The first line contains the number of data sets T, where 1 <= T <= 10.

Each data set consists of two lines. The first line contains the sequence length n, where 4 <= n <= 5,000. The second line contains A[1], A[2], ..., A[n] in order.

Each A[i] is between 1 and 10,000, inclusive, and all values in one data set are distinct.

Output

For each data set, print one line. Print Yes if the sequence has the weakness, and No otherwise.

Examples1

Example 1

Input

3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9

Expected output

Yes
No
No