Problem 2076: 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.

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$ .

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

magie.in

3
2 3 4

magie.out

DA

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$ .

magie.in

4
5 3 4 3

magie.out

DA

magie.in

7
3 3 1 4 2 5 4

magie.out

NU

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$ ).