임의의 수열에 대하여, 유한 번의 삭제 연산을 거쳐 수열을 빈 수열로 만들 수 있다면, 이 수열을 '삭제 가능'하다고 한다. 한 번의 삭제 연산은 다음과 같이 정의된다.

• 현재 수열의 길이를 $k$라고 할 때, 수열 내의 모든 $k$를 삭제한다.

길이가 $n$인 수열 $a$가 주어지며, $m$번의 수정 연산이 수행된다. 각 $i$번째 수정 연산 후, 수정된 수열 $a$를 삭제 가능하게 만들기 위해 최소 몇 개의 수를 수정해야 하는지 답해야 한다.

각 수정 연산은 특정 위치의 값을 바꾸거나, 수열 전체에 1을 더하거나, 수열 전체에서 1을 빼는 연산이다.

입력

첫 번째 줄에는 두 개의 양의 정수 $n, m$이 주어지며, 각각 수열의 길이와 수정 횟수를 나타낸다.

두 번째 줄에는 $n$개의 양의 정수가 주어지며, 수열 $a$를 나타낸다. 즉, 입력된 $i$번째 수는 수열 $a$의 $i$번째 원소 $a_i$이다.

이어지는 $m$개의 줄에는 각각 두 정수 $p, x$가 주어지며, 이는 수정 연산을 나타낸다.

$1 \le p \le n$일 때, 이 연산은 단일 위치 수정으로, 수열의 $p$번째 원소 $a_p$를 $x$로 바꾼다.

$p = 0$일 때, 이 연산은 수열 전체에 $x$를 더하는 연산이다.

출력

$m$개의 줄을 출력한다. 각 줄에는 해당 수정 연산 후의 정답을 출력한다.

예제

예제 입력 1

3 9
1 2 3
1 1
0 1
0 1
0 1
2 2
3 2
0 -1
0 -1
0 -1

예제 출력 1

0
1
2
3
2
1
1
2
2

참고

첫 번째 수정 후, 수열은 $(1, 2, 3)$이며, 수정 없이 삭제 가능하다.

네 번째 수정 후, 수열은 $(4, 5, 6)$이며, 세 수를 모두 수정해야 삭제 가능해진다.

여섯 번째 수정 후, 수열은 $(4, 2, 2)$이며, 첫 번째 수를 $3$으로 바꾸면 삭제 가능하다.

아홉 번째 수정 후, 수열은 $(1, -1, -1)$이며, 두 번째 수를 $2$로, 세 번째 수를 $3$으로 바꾸면 삭제 가능하다.

서브태스크

모든 데이터에 대하여,

• $1\le n,m \le 1.5 \times 10^5$
• $1\le a_i \le n$
• $0\le p\le n$
  • $p>0$ 일 때, $1\le x \le n$
  • $p=0$ 일 때, $x=-1$ 또는 $1$