Disjoint LIS and LDS

题目描述

You are given a permutation $p$ of length $n$.

A subsequence of $p$ is obtained by deleting zero or more elements from $p$ without changing the order of the remaining elements.

A subsequence is called increasing if its elements are strictly increasing, and decreasing if its elements are strictly decreasing.

A longest increasing subsequence, abbreviated as LIS, is an increasing subsequence with the maximum possible length among all increasing subsequences of $p$. Similarly, a longest decreasing subsequence, abbreviated as LDS, is a decreasing subsequence with the maximum possible length among all decreasing subsequences of $p$.

Determine whether there exist an LIS and an LDS of $p$ such that they are disjoint, i.e. they do not use the same position of the original permutation.

输入格式

The first line contains an integer $T$ ($1 \le T \le 5 \cdot 10^5$), the number of test cases.

Each test case consists of two lines.

The first line of each test case contains an integer $n$ ($1 \le n \le 5 \cdot 10^5$), the length of the permutation.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), forming a permutation of $1, 2, \ldots, n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

输出格式

For each test case, output YES if there exist a longest increasing subsequence and a longest decreasing subsequence that are disjoint.

Otherwise, output NO.

You may print each letter in any case. For example, YES, Yes, and yes are all accepted.

样例输入 #1

6
1
1
4
2 4 1 3
4
2 1 4 3
5
1 2 3 4 5
5
5 4 3 2 1
8
3 7 1 5 8 2 6 4

样例输出 #1

NO
YES
NO
NO
NO
YES