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.

* $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") ==