Zerouri

La final de semestru, profesorul Morf, cunoscut pentru strictețea și perfecționismul său, s-a trezit într-o situație delicată: toți elevii din clasa a VIII-a aveau punctaje cam prea mari în catalog și directorul tocmai anunțase o verificare a mediilor, iar Morf știa că o clasă plină de punctaje atât de mari ar ridica semne de întrebare.

Dar acesta nu putea fi evident, deoarece dacă ar fi scăzut punctajele prea rapid elevii ar fi observat imediat. Așa că profesorul a găsit o metodă mai discretă.

În fiecare seară, după ce școala se golea, el deschidea catalogul și alegea grupuri de elevi așezați unii lângă alții și le micșora notele tuturor din acel grup cu un punct. Făcea asta atent, având grijă ca niciun punctaj să nu scadă sub zero.

Și astfel, între filele prăfuite ale catalogului, s-a născut una dintre cele mai ciudate și elegante dileme: cum să micșorezi punctajele elevilor cât mai repede, fără ca nimeni să-și dea seama.

Cerință

Se dă un vector $A$ de numere naturale. O operație constă în alegerea unui interval $\left[st, dr\right]$ cu $1\leq st \leq dr \leq N$ și scăderea cu $1$ a fiecărui element din acel interval. Operația este permisă numai dacă, în momentul aplicării, toate elementele din intervalul respectiv sunt mai mari sau egale cu $1$.

Transformați vectorul $A$ într-un vector nul (care are toate elementele nule), folosind un număr minim de operații. În funcție de cerință:

• $C=1$ afișați doar numărul minim de operații;
• $C=2$ afișați numărul minim de operații și operațiile în ordinea aplicării lor.

Date de intrare

Fișierul de intrare zerouri.in conține:

• pe prima linie două numere naturale nenule, $C$ și $N$, cu semnificația din enunț;
• pe următoarea linie $N$ numere naturale, reprezentând elementele vectorului $A$.

Date de ieșire

Pe prima linie a fișierului de ieșire zerouri.out se va afișa un singur număr $K$, reprezentând numărul minim de operații. Dacă $C=2$, pe următoarele $K$ linii, vor fi, în ordinea aplicării lor, operațiile, reprezentate prin valorile $st$ și $dr$ separate printr-un spațiu.

Restricții și precizări

Pentru $C=1$:

• $1\leq N\leq 1 \ 000 \ 000$;
• $0\leq A[i]\leq 1 \ 000 \ 000 \ 000$, $1\leq i\leq N$.

Pentru $C=2$:

• $1\leq N\leq 50 \ 000$;
• $0\leq A[i]\leq 200$, $1\leq i\leq N$.

Exemplul 1

zerouri.in

1
6
2 0 1 1 0 2

zerouri.out

5

Explicație

Se pot alege intervalele $(1,1), (1,1), (3,4), (6,6), (6,6)$. Se poate demonstra că această soluție este optimă.

Exemplul 2

zerouri.in

2
6
2 0 1 1 0 2

zerouri.out

5
1 1
1 1
3 4
6 6
6 6