Нассер і рівний масив#13082

Нассер і рівний масив

1 секунда

256 мегабайтів

Нассер має масив $a$ з $n$ додатних цілих чисел. Він може виконувати наведені нижче операції будь-яку кількість разів (можливо, жодного) і в довільному порядку:

1. Вибрати індекс $i$ ( $1 \leq i \leq n$ 1 \le i \le n) і збільшити $a_{i}$ a_i на $2$ .

2. Вибрати відрізок $[l, r]$ [l, r] ( $1 \leq l < r \leq n$ 1 \le l < r \le n) такий, що $a_{l} = a_{l + 1} = \dots = a_{r}$ a_l = a_{l+1} = \ldots = a_r, і збільшити кожне з чисел $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r на $1$ .

Зауважте, що друга операція вимагає, щоб вибраний відрізок містив щонайменше два елементи, усі з яких є рівними на момент виконання операції. Наприклад, якщо $a = [4, 5, 5, 7]$ a = [4, 5, 5, 7], то відрізок $[2, 3]$ вибрати можна, а відрізки $[1, 2]$ та $[2, 4]$ — ні.

Визначте, чи може Нассер зробити всі елементи масиву рівними.

Вхідні дані

Кожен тест містить декілька тестових випадків. Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків. Далі йде опис тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — розмір масиву.

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

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

Вихідні дані

Виведіть YES, якщо за допомогою дозволених операцій можна зробити всі елементи рівними. Інакше виведіть NO.

Відповідь можна виводити в будь-якому регістрі. Наприклад, рядки yEs, yes, Yes та YES будуть зараховані як правильні позитивні відповіді.

Приклади

Приклад 1

Примітка

У першому тестовому випадку $a = [1, 2]$ a = [1, 2]. Різниця $a_{2} - a_{1}$ a_2 - a_1 дорівнює $1$ . Перша операція змінює цю різницю рівно на $2$ , тому вона завжди залишається непарною і ніколи не стає рівною $0$ . Другу операцію можна застосувати лише до двох рівних сусідніх елементів, тож тут вона ніколи не може бути застосована. Отже, елементи ніколи не зможуть стати рівними.

У другому тестовому випадку $a = [2, 4]$ a = [2, 4]. Застосуємо першу операцію з $i = 1$ i = 1: $[2, 4] \to [4, 4]$ [2, 4] \to [4, 4].

У четвертому тестовому випадку $a = [3, 2, 2, 1]$ a = [3, 2, 2, 1]. Застосуємо другу операцію з $[l, r] = [2, 3]$ [l, r] = [2, 3]: $[3, 2, 2, 1] \to [3, 3, 3, 1]$ [3, 2, 2, 1] \to [3, 3, 3, 1]. Потім застосуємо першу операцію з $i = 4$ i = 4: $[3, 3, 3, 1] \to [3, 3, 3, 3]$ [3, 3, 3, 1] \to [3, 3, 3, 3].

Оцінювання

Підзадача $1$ ( $100$ балів) : Додаткових обмежень немає.