P-sir

psir

== include(page="template/taskheader" task_id="psir") ==

Un sir de numere naturale $a{~1~}, a{~2~}, ..., a{~k~} (k &ge; 2)$ se numeste _p-sir_ daca se respecta conditia $(a{~i~}-a{~i-1~})*(a{~i~}-a{~i-2~}) < 0$ pentru $2 < i &le; 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{~1~}, P{~2~},... P{~N~}$ sa se determine cate _p-subsiruri_ contine.

Un sir de numere naturale $a{~1~}, a{~2~}, ..., a{~k~}$ se numeste p-sir daca se respecta conditia $(a{~i~}-a{~i-1~})*(a{~i~}-a{~i-2~}) < 0$ pentru $2 < i &le; k$.

h2. 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{~1~}, P{~2~},... P{~N~}$.

...

h2. Date de iesire

In fisierul de iesire $psir.out$ se va scrie numarul de _p-subsiruri_, modulo $2^32^$.

...

h2. Restrictii

* $1 ≤ N ≤ 2.000$
* $1 ≤ P{~i~} ≤ 2.000.000.000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. psir.in |_. psir.out |

| 4
1 1 5 2
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Cele $8$ p-subsiruri sunt:
$(P{~1~}, P{~2~}) = (1, 1)$
$(P{~1~}, P{~3~}) = (1, 5)$
$(P{~1~}, P{~4~}) = (1, 2)$
$(P{~1~}, P{~3~}, P{~4~}) = (1, 5, 2)$
$(P{~2~}, P{~3~}) = (1, 5)$
$(P{~2~}, P{~4~}) = (1, 2)$
$(P{~2~}, P{~3~}, P{~4~}) = (1, 5, 2)$
$(P{~3~}, P{~4~}) = (5, 2)$

...

== include(page="template/taskfooter" task_id="psir") ==

1956