Задано масив цілих чисел h_1, h_2, \ldots, h_n. Розбийте його на дві підпослідовності, тобто віднесіть кожен елемент рівно до однієї з двох підпослідовностей (будь-яка з них може бути порожньою), так, щоб:
перша підпослідовність була неспадною: якщо вона складається з елементів з індексами i_1 < i_2 < \ldots < i_k, то h_{i_1} \le h_{i_2} \le \ldots \le h_{i_k};
друга підпослідовність була незростаючою: якщо вона складається з елементів з індексами j_1 < j_2 < \ldots < j_l, то h_{j_1} \ge h_{j_2} \ge \ldots \ge h_{j_l}.
Визначте, чи існує таке розбиття.
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових випадків.
Кожен тестовий випадок складається з двох рядків. Перший рядок містить ціле число (1 \le n \le 10^6) — довжину масиву. Другий рядок містить цілих чисел h_1, h_2, \ldots, h_n (0 \le h_i \le 10^9).
Сума за всіма тестовими випадками не перевищує 10^6.
Для кожного тестового випадку виведіть рядок YES, якщо відповідне розбиття існує, і NO інакше.
Слова YES і NO можна виводити в будь-якому регістрі.
Приклад 1
У першому тестовому випадку h = [3, 5, 5, 2, 6, 1], і відповідне розбиття існує, тож відповідь — YES.
Наприклад, неспадною підпослідовністю може бути , а незростаючою — 5, 5, 2, 1.
Інше відповідне розбиття: неспадна підпослідовність — 3, 5, 5, 6, а незростаюча — .
На рисунку показано перше з цих розбиттів: неспадна підпослідовність — темна (суцільна лінія), а незростаюча — світла (пунктирна лінія).
У другому тестовому випадку h = [2, 1, 4, 3]. Припустимо, що елемент належить незростаючій підпослідовності.
Тоді раніші й менші елементи і не можуть їй належати, отже, обидва належать неспадній підпослідовності, але ця підпослідовність не може містити , за яким іде .
Отже, елемент належить неспадній підпослідовності, і тоді пізніший і менший елемент належить незростаючій.
Тепер елементи і раніші й менші за , тож вони не можуть належати незростаючій підпослідовності, і знову обидва мали б належати неспадній, що неможливо.
Тому відповідь — NO.
У третьому тестовому випадку всі елементи можуть належати одній підпослідовності, а інша залишається порожньою.
У п'ятому тестовому випадку незростаюча підпослідовність — , а неспадна — .