Fişierul intrare/ieşire:	psir.in, psir.out	Sursă	preONI 2007 Runda Finala
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	0.175 sec	Limită de memorie	24576 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

P-sir

Un sir de numere naturale a₁, a₂, ..., a_k (k ≥ 2) se numeste p-sir daca se respecta conditia (a_i-a_i-1)*(a_i-a_i-2) < 0 pentru 2 < i ≤ k. Un subsir al unui sir care indeplineste conditia de p-sir se numeste p-subsir. Dandu-se un sir de N numere naturale P₁, P₂,... P_N sa se determine cate p-subsiruri contine.

Date de intrare

Pe prima linie din fisierul de intrare psir.in se va afla numarul natural N. Pe urmatoarea linie vor fi scrise N numere naturale reprezentand elementele P₁, P₂,... P_N.

Date de iesire

In fisierul de iesire psir.out se va scrie numarul de p-subsiruri, modulo 2³².

Restrictii

• 1 ≤ N ≤ 2.000
• 1 ≤ P_i ≤ 2.000.000.000

Exemplu

Explicatie

Cele 8 p-subsiruri sunt:
(P₁, P₂) = (1, 1)
(P₁, P₃) = (1, 5)
(P₁, P₄) = (1, 2)
(P₁, P₃, P₄) = (1, 5, 2)
(P₂, P₃) = (1, 5)
(P₂, P₄) = (1, 2)
(P₂, P₃, P₄) = (1, 5, 2)
(P₃, P₄) = (5, 2)

Cum se trimit solutii?