papusa

Păpuşa Matrioşka este o jucărie din lemn, goală pe dinăuntru. De aceea, în interiorul său poate fi introdusă oricare altă păpuşă Matrioşka de înălţime mai mică.
La un magazin de suveniruri se găsesc $n$ păpuşi Matrioşka aşezate în şir, în număr egal, pe două rafturi alăturate. Pe raftul din stânga sunt expuse prima jumătate de păpuşi, situate în şir pe poziţiile $1$, $2$, $\dots$, $\frac{n}{2}$, iar raftul din dreapta ultima jumătate de păpuşi, situate în şir pe poziţiile $\frac{n}{2}+1$, $\dots$, $n$. Prin notaţia $\frac{n}{2}$ se înţelege jumătatea numărului $n$.
Ana şi Iulia vor să cumpere cât mai multe păpuşi Matrioşka, dar tatăl lor le impune următoarele reguli:

• Iulia are voie să aleagă păpuşi din raftul din stânga, iar Ana din raftul din dreapta
• Dacă de pe un raft se cumpără mai multe păpuşi, atunci ele se vor afla pe poziţii consecutive pe raft;
• Prima păpuşă cumpărată de o fetiţă va avea înălţimea mai mică decât cea de a doua, a doua decât cea de a treia şi aşa mai departe astfel încât fiecare păpuşă să poate fi introdusă în următoarea păpuşă cumpărată;
• Ultimele păpuşi cumpărate trebuie să se situeze doar la capetele rafturilor şi în plus:
  1. dacă ultima păpuşă cumpărată de Iulia este pe poziţia $1$ atunci ultima păpuşă cumpărată de Ana trebuie să fie pe poziţia $n$;
  2. dacă ultima păpuşă cumpărată de Iulia este pe poziţia $\frac{n}{2}$ atunci ultima păpuşă cumpărată de Ana trebuie să fie pe poziţia $\frac{n}{2}+1$

Pentru a putea să aleagă cât mai multe păpuşi respectând regulile impuse de tatăl lor, fetiţelor li se permite să execute în acelaşi timp următoarea operaţie, până se revine la aşezarea iniţială a păpuşilor:

• Iulia mută păpuşa de pe poziţia $1$ pe poziţia $\frac{n}{2}$, deplasând cu o poziţie spre stânga toate celelalte păpuşi din raftul său;
• Ana mută păpuşa de pe poziţia $n$ pe poziţia $\frac{n}{2}+1$, deplasând cu o poziţie spre dreapta toate celelalte păpuşi din raftul său;

Cerinţă

Pentru a le ajuta pe Iulia şi Ana să achiziţioneze $împreună$ un număr maxim de păpuşi, scrieţi un program care citeşte un număr natural $n$ şi înălţimile celor $n$ păpuşi şi determină:

1. numărul $M$ de operaţii efectuate concomitent de fetiţe;
2. numărul maxim $P$ de păpuşi care vor fi cumpărate.

Date de intrare

Fişierul text papusa.in conţine pe prima linie un număr natural par $n$, reprezentând numărul de păpuşi. Pe linia a doua sunt $n$ numere naturale separate prin câte un spaţiu, reprezentând înălţimile păpuşilor situate pe cele două rafturi, în ordine de la poziţia $1$ la $n$.

Date de ieşire

Fişierul de ieşire papusa.out va conţine:

• pe prima linie, numărul natural $M$;
• pe a doua linie, numărul natural $P$.

Restricţii şi precizări

• $2 \leq n \leq 1 \ 000$, $n$ este număr par
• $1 \leq$ înălţimile păpuşilor $\leq 10 \ 000$
• Dacă numărul maxim de păpuşi se obţine fără a face operaţii de mutare atunci $M = 0$
• Pentru toate testele de intrare există o singură configuraţie pentru care se poate cumpăra un număr maxim de păpuşi
• Pentru rezolvarea cerinţei $1$ se acordă $40\%$ din punctaj, pentru rezolvarea cerinţei $2$, $60\%$ din punctaj

Exemplu

papusa.in

8
5 7 2 4 6 10 14 8

papusa.out

2
7

Explicaţie

Raftul Iuliei conţine păpuşile de înălţimi $5$, $7$, $2$, $4$, iar al Anei păpuşile de înălţimi $6$, $10$, $14$, $8$. Pe această aşezare Iulia şi Ana pot cumpăra păpuşile de înălţime $2 \ 4 \ 6$ sau $5 \ 8$. Se pot cumpăra cel mult $3$ păpuşi.
Configuraţia obţinută după prima operaţie de mutare este: $7 \ 2 \ 4 \ 5 \ 8 \ 6 \ 10 \ 14$ Pe această aşezare Iulia şi Ana pot cumpăra păpuşile de înălţime $2 \ 4 \ 5 \ 6 \ 8$ sau $2 \ 7 \ 6 \ 10 \ 14$. Se pot cumpăra cel mult $5$ păpuşi.
Configuraţia obţinută după a doua operaţie este $2 \ 4 \ 5 \ 7 \ 14 \ 8 \ 6 \ 10$. Pe această aşezare Iulia şi Ana pot cumpăra păpuşile cu înălţimile $2 \ 4 \ 5 \ 7 \ 6 \ 8 \ 14$ sau $2 \ 6 \ 10$. Deci se pot cumpăra cel mult $7$ păpuşi.
Configuraţia obţinută după a treia operaţie $4 \ 5 \ 7 \ 2 \ 10 \ 14 \ 8 \ 6$. Pe această aşezare Iulia şi Ana pot cumpăra păpuşile cu înălţimile $2 \ 10$ sau $4 \ 6$. Deci se pot cumpăra cel mult $2$ păpuşi.
Numărul maxim de păpuşi cumpărate este $7$ şi se obţine după a $2$-a operaţie de mutare.