Magie

Time limit: 1s Memory limit: 256MB Input: magie.in Output: magie.out

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

Cerință

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

Un șir de numere a1,a2,,ana_1,a_2,\ldots,a_n este stabil dacă:

  • n<3n < 3; sau
  • aia_i, aja_j și aka_k pot fi lungimile laturilor unui triunghi, pentru orice 1i<j<kn1 \le i < j < k \le n.

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

Se dă un șir a1,a2,,ana_1,a_2,\ldots,a_n. Verificați dacă toate subsecvențele șirului aa sunt stabile.

Date de intrare

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

Pe a doua linie se vor afla nn numere a1,a2,,ana_1,a_2,\ldots,a_n - elementele șirului aa.

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

  • 1n21051 \le n \le 2 \cdot 10^5;
  • 1ai1091 \le a_i \le 10^9;
  • Pentru 3030 de puncte, n50n \le 50;
  • Pentru încă 1010 puncte, n100n \le 100;
  • Pentru încă 1010 puncte, n500n \le 500;
  • Pentru încă 2020 puncte, n5 000n \le 5 \ 000;
  • Pentru restul de 3030 puncte, nu se impun restricții suplimentare.

Exemplul 1

magie.in

3
2 3 4

magie.out

DA

Explicație

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

Subsecvența [2,3,4][2,3,4] este stabilă deoarece 2+3>42+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][3,1,4,2] nu este stabilă deoarece 11, 44 și 22 nu pot fi lungimile laturilor unui triunghi (1+241+2 \le 4).

Log in or sign up to be able to send submissions!