Oglinditul unui număr natural x este numărul obținut prin parcurgerea cifrelor lui x de la dreapta la stânga, ignorându-se cifrele nule de pe ultimele poziții ale lui x. De exemplu, oglinditul lui 103 este 301, în timp ce oglinditul lui 2500 este 52. O pereche de numere naturale distincte x și y se numește pereche oglindită dacă atât x este oglinditul lui y, cât și y este oglinditul lui x. De exemplu, numerele x = 42 și y = 24 formează o pereche oglindită, însă numerele x = 1 și y = 100 nu formează o pereche oglindită.

Un număr natural x este considerat palindrom dacă x este egal cu oglinditul său. De exemplu, numărul 42124 este palindrom. Din două numere distincte se poate forma un număr nou prin alipirea unuia la dreapta celuilalt. De exemplu, din numerele 124 și 42 se pot obține numerele 12442 (din alipirea lui 42 la dreapta lui 124) și 42124 (din alipirea lui 124 la dreapta lui 42).

Cerința

Fie un șir de numere naturale a[1], a[2], ..., a[n]. Determinați:

1) Numărul perechilor de indici (i, j), cu 1 ≤ i < j ≤ n, având proprietatea că a[i] și a[j] formează o pereche oglindită.
2) Cel mai mare număr palindrom care se poate forma prin alipirea a două numere distincte din șir.

Date de intrare

Fișierul de intrare perechi.in conține pe prima linie un număr natural C, având valoarea 1 sau 2, reprezentând numărul cerinței. Pe a doua linie se află numărul natural n. A treia linie din fișier conține șirul de numere naturale a[1], a[2], ..., a[n], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire perechi.out va conține un singur număr, reprezentând rezultatul corespunzător pentru cerința dată.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ C ≤ 2
• 1 ≤ n ≤ 100.000
• 1 ≤ a[i] < 10.000
• Se garantează că pentru cerința 1 există în șirul dat cel puțin o pereche oglindită, iar la cerința 2 există în șirul dat cel puțin un număr palindrom.
• Pentru 27 de puncte, C = 1, n ≤ 10.000
• Pentru 23 de puncte, C = 1, 10.000 < n ≤ 100.000
• Pentru 27 de puncte, C = 2, n ≤ 10.000
• Pentru 23 de puncte, C = 2, 10.000 < n ≤ 100.000

Exemplul 1:

perechi.in

1
5
21 12 21 12 21

perechi.out

6

Explicație

Există 6 perechi de indici cu proprietatea că valorile corespunzătoare lor formează perechi oglindite: (1, 2), (1, 4), (2, 3), (2, 5), (3, 4) și (4, 5). Fiecare dintre aceste perechi oglindite este compusă din valorile 12 și 21.

Exemplul 2:

perechi.in

1
6
13 97 76 67 76 31

perechi.out

3

Explicație

Există 3 perechi de indici cu proprietatea că valorile corespunzătoare lor formează perechi oglindite: (1, 6), (3, 4) și (4, 5). Aceste perechi oglindite formate sunt: (13, 31), (76, 67), respectiv, (67, 76).

Exemplul 3:

perechi.in

26
24 79 42 97 123 124

perechi.out

42124

Explicație

Se pot forma următoarele numere palindrom: 2442, 4224, 7997, 9779 și 42124. Cel mai mare dintre acestea este 42124.