wind

Domnul Vânt a pus pe marginea unei șosele $N$ centrale eoliene, dintre care unele produc energie electrică, iar altele, deocamdată, doar consumă energie. El a etichetat centralele cu numerele naturale distincte de la $1$ la $N$, în ordinea poziționării lor pe șosea. Fiecare centrală eoliană are la bază un ecran pe care este afișat un număr întreg, reprezentând cantitatea de energie pe care o produce (dacă numărul este pozitiv) sau pe care o consumă (dacă numărul este negativ).

Pentru a construi corect $k$ orașe de-a lungul acestei șosele, un arhitect trebuie să aibă în vedere că:

• fiecărui oraș îi va fi atribuit câte un grup format din centrale eoliene vecine pe șosea, toate grupurile având același număr de centrale;
• cantitatea de energie repartizată unui oraș este egală cu suma numerelor afișate pe ecranele centralelor eoliene din grupul atribuit; uneori este posibil ca, deocamdată, suma obținută să fie negativă;
• fiecare dintre cele $N$ centrale eoliene trebuie să fie atribuită unui oraș;
• factorul de dezechilibru, notat cu $P(k)$, este valoarea maximă a diferenței dintre energiile repartizate oricăror două orașe diferite, dintre cele $k$.

Cerință

Scrieţi un program care citește numărul $N$, valorile afișate pe cele $N$ ecrane ale centralelor eoliene și rezolvă următoarele două cerinţe:

1. afișează numărul $M$ de moduri în care se pot grupa cele $N$ centrale pentru construcția corectă de orașe;
2. afișează numărul maxim $X$ de orașe ce pot fi construite corect, dintre cele care au factorul de dezechilibru minim, precum și eticheta $E$ a primei centrale eoliene atribuită orașului cu cea mai mare cantitate de energie repartizată, dintre cele $X$ orașe; dacă sunt mai multe astfel de orașe, se ia în considerare cel care are atribuite centrale etichetate cu numere mai mari.

Date de intrare

Fișierul de intrare wind.in conține pe prima linie un număr natural $C$ reprezentând cerința care trebuie rezolvată ($1$ sau $2$). A doua linie a fișierului conține un număr natural $N$, cu semnificația din enunț. A treia linie din fișier conține $N$ numere întregi, separate prin câte un spațiu, reprezentând valorile afișate pe cele $N$ ecrane ale centralelor eoliene, în ordinea poziționării acestora pe șosea.

Date de ieșire

Fişierul de ieșire wind.out va conţine pe prima linie:

• dacă $C=1$, numărul natural $M$, reprezentând răspunsul la cerința 1;
• dacă $C=2$, cele două numere naturale $X$ și $E$, în această ordine, separate printr-un singur spațiu, reprezentând răspunsul la cerința 2.

Restricţii și precizări

• $2 \leq N ≤ 100\ 000$, $N$ număr natural;
• Numerele afișate pe ecranele centralelor sunt numere întregi formate din cel mult 9 cifre;
• Se vor construi minimum 2 orașe;
• Pentru rezolvarea cerinței 1 se acordă 20 de puncte.
• Pentru rezolvarea cerinței 2 se acordă 70 de puncte. Pentru fiecare test al acestei cerințe veți primi $50\%$ din punctajul testului pentru valoarea corectă $X$ și $50\%$ din punctajul testului pentru valoarea corectă $E$. Această cerință necesită ca în fișierul de ieșire să existe exact 2 numere.

Exemplul 1

wind.in

1
12
2 4 -5 12 3 5 -6 4 5 7 -8 2

wind.out

5

Explicație

Cerinţa este 1.
Centralele eoliene se pot grupa câte 1, câte 2, câte 3, câte 4 sau câte 6.

Exemplul 2

wind.in

2
12
2 4 -5 12 3 5 -6 4 5 7 -8 2

wind.out

3 1

Explicație

Cerinţa este 2.
Posibilitățile de grupare:

• câte o centrală/oraș:
  • sumele sunt $2, 4, -5, \ldots, 2$;
  • $P(12) = 20 = 12-(-8)$;
• câte 2 centrale/oraș:
  • sumele sunt: $6, 7, 8, -2, 12, -6$;
  • $P(6) = 18 = 12-(-6)$;
• câte 3 centrale/oraș:
  • sumele sunt: $1, 20, 3, 1$;
  • $P(4) = 19 = 20-1$;
• câte 4 centrale/oraș:
  • sumele sunt: $13, 6, 6$;
  • $P(3) = 7 = 13-6$;
• câte 6 centrale/oraș:
  • sumele sunt: $21, 4$;
  • $P(2) = 17 = 21-4$.

Astfel, factorul de dezechilibru minim este $P(3) = 7$, deci $X=3$. Pentru această grupare a centralelor, orașul cu cantitatea maximă de energie ($13$) corespunde primului grup, care începe cu centrala etichetată cu $E=1$.