palind2

Palind2

Ana a descoperit ca are o adevarata pasiune pentru palindroame. Un sir de numere este palindrom daca se citeste la fel de la stanga la dreapta si de la dreapta la stanga (primul numar este egal cu ultimul, al doilea cu penultimul etc). Ea are un sir cu $N$ numere naturale si vrea ca orice subsecventa de lungime impara a sirului sa fie palindrom. Pentru a-si indeplini dorinta ea poate efectua asupra sirului mai multe operatii. O operatie consta in alegerea unui element din sir si incrementarea sau decrementarea lui cu o unitate. Bineinteles, Ana doreste sa utilizeze un numar minim de operatii pentru ca sirul obtinut sa respecte proprietatea amintita mai sus (orice subsecventa de lungime impara sa fie palindrom).

 
h2.Cerinta

h2. Cerinta

Determinati pentru Ana numarul minim de operatii pe care trebuie sa-l efectueze pentru ca orice subsecventa de lungime impara a sirului obtinut in urma efectuarii operatiilor sa fie palindrom. De asemenea aflati si numarul de siruri finale distincte pe care le poate obtine efectuand acest numar minim de operatii.
h2. Date de intrare

Fisierul de intrare $palind.in$ va contine pe prima linie numarul $T$, reprezentand numarul de seturi de date de intrare care urmeaza. In continuare urmeaza seturile de date de intrare, fiecare pe cate doua linii. Pe prima linie a unui set de date se afla numarul $N$, avand semnificatia din enunt. Pe urmatoarea linie se afla elementele sirului initial, separate prin cate un spatiu.

Fisierul de intrare $palind2.in$ va contine pe prima linie numarul $T$, reprezentand numarul de seturi de date de intrare care urmeaza. In continuare urmeaza seturile de date de intrare, fiecare pe cate doua linii. Pe prima linie a unui set de date se afla numarul $N$, avand semnificatia din enunt. Pe urmatoarea linie se afla elementele sirului initial, separate prin cate un spatiu.

h2. Date de iesire

Fisierul de iesire $palind.out$ va contine $T$ linii, pe linia $i$ aflandu-se doua numere, reprezentand raspunsul pentru al $i$-lea set de date de intrare. Primul numar este numarul minim de operatii, iar al doilea numarul de siruri distincte finale care se pot obtine efectuand numarul minim de operatii.

Fisierul de iesire $palind2.out$ va contine $T$ linii, pe linia $i$ aflandu-se doua numere, reprezentand raspunsul pentru al $i$-lea set de date de intrare. Primul numar este numarul minim de operatii, iar al doilea numarul de siruri distincte finale care se pot obtine efectuand numarul minim de operatii.

h2. Restrictii

* $1 ≤ N ≤ 10.000$;
* Elementele sirului sunt numere naturale din intervalul $[1, 7.000]$;
* Subsecventa a unui sir este un subsir de numere care apar pe pozitii consecutive;

* Toate testele folosite la corectare vor avea T = 20;
* Pentru 20% din teste $1 ≤ N ≤ 100$;
* Pentru 20% din teste valoarea maxima din oricare sir este cel mult $500$ si $101 ≤ N$.

* Toate testele folosite la corectare vor avea $T = 20$;
* Pentru $20%$ din teste $1 ≤ N ≤ 100$;
* Pentru $20%$ din teste valoarea maxima din oricare sir este cel mult $500$ si $101 ≤ N$.

h2. Exemplu
table(example). |_. palind2.in |_. palind2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
3
1 2 3
1
3
| 2 3
0 1

|
h3. Explicatie

...

Pentru primul test, cele trei siruri posibile sunt: 1 2 1, 2 2 2 si 3 2 3. Pentru al doilea test, singurul sir posibil este format din elementul 3.

== include(page="template/taskfooter" task_id="palind2") ==

3068