Ana a descoperit că are o adevărată pasiune pentru palindroame. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie constă în alegerea unui element din şir şi incrementarea sau decrementarea lui cu o unitate. Bineînţeles, Ana doreşte să utilizeze un număr minim de operaţii pentru ca şirul obţinut să respecte proprietatea amintită mai sus (orice subsecvenţă de lungime impară să fie palindrom).
Cerinţă
Determinaţi pentru Ana numărul minim de operaţii pe care trebuie să-l efectueze pentru ca orice subsecvenţă de lungime impară a şirului obţinut în urma efectuării operaţiilor să fie palindrom. De asemenea aflaţi şi numărul de şiruri finale distincte pe care le poate obţine efectuând acest numar minim de operaţii.
Date de intrare
Fişierul de intrare palind.in va conţine pe prima linie numărul T, reprezentând numărul de seturi de date de intrare care urmează. În continuare urmează seturile de date de intrare, fiecare pe câte două linii. Pe prima linie a unui set de date se află numărul N, având semnificaţia din enunţ. Pe următoarea linie se află elementele şirului iniţial, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire palind.out va conţine T linii, pe linia i aflându-se două numere, reprezentând raspunsul pentru al i-lea set de date de intrare. Primul numar este numarul minim de operaţii, iar al doilea numărul de şiruri distincte finale care se pot obţine efectuând numărul minim de operaţii.
Restricţii
1 ≤ T ≤ 20 1 ≤ N ≤ 10.000
Elementele şirului sunt numere naturale din intervalul [1, 7.000].
Subsecvenţă a unui şir este un subşir de numere care apar pe poziţii consecutive.
Toate testele folosite la evaluare vor avea T = 20.
Pentru 20% din teste, 1 ≤ N ≤ 100
Pentru 20% din teste valoarea maximă din oricare şir este cel mult 500 şi N ≥ 101
Exemple
palind.in
palind.out
Explicaţii
1
3
1 2 3
2 3
Pentru singurul test, cele trei şiruri posibile sunt:
1 2 1, 2 2 2 si 3 2 3.