În Ţara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputaţi cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcţie de doctrina fiecăruia. Oricare doi deputaţi ale căror doctrine corespund unor numere consecutive fac parte din acelaşi partid. Prin urmare, partidele vor fi alcătuite din deputaţi ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputaţi, cu doctrinele 1,2,3,5 şi 6, atunci înseamnă că aceştia sunt grupaţi în două partide: unul format din 1,2 şi 3 şi altul din 5 şi 6.)
Un guvern trebuie să beneficieze de susţinerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputaţi, atunci un guvern are nevoie de susţinerea a cel puţin 4 deputaţi.
Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este următoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeaşi coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1,2,4,5,7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5.
Cerinţă
Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară.
Date de intrare
Pe prima linie a fişierului de intrare politic.in se află un număr natural nenul N, reprezentând numărul de deputaţi din parlament.
Pe a doua linie se află N numere naturale nenule separate prin câte un spaţiu, ordonate strict crescător, reprezentând doctrinele parlamentarilor.
Date de ieşire
Prima linie a fişierului de ieşire politic.out va conţine un număr natural nenul X, reprezentând numărul de partide din parlament, iar a doua linie va conţine un alt număr natural nenul Y, care reprezintă numărul de coaliţii majoritare care se pot forma.
Restricţii
0 < N ≤ 20000
numerele din şir sunt mai mici sau egale cu 30000
pentru determinarea corectă a numărului de partide parlamentare se acordă 30% din punctaj, iar pentru afişarea corectă a numărului de variante de coaliţie majoritară se acordă 70% din punctaj
Exemple
politic.in
politic.out
Explicaţii
10
1 2 3 5 6 8 10 11 14 15
5
4
Partidele parlamentare sunt: P1=(1,2,3), P2=(5,6), P3=(8), P4=(10,11) şi P5=(14,15).
Variantele de coaliţie majoritară sunt :
P1+P2+P3, P1+P2+P3+P4, P2+P3+P4, P2+P3+P4+P5.