Знаєте цю задачу?#13112

Знаєте цю задачу?

1 секунда
256 мегабайтів

Задано масив цілих чисел h_1, h_2, \ldots, h_n. Розбийте його на дві підпослідовності, тобто віднесіть кожен елемент рівно до однієї з двох підпослідовностей (будь-яка з них може бути порожньою), так, щоб:

Визначте, чи існує таке розбиття.

Вхідні дані

Перший рядок містить одне ціле число (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

Loading
Loading

Примітка

У першому тестовому випадку h = [3, 5, 5, 2, 6, 1], і відповідне розбиття існує, тож відповідь — YES.

  • Наприклад, неспадною підпослідовністю може бути , а незростаючою — 5, 5, 2, 1.

  • Інше відповідне розбиття: неспадна підпослідовність — 3, 5, 5, 6, а незростаюча — .

На рисунку показано перше з цих розбиттів: неспадна підпослідовність — темна (суцільна лінія), а незростаюча — світла (пунктирна лінія).

У другому тестовому випадку h = [2, 1, 4, 3]. Припустимо, що елемент належить незростаючій підпослідовності.

  • Тоді раніші й менші елементи і не можуть їй належати, отже, обидва належать неспадній підпослідовності, але ця підпослідовність не може містити , за яким іде .

  • Отже, елемент належить неспадній підпослідовності, і тоді пізніший і менший елемент належить незростаючій.

  • Тепер елементи і раніші й менші за , тож вони не можуть належати незростаючій підпослідовності, і знову обидва мали б належати неспадній, що неможливо.

Тому відповідь — NO.

У третьому тестовому випадку всі елементи можуть належати одній підпослідовності, а інша залишається порожньою.

У п'ятому тестовому випадку незростаюча підпослідовність — , а неспадна — .