Сусідні послідовні
Limits: 2 sec., 256 MiB
У Марічки є масив \(a\) з \(n\) цілих чисел.
За одну операцію Марічка може взяти два сусідні елементи масиву, значення яких відрізняються на одиницю, та видалити менший з них. Після видалення числа, які були зліва та справа від видаленого, вважаються сусідніми.
Марічці цікаво, чи можливо зробити таку послідовність операцій, щоб залишилося лише одне число.
Input
У першому рядку задано ціле число \(n\) — кількість елементів масиву.
У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.
Output
Виведіть TAK, якщо Марічка може залишити одне число, або
NI в іншому випадку.
Constraints
\(1 \le n \le 2 \cdot 10^5\),
\(0 \le a_i \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 6 4 5 7 | TAK |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4 6 5 7 | NI |
Notes
У першому прикладі спершу можна взяти сусідні числа 4 та 5 і видалити число 4. Тоді послідовність стане рівною \((6, 5, 7)\). Далі Марічка вибирає сусідні числа 6 та 5 і видаляємо 5. Після такої операції послідовність буде \((6, 7)\). Насамкінець Марічка бере сусідні числа 6 та 7 і видаляємо 7. Послідовність стане рівною \((7)\). Вона складається одного елементу, що нам і було потрібно.
У другому прикладі дістати послідовність з одного елемента неможливо.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|