patru

„De aceea noi facem cunoscut tuturor domniilor voastre că pe la Boboteaza trecută sus-numitul turc a trimis asupra mea în țara noastră o mare armată în număr de o sută și douăzeci de mii de oameni [...] și auzind bine și văzând și noi, pentru apărare am luat spada în mână și cu ajutorul domnului Dumnezeu am mers asupra lor și i-am călcat în picioare și i-am trecut prin ascuțișul săbiei noastre.”
— din scrisoarea adresată principilor creștini de Ștefan cel Mare după victoria de la Vaslui din ianuarie 1475

Imediat după marea biruință de la Vaslui, Ștefan și-a pus oștenii să se așeze pe un rând lung și fiecăruia din ei i-a pus o pecete reprezentând vitejia pe care a arătat-o în luptă. Astfel voievodul a putut vedea rândul de oșteni prin șirul $v_1, v_2, \dots, v_n$ de vitejii, numere naturale nenule. Unii dintre ei au fost mai bravi, alții mai puțin, astfel că există oșteni care au arătat o vitejie de câteva ori mai mare decât a altora.

Cerință

Ștefan vrea să afle de câte ori se află în șir patru indici $i$, $j$, $k$, $p$ astfel încât $i \lt j \lt k \lt p$ și $v_i \cdot v_j \cdot v_k = v_p$

Date de intrare

Fişierul de intrare patru.in conține pe prima linie numărul natural $n$, iar pe următoarea linie, separate prin câte un spațiu, numerele $v_1, v_2, \dots, v_n$ reprezentând vitejiile oștenilor.

Date de ieșire

Fişierul de ieşire patru.out conține o singură linie pe care va fi scris un număr natural reprezentând valoarea cerută.

Restricții și precizări

• $4 \le n \le 10\ 000$
• $1 \le v_i \le 2^{31}-1$, pentru orice $1 \le i \le n$
• Atenție, nu puteți schimba ordinea oștenilor, doar voievodul are acest drept!

Exemplu

patru.in

6
1 2 3 1 6 2

patru.out

3

Explicație

Cele trei soluții de câte 4 indici sunt pe pozițiile:

• $1\ 2\ 3\ 5$ și $v_1 \cdot v_2 \cdot v_3 = v_5$;
• $2\ 3\ 4\ 5$ și $v_2 \cdot v_3 \cdot v_4 = v_5$;
• $1\ 2\ 4\ 6$ și $v_1 \cdot v_2 \cdot v_4 = v_6$.