Problema Joker

Alice a primit de Crăciun un joc prin intermediul căruia să exerseze noțiuni elementare de matematică, parcurse în anul școlar anterior. Jocul conține n cartonașe pe care sunt înscripționate numere naturale distincte.

Un cartonaș primește rolul de joker dacă are următoarele proprietăți: valorile cartonașelor de imediat la stânga lui (cel puțin unul) împreună cu valoarea sa formează un șir strict crescător și valoarea sa împreună cu valorile cartonașelor de imediat la dreapta lui (cel puțin unul) formează un șir strict descrescător. Toate aceste elemente constituie o secvență joker. Astfel, dacă x1, x2, …, xn sunt valorile înscripționate pe cartonașe și xi < xi+1 < ... < xk-1 < xk > xk+1 > ... > xj (1≤i<k<j≤n), atunci xi, xi+1, …, xk-1, xk, xk+1, …, xj se va numi secvență joker, iar xk va fi valoarea de pe cartonașul de tip joker. Două secvențe joker au maxim un element comun. Spre exemplu, şirul cartonașelor cu valorile 23 44 76 99 100 nu conţine nicio secvenţă joker, iar cel format cu valorile 2 5 8 3 1 4 7 0 conţine 2 secvenţe joker: 2 5 8 3 1 şi 1 4 7 0, cu jokerii 8, respectiv 7.

Jocul introduce o nouă noțiune și anume cifra de control a unui număr. Aceasta se obține efectuând suma cifrelor sale, apoi suma cifrelor acestei sume, până când suma obținută este un număr format dintr-o singură cifră. Această ultimă cifră poartă numele de cifră de control.

Cerință

Mama așează cele n cartonașe într-o anumită ordine și îi solicită lui Alice să determine:

1. Câte secvențe de tip joker există
2. Care sunt cele mai mari două valori distincte care au cifra de control pară și care se află pe cartonașe joker
3. Care sunt cartonașele care rămân dacă: se elimină toate cartonașele de tip joker, după care pe șirul de cartonașe nou obținut se procedează în aceeași manieră, procesul repetându-se până când nu mai rămâne niciun cartonaș joker.

Date de intrare

Fișierul de intrare joker.in conține pe prima linie un număr natural C, care poate fi 1, 2 sau 3. A doua linie conține numărul natural N ce reprezintă numărul de cartonașe, iar pe a treia linie se află N numere naturale distincte, separate prin câte un spațiu, reprezentând numerele înscripționate pe cartonașe, așa cum le-a așezat mama lui Alice.

Date de ieșire

Dacă valoarea lui C este 1, atunci se va rezolva numai punctul 1 din cerință. În acest caz, fișierul de ieșire joker.out va conține pe prima linie un singur număr natural reprezentând numărul de secvențe joker.

Dacă valoarea lui C este 2, atunci se va rezolva numai punctul 2 din cerință. În acest caz, fișierul de ieșire joker.out va conține pe prima linie două numere naturale distincte, în ordine crescătoare, separate prin spațiu, reprezentând cele mai mari două valori care se găsesc pe cartonașe de tip joker și care au cifra de control pară sau valoarea -1 dacă nu există două astfel de valori.

Dacă valoarea lui C este 3, atunci se va rezolva numai punctul 3 din cerință. În acest caz, fișierul de ieșire joker.out va conține pe prima linie, separate printr-un spațiu, valorile de pe cartonașele care rămân în urma procesului de eliminări succesive, așa cum este acesta descris în enunț.

Restricții și precizări

• C poate fi 1, 2 sau 3
• Pentru C=1 și C=2: 1 ≤ N ≤ 106, iar numerele de pe cartonașe vor fi numere naturale distincte < 109
• Pentru C=3: 1 ≤ N ≤ 100, iar numerele de pe cartonașe vor fi numere naturale distincte < 109
• Rezolvarea cerinței 1 garantează 30 de puncte, a cerinței 2 – 30 de puncte, respectiv a cerinței 3 – 40 de puncte

Exemple