Dla dowolnego ciągu liczbowego mówimy, że jest on „usuwalny”, jeśli można go sprowadzić do ciągu pustego poprzez skończoną liczbę operacji usuwania. Pojedyncza operacja usuwania jest zdefiniowana następująco:
- Niech $k$ będzie aktualną długością ciągu. Usuwamy z ciągu wszystkie liczby równe $k$.
Dany jest ciąg $a$ o długości $n$ oraz $m$ operacji modyfikacji. Po każdej $i$-tej modyfikacji należy odpowiedzieć na pytanie: ile co najmniej liczb należy jeszcze zmodyfikować w ciągu $a$, aby stał się on usuwalny?
Każda operacja modyfikacji polega na zmianie wartości pojedynczego elementu, zwiększeniu wszystkich elementów ciągu o jeden lub zmniejszeniu wszystkich elementów ciągu o jeden.
Wejście
Pierwsza linia zawiera dwie dodatnie liczby całkowite $n$ oraz $m$, oznaczające odpowiednio długość ciągu oraz liczbę operacji modyfikacji.
Druga linia zawiera $n$ dodatnich liczb całkowitych, oznaczających ciąg $a$, gdzie $i$-ta liczba to $a_i$.
Następnie $m$ linii, z których każda zawiera dwie liczby całkowite $p$ oraz $x$, opisujące operację modyfikacji.
Jeśli $1\le p \le n$, operacja polega na zmianie wartości $p$-tego elementu ciągu $a_p$ na $x$.
Jeśli $p=0$, operacja polega na zwiększeniu wszystkich elementów ciągu o $x$.
Wyjście
Wypisz $m$ linii, każda zawierająca jedną liczbę całkowitą. $i$-ta linia powinna zawierać odpowiedź po wykonaniu $i$-tej operacji modyfikacji.
Przykład
Przykład 1
3 9 1 2 3 1 1 0 1 0 1 0 1 2 2 3 2 0 -1 0 -1 0 -1
Wyjście 1
0 1 2 3 2 1 1 2 2
Uwagi
Po pierwszej modyfikacji ciąg wynosi $(1, 2, 3)$ i jest usuwalny bez żadnych zmian.
Po czwartej modyfikacji ciąg wynosi $(4, 5, 6)$. Aby stał się usuwalny, należy zmienić wszystkie trzy liczby.
Po szóstej modyfikacji ciąg wynosi $(4, 2, 2)$. Zmiana pierwszej liczby na $3$ sprawia, że ciąg staje się usuwalny.
Po dziewiątej modyfikacji ciąg wynosi $(1, -1, -1)$. Można zmienić drugą liczbę na $2$ oraz trzecią na $3$, aby ciąg stał się usuwalny.
Podzadania
| Subtask # | Punkty | $n\le$ | $m\le$ | Czy spełnia $p>0$ |
|---|---|---|---|---|
| $1$ | $7$ | $5$ | $10$ | Nie |
| $2$ | $14$ | $300$ | $1$ | Tak |
| $3$ | $15$ | $3000$ | $1$ | Tak |
| $4$ | $11$ | $3000$ | $3000$ | Tak |
| $5$ | $13$ | $10^5$ | $10^5$ | Tak |
| $6$ | $32$ | $10^5$ | $10^5$ | Nie |
| $7$ | $8$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | Nie |
Dla $100\%$ danych:
- $1\le n,m \le 1.5 \times 10^5$
- $1\le a_i \le n$
- $0\le p\le n$
- Gdy $p>0$, $1\le x \le n$.
- Gdy $p=0$, $x=-1$ lub $1$.