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,…[n/2], iar raftul din dreapta ultima jumătate de păpuşi, situate în şir pe poziţiile [n/2]+1,…n. Prin notaţia [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:
- 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;
- dacă ultima păpuşă cumpărată de Iulia este pe poziţia [n/2] atunci ultima păpuşă cumpărată de Ana trebuie să fie pe poziţia [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 [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 [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ă:
a) numărul M de operaţii efectuate concomitent de fetiţe;
b) 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, iar pe a doua linie, numărul natural P.
Restricţii
• 2 ≤ n ≤ 1000, n este număr par
• 1 ≤ înălţimile păpuşilor ≤ 10000
• 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
Exemple
papusa.in
papusa.out
Explicaţii
8
5 7 2 4 6 10 14 8
2
7
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 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 doua operaţie de mutare.
