== include(page="template/taskheader" task_id="maxpal") ==
Lui Termopanes îi place să se joace cu numere naturale foarte mari. Uneori sora lui îi oferă un număr nou şi în acest caz el îl adaugă în colecţia lui de numere. Alteori sora lui îl intreabă: **dacă ai pune numerele din colecţia ta în ordine crescătoare, care ar fi numărul de pe poziţia $k$ ?**
Şirul cu n elemente x{~1~}, x{~2~},..., x{~n~} se numeşte palindrom dacă este identic cu şirul x{~n~}, x{~n-1~},..., 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{~i1~}, x{~i2~},..., x{~ik~}, cu 1 ≤ i{~1~} < i{~2~} <...< i{~k~} ≤ $n$. Vom numi i{~1~},i{~2~},...,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.
h2. Cerinta
Cunoscând o succesiune de operaţii prin care sora lui Termopanes fie îi oferă acestuia un număr, fie îi pune o întrebare, răspundeţi în ordine la toate întrebările puse.
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ă.
h2. Date de intrare
Fişierul de intrare $nums.in$ va conţine pe prima linie numărul natural n reprezentând numărul de operaţii. Pe următoarele $N$ linii se vor afla cate $2$ numere $t$ şi $x$ separate printr-un spaţiu. Dacă $t$ este $1$ atunci elementul $x$ se adaugă în colecţia lui Termopanes, iar dacă $t$ este $0$, atunci lui Termopanes $i$ se adresează o întrebare.
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.
h2. Date de ieşire
Fişierul de ieşire $nums.out$ va conţine $L$ linii (câte o linie pentru fiecare operaţie de tipul $0$). Pe linia $i$ se va afişa răspunsul la a $i$-a întrebare.
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 **$666013$**.
h2. Restricţii
* $1$ ≤ $N$ ≤ $100000$
* $1$ ≤ $k$ ≤ numărul de elemente ale colecţiei la momentul întrebării
* Numărul de cifre al oricărui număr adăugat colecţiei nu va depaşi $100000$
* Dimensiunea fişierului de intrare nu va depaşi $6$ MB
* Dacă Termopanes primeşte un număr deja existent în colecţia sa, nu îl mai adaugă colecţiei.
* Niciun număr nu începe cu $0$
* $3$ ≤ $N$ ≤ $2000$
* $0$ ≤ $x${~i~} ≤ $255$
* Pentru răspuns corect la prima cerinţă se acordă $30$% din punctaj, iar pentru a doua $70$%
h2. Exemplu
table(example). |_. maxpal.in |_. maxpal.out |
| 7
1 1232
1 1002
1 212
0 2
1 213
1 123
0 3
| 1002
213
| 5
2 1 4 2 2
| 3 5
|
h3. Explicaţie
În momentul în care se pune prima întrebare, numerele din colecţie sunt: $212$ $1002$ $1232$, al $2$-lea fiind $1002$
Când se pune a doua întrebare, numerele sunt: $123$ $212$ $213$ $1002$ $1232$, al $3$-lea fiind $213$.
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$)
== include(page="template/taskfooter" task_id="maxpal") ==
