Bolivija

문제

Bolivija, predivna južnoamerička država s bogatom kulturom i povijesti, prepuna prirodnih ljepota, uključujući dio Amazonske prašume te planinski lanac Ande. Bitnije za naše natjecatelje, to je mjesto održavanja sljedeće Međunarodne informatičke olimpijade!

U sklopu promocije natjecanja, organizatori su dobili zadatak fotografirati planinski lanac te sastaviti album od najzapanjujućih slika. Planinski lanac predstavljamo nizom $vv$ od $NN$ nenegativnih cijelih brojeva koji predstavljaju redom visine planina u planinskom lancu. Pri tome, $NN$ je neparan i središnja planina (na poziciji $\frac{N+1}{2}\backslash frac\{N+1\}\{\; 2\}$) je upravo ona najviša, na čijem je samom vrhu ugasli vulkan Nevado Sajama.

Organizatori imaju vrlo specifične uvjete za prikupljanje fotografija. Prvo, biraju dva nenegativna cijela broja $AA$ i $BB$ tako da je te da je $BB$ manji ili jednak visini najvišeg vrha, Nevado Sajame. Zatim, namještaju kadar fotografije tako da širinom obuhvaća svih $NN$ planina, no tako da fotografija obuhvaća samo raspon visina između $AA$ i $BB$. Dodatno, organizatori su zadovoljni fotografijom samo ukoliko je ona simetrična s obzirom na os simetrije koja prolazi središnjom planinom.

[이미지 1]

Slika: Primjer valjanog izbora fotografije koji odgovara drugom probnom primjeru

Organizatore sada zanima koliko različitih fotografija mogu prikupiti, odnosno koliko postoji parova brojeva $AA$ i $BB$ koji zadovoljavaju željene uvjete. Razmišljajući predugo o odgovoru, burna tektonska aktivnost dovela je do promjene visina nekih planina. Ukupno se dogodilo $QQ$ promjena visina, a vaš je zadatak pomoći organizatorima odrediti traženi broj fotografija nakon svake od promjena. Pri tome, nijedna od promjena nije utjecala na visinu središnje planine i ona je u svakom trenutku bila najviša planina.

입력

U prvom su retku prirodni brojevi $NN$ i $QQ$, redom broj planina i broj promjena.

U drugom je retku niz $vv$ od $NN$ nenegativnih cijelih brojeva, redom visine planina u planinskom lancu. Garantirano je da je $NN$ neparan te da je središnja planina upravo ona najviša.

U $ii$-tom od sljedećih $QQ$ redaka su prirodan i nenegativan cijeli broj $x_{i}x\_i$ i $h_{i}h\_i$ (1 ≤ x_i ≤ N), koji označavaju da je došlo do promjene visine planine na poziciji $x_{i}x\_i$ koja poprima novu visinu $h_{i}h\_i$. Garantirano je da $x_i\mathrm{\ne }\frac{N+1}{2}x\_i\; \backslash ne\; \backslash frac\{N+1\}\{\; 2\}$ te da je nova visina manja ili jednaka visini središnje planine.

출력

Ispišite $Q+1Q\; +\; 1$ redaka. U $ii$-tom retku ispišite traženi mogući broj fotografija nakon i − 1 tektonskih promjena.

힌트

Pojašnjenje drugog probnog primjera:

Mogući izbori za $AA$ i $BB$ su: $(0,1),(2,3),(2,4),(3,4),(5,6),(5,7),(6,7)(0,\; 1),(2,\; 3),(2,\; 4),(3,\; 4),(5,\; 6),(5,\; 7),(6,\; 7)$. Ukupno ih je sedam.

Slika u tekstu odgovara odabiru $A=2A\; =\; 2$ i $B=4B\; =\; 4$.