Se consideră N numere naturale nenule a1, a2, …, aN.

Cerința

Să se determine numărul de perechi de indici (i,j), 1 ≤ i, j ≤ N, i ≠ j , cu proprietatea că, dacă am alipi numărul aj la finalul numărului ai, obținem un număr divizibil cu 11. Perechile (i,j) și (j,i) se consideră diferite.

Date de intrare

Fişierul de intrare div11.in conţine pe prima linie numărul natural N. Pe următoarea linie se află cele N numere naturale nenule a1, a2, …, aN, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire div11.out va conţine o singură linie pe care va fi scris numărul de perechi cu proprietatea din enunţ.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• Numerele de pe a doua linie a fișierului de intrare sunt mai mici sau egale cu 1017. Vom nota numărul maxim de cifre pe care le poate avea un număr cu C.
• Pentru 12 puncte, N ≤ 1000, C ≤ 3
• Pentru 12 puncte, N ≤ 1000, C ≤ 8
• Pentru 16 puncte, N ≤ 1000, C ≤ 17
• Pentru 7 puncte, N ≤ 100.000, C = 1
• Pentru 17 puncte, N ≤ 100.000, C ≤ 3
• Pentru 36 puncte, N ≤ 100.000, C ≤ 17

Exemplul 1:

div11.in

7
1 2 1 3 3 1 2

div11.out

10

Explicație

Numerele divizibile cu 11 care se pot obține sunt: 11 (de 6 ori pentru perechile de indici (1,3), (1,6), (3,6), (3,1), (6,1) și (6,3)), 22 și 33.

Exemplul 2:

div11.in

5
14 120 32 8 3

div11.out

3

Explicație

Numerele divizibile cu 11 care se pot obține sunt: 143, 32120, 814.