D - Grades and Supplementary Lessons Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君の学校では、 N 人の生徒が期末テストを受けました。各生徒には 1 から N までの出席番号が付けられています。

テストの結果、生徒 i の得点は S_i でした。

ここで基準値を次のように定めます。 N 人の得点を小さい順に並べた列を A_1 \le A_2 \le \cdots \le A_N とします。同じ得点の生徒が複数いる場合も、それぞれを別の要素として列に含めます（したがって列の長さは常に N です）。このとき、先頭から \lceil N/2 \rceil 番目の値 A_{\lceil N/2 \rceil} を基準値とします。ここで \lceil \cdot \rceil は天井関数（切り上げ）を表します。たとえば N = 5 のときは \lceil 5/2 \rceil = 3 番目、 N = 4 のときは \lceil 4/2 \rceil = 2 番目の値が基準値です。なお、同じ得点の要素が複数あっても、それらの間の並び順によらず A_{\lceil N/2 \rceil} の値は一意に定まります。

このテストでは、得点が厳密に基準値未満の生徒が補習の対象となります。基準値と同じ得点の生徒は補習の対象にはなりません。

その後、先生は採点の見直しにより、生徒の得点を Q 回にわたって更新します。得点が増える場合も減る場合もあり、同じ生徒の得点が複数回更新されることもあります。

j 回目の更新（ 1 \le j \le Q ）では、生徒 T_j の得点を V_j に置き換えます。

各更新の直後に、補習の対象となる生徒の人数を求めてください。すなわち、その時点での N 人の得点から定まる基準値に対して、得点が厳密に基準値未満である生徒が何人いるかを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq T_j \leq N （ 1 \leq j \leq Q ）
  • 0 \leq V_j \leq 10^9 （ 1 \leq j \leq Q ）
  • 入力はすべて整数である。

入力

N Q
S_1 S_2 \ldots S_N
T_1 V_1
T_2 V_2
\vdots
T_Q V_Q
  • 1 行目には、生徒の人数を表す整数 N と、更新の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各生徒の初期得点 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各更新の内容が与えられる。
  • 2 + j 行目（ 1 \le j \le Q ）には、 j 回目の更新で得点を変更する生徒の出席番号 T_j と、変更後の得点 V_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。 j 行目（ 1 \le j \le Q ）には、 j 回目の更新の直後における補習対象の生徒の人数を整数で出力せよ。

入力例 1

5 3
50 30 70 20 60
2 55
4 80
1 10

出力例 1

2
2
2

入力例 2

4 2
40 40 40 40
1 30
3 30

出力例 2

1
0

入力例 3

10 5
15 92 35 78 54 12 67 43 89 26
3 80
7 10
1 100
5 20
10 50

出力例 3

4
4
4
4
4

入力例 4

15 8
100 200 300 400 500 600 700 800 900 1000 50 150 250 350 450
1 999
11 999
5 0
8 0
15 1000
3 500
12 500
7 0

出力例 4

7
7
7
7
7
7
6
7

入力例 5

1 1
100
1 0

出力例 5

0

Score : 400 pts

Problem Statement

At Takahashi's school, N students took a final exam. Each student is assigned a student ID number from 1 to N.

As a result of the exam, student i scored S_i points.

The threshold value is defined as follows. Sort the scores of all N students in non-decreasing order to form a sequence A_1 \le A_2 \le \cdots \le A_N. If multiple students have the same score, each is included as a separate element in the sequence (so the sequence always has length N). The threshold value is the \lceil N/2 \rceil-th value A_{\lceil N/2 \rceil}, where \lceil \cdot \rceil denotes the ceiling function (rounding up). For example, when N = 5, the threshold is the \lceil 5/2 \rceil = 3-rd value, and when N = 4, it is the \lceil 4/2 \rceil = 2-nd value. Note that even if there are multiple elements with the same score, the value of A_{\lceil N/2 \rceil} is uniquely determined regardless of how ties are ordered.

In this exam, students whose scores are strictly less than the threshold value are required to attend supplementary lessons. Students whose scores are equal to the threshold value are not required to attend.

Afterwards, the teacher updates the students' scores Q times due to regrading. Scores may increase or decrease, and the same student's score may be updated multiple times.

In the j-th update (1 \le j \le Q), the score of student T_j is replaced with V_j.

Immediately after each update, determine the number of students who are required to attend supplementary lessons. That is, output the number of students whose scores are strictly less than the threshold value determined from the current scores of all N students.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq Q)
  • 0 \leq V_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Input

N Q
S_1 S_2 \ldots S_N
T_1 V_1
T_2 V_2
\vdots
T_Q V_Q
  • The first line contains an integer N representing the number of students and an integer Q representing the number of updates, separated by a space.
  • The second line contains the initial scores S_1, S_2, \ldots, S_N of each student, separated by spaces.
  • The following Q lines describe each update.
  • The (2 + j)-th line (1 \le j \le Q) contains the student ID T_j of the student whose score is changed in the j-th update and the new score V_j, separated by a space.

Output

Print Q lines. The j-th line (1 \le j \le Q) should contain an integer representing the number of students required to attend supplementary lessons immediately after the j-th update.

Sample Input 1

5 3
50 30 70 20 60
2 55
4 80
1 10

Sample Output 1

2
2
2

Sample Input 2

4 2
40 40 40 40
1 30
3 30

Sample Output 2

1
0

Sample Input 3

10 5
15 92 35 78 54 12 67 43 89 26
3 80
7 10
1 100
5 20
10 50

Sample Output 3

4
4
4
4
4

Sample Input 4

15 8
100 200 300 400 500 600 700 800 900 1000 50 150 250 350 450
1 999
11 999
5 0
8 0
15 1000
3 500
12 500
7 0

Sample Output 4

7
7
7
7
7
7
6
7

Sample Input 5

1 1
100
1 0

Sample Output 5

0