Випуклий масив

Вхідні дані

У першому рядку задано одне ціле число $T$ $(1 \leq T \leq 1 0^{5})$ (1\le T\le 10^5) — кількість наборів вхідних даних. Далі задано опис наборів вхідних даних.

У першому рядку кожного набору вхідних даних задано одне ціле число $n$ $(3 \leq n \leq 3 \cdot 1 0^{5})$ (3\le n\le 3\cdot 10^5) — довжина масиву $a$ .

У другому рядку кожного набору вхідних даних задано $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(0 \leq a_{i} \leq 1 0^{9})$ (0\le a_i\le 10^9) — елементи масиву $a$ .

Гарантується, що сума $n$ по всім наборам вхідних даних одного тесту не перевищує $3 \cdot 1 0^{5}$ 3\cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть в окремому рядку «YES», якщо шукана перестановка існує, і «NO» в протилежному випадку.

Приклади

Приклад 1

Loading

Примітка

У першому наборі вхідних даних першого прикладу перестановками масиву $[0, 3, 4, 6]$ [0, 3, 4, 6], які задовольняють описану умову, є $[4, 0, 3, 6]$ [4, 0, 3, 6] та $[6, 3, 0, 4]$ [6, 3, 0, 4].

Оцінювання

Нехай $S$ — сума $n$ по всім наборам вхідних даних одного тесту.

( $3$ бали): $n = 4$ n = 4;
( $4$ бали): $T = 1$ T = 1, $n \leq 7$ n \le 7;
( $7$ балів): $T = 1$ T = 1, $n \leq 15$ n \le 15;
( $5$ балів): якщо якась шукана перестановка існує, то існує така шукана перестановка, для якої виконується $b_{1} \geq b_{2}$ b_1 \ge b_2 та $b_{2} \leq b_{3}$ b_2 \le b_3;
( $17$ балів): $S \leq 50$ S \le 50;
( $10$ балів): $S \leq 400$ S \le 400;
( $13$ балів): $S \leq 2000$ S \le 2000;
( $9$ балів): $S \leq 8000$ S \le 8000;
( $18$ балів): $a_{i} \leq 1 0^{6}$ a_i \le 10^6 для $1 \leq i \leq n$ 1 \le i \le n;
( $14$ балів): без додаткових обмежень.