Moisil++ 2023 Clasa a 9a Mirror | Magie

Deoarece geometria nu este în materia de OJI, comisia vă propune următoarea problemă:

Cerință

Trei numere $a \le b \le c$ pot fi lungimile laturilor unui triunghi dacă și numai dacă $a+b>c$.

Un șir de numere $a_1,a_2,\ldots,a_n$ este stabil dacă:

• $n < 3$; sau
• $a_i$, $a_j$ și $a_k$ pot fi lungimile laturilor unui triunghi, pentru orice $1 \le i < j < k \le n$.

De exemplu: $[]$, $[1]$ și $[5,3,4,3]$ sunt stabile, pe când $[1,3,1]$ și $[3,3,1,4,2,5,4]$ nu sunt stabile.

Se dă un șir $a_1,a_2,\ldots,a_n$. Verificați dacă toate subsecvențele șirului $a$ sunt stabile.

Date de intrare

Pe prima linie a fișierului de intrare magie.in se va afla un singur număr $n$ - lungimea șirului $a$.

Pe a doua linie se vor afla $n$ numere $a_1,a_2,\ldots,a_n$ - elementele șirului $a$.

Date de ieșire

Fișierul de ieșire magie.out va conține DA, dacă toate subsecvențele șirului dat sunt stabile, respectiv NU, în caz contar.

Restricții și precizări

• $1 \le n \le 2 \cdot 10^5$;
• $1 \le a_i \le 10^9$;
• Pentru $30$ de puncte, $n \le 50$;
• Pentru încă $10$ puncte, $n \le 100$;
• Pentru încă $10$ puncte, $n \le 500$;
• Pentru încă $20$ puncte, $n \le 5 \ 000$;
• Pentru restul de $30$ puncte, nu se impun restricții suplimentare.

Exemplul 1

magie.in

3
2 3 4

magie.out

DA

Explicație

Subsecvențele $[2]$, $[3]$, $[4]$, $[2,3]$ și $[3,4]$ sunt stabile deoarece au mai puțin de $3$ elemente.

Subsecvența $[2,3,4]$ este stabilă deoarece $2+3 > 4$.

Exemplul 2

magie.in

4
5 3 4 3

magie.out

DA

Exemplul 3

magie.in

7
3 3 1 4 2 5 4

magie.out

NU

Explicație

Subecvența $[3,1,4,2]$ nu este stabilă deoarece $1$, $4$ și $2$ nu pot fi lungimile laturilor unui triunghi ($1+2 \le 4$).