Spunem că o secvență de numere (a[i], a[i + 1], ..., a[j]) este esm dacă:

• are cel puțin 3 elemente
• există cel puțin o pereche de numere (a[x], a[y]) în acea secvență, cu i ≤ x < y < j, astfel încât a[x] * a[y] = a[j]

De exemplu, secvența (54, 7, 22, 6, 9, 42) este esm deoarece 7 * 6 = 42.

Cerința

Se dă un șir a[1], a[2], ..., a[n] de numere naturale. Să se determine:

• Numărul de secvențe esm din șir de lungime 3.
• Numărul de secvențe esm din șir care se termină cu elementul de la ultima poziție, a[n].
• Numărul de secvențe esm din șir.

Date de intrare

Fișierul de intrare esm.in conține pe prima linie un număr natural C, pe a doua linie numărul natural n, iar pe a treia linie, separate prin câte un spațiu, elementele șirului a[1], a[2], ..., a[n].

Date de ieșire

Fișierul de ieșire esm.out va conține un singur număr natural X:

• Dacă C = 1, atunci X va fi numărul de secvențe esm din șir de lungime 3.
• Dacă C = 2, atunci X va fi numărul de secvențe esm din șir care se termină cu a[n].
• Dacă C = 3, atunci X va fi numărul de secvențe esm din șir.

Restricții și precizări

• C ∊ {1,2,3}
• 1 ≤ n ≤ 100.000
• 1 ≤ a[i] ≤ 100.000, pentru orice i ∊ {1, 2, ..., n}
• Lungimea unei secvențe este egală cu numărul de elemente din secvență.
• Pentru 30 de puncte, C = 1
• Pentru 30 de puncte, C = 2
• Pentru 40 de puncte, C = 3

Exemplul 1:

esm.in

1
82
3 6 18 1 18 3 5

esm.out

3

Explicație

Secvențele esm din șir de lungime 3 sunt: (2, 3, 6), (3, 6, 18) și (18, 1, 18).

Exemplul 2:

esm.in

2
8
5 8 20 2 4 7 5 40

esm.out

3

Explicație

Secvențele esm din șir care se termină cu 40 sunt:
(5, 8, 20, 2, 4, 7, 5, 40);
(8, 20, 2, 4, 7, 5, 40);
(20, 2, 4, 7, 5, 40).

Exemplul 3:

esm.in

3
8
2 2 4 8 1 8 16 7

esm.out

9

Explicație

Secvențele esm din șir sunt:
(2, 2, 4)
(2, 2, 4, 8)
(2, 4, 8)
(2, 2, 4, 8, 1, 8)
(2, 4, 8, 1, 8)
(4, 8, 1, 8)
(8, 1, 8)
(2, 2, 4, 8, 1, 8, 16)
(2, 4, 8, 1, 8, 16).