maxpal

Şirul cu $n$ elemente $x_1, x_2, \dots, x_n$ se numeşte palindrom dacă este identic cu şirul $x_n, x_{n-1}, \dots, x_1$. Se defineşte subşir al şirului $x$ o submulţime a elementelor şirului $x$ aflate nu neapărat pe poziţii succesive, în care poziţiile relative dintre două elemente se păstrează: $x_{i_1}, x_{i_2}, \dots, x_{i_k}$, cu $1 \leq i_1 < i_2 < \dots < i_k \leq n$. Vom numi $i_1, i_2, \dots, i_k$ şirul indicilor. Două subşiruri se consideră distincte dacă cele două şiruri de indici corespunzătoare celor două subşiruri diferă prin cel puţin un element. De exemplu pentru şirul $x = (1, 3, 5, 6, 3, 5, 1)$ subşirul $(1, 3, 5)$ poate fi corespondentul a trei subşiruri distincte $(x_1, x_2, x_3)$, $(x_1, x_2, x_6)$, $(x_1, x_5, x_6)$, dar nu poate fi corespondentul subşirului $(x_1, x_5, x_3)$, pentru că în acest caz s-a inversat poziţia relativă a elementelor $x_3$ şi $x_5$. Subşirul $(x_1, x_2, x_3, x_5, x_7)$ = $(1, 3, 5, 3, 1)$ este un subşir palindrom.

Cerinţă

Cunoscând elementele unui şir, să se calculeze lungimea maximă a unui subşir palindrom şi numărul de subşiruri distincte de lungime maximă.

Date de intrare

Fişierul de intrare maxpal.in conţine două linii. Pe prima linie se află un număr natural reprezentând valoarea lui $n$, iar pe linia următoare cele $n$ elemente ale şirului $x$, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire maxpal.out va conţine pe o singură linie două numere naturale separate printr-un spaţiu; prima va reprezenta lungimea maximă a unui subşir palindrom iar a doua restul împărţirii numărului de subşiruri palindrom distincte de lungime maximă la numărul $666 \ 013$.

Restricții și precizări

• $3 \leq n \leq 2 \ 000$
• $0 \leq x_i \leq 255$
• Pentru răspuns corect la prima cerinţă se acordă $30\%$ din punctaj, iar pentru a doua $70\%$

Exemplul 1

maxpal.in

5
2 1 4 2 2

maxpal.out

3 5

Explicație

Cel mai lung subşir palindrom are lungimea $3$. Avem $5$ soluţii distincte:

$(x_1, x_2, x_4) = (2, 1, 2)$
$(x_1, x_2, x_5) = (2, 1, 2)$
$(x_1, x_3, x_4) = (2, 4, 2)$
$(x_1, x_3, x_5) = (2, 4, 2)$
$(x_1, x_4, x_5) = (2, 2, 2)$