B - Updating the Report Card Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は学校のクラス担任として、生徒たちの成績管理を行っています。クラスには N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。i 番目の生徒の初期の点数は S_i 点です。

学期末になり、成績表の更新作業を行うことになりました。更新は合計 M 回行われます。j 回目の更新では、生徒 P_j の点数が V_j 点に書き換えられます。同じ生徒に対して複数回の更新が行われることもあり、その場合は更新のたびに点数が上書きされます。

すべての更新が完了した後、点数が K 点未満の生徒は補習対象となります。高橋君のために、補習対象となる生徒の人数を求めてください。ただし、K 点ちょうどの生徒は補習対象に含まれません。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 0 \leq K \leq 100
  • 0 \leq S_i \leq 100 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • 0 \leq V_j \leq 100 (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M K
S_1 S_2 \cdots S_N
P_1 V_1
P_2 V_2
\vdots
P_M V_M
  • 1 行目には、生徒の人数を表す N 、更新の回数を表す M 、補習の基準点を表す K が、スペース区切りで与えられる。
  • 2 行目には、各生徒の初期の点数を表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • S_i は i 番目の生徒の初期の点数を表す。
  • 3 行目から 2 + M 行目には、更新の内容が与えられる（M = 0 の場合、この部分は存在しない）。
  • 2 + j 行目には、j 回目の更新で点数が変更される生徒の番号 P_j と、変更後の点数 V_j が、スペース区切りで与えられる。

出力

すべての更新が完了した後、点数が K 点未満である補習対象の生徒の人数を 1 行で出力してください。

入力例 1

5 3 60
45 72 58 81 39
1 65
3 62
5 55

出力例 1

1

入力例 2

3 0 50
30 50 70

出力例 2

1

入力例 3

10 6 70
85 42 67 91 55 78 63 49 72 88
2 75
4 68
5 70
7 71
8 45
2 69

出力例 3

4

Score : 233 pts

Problem Statement

Takahashi is managing student grades as the homeroom teacher of a school class. There are N students in the class, numbered from 1 to N. The initial score of the i-th student is S_i points.

At the end of the term, it is time to update the report cards. A total of M updates are performed. In the j-th update, the score of student P_j is changed to V_j points. The same student may be updated multiple times, in which case their score is overwritten with each update.

After all updates are completed, students with a score strictly less than K points are required to attend supplementary lessons. For Takahashi's sake, determine the number of students who are required to attend supplementary lessons. Note that students with exactly K points are not included.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 0 \leq K \leq 100
  • 0 \leq S_i \leq 100 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • 0 \leq V_j \leq 100 (1 \leq j \leq M)
  • All input values are integers

Input

N M K
S_1 S_2 \cdots S_N
P_1 V_1
P_2 V_2
\vdots
P_M V_M
  • The first line contains N representing the number of students, M representing the number of updates, and K representing the threshold score for supplementary lessons, separated by spaces.
  • The second line contains the initial scores S_1, S_2, \ldots, S_N of each student, separated by spaces.
  • S_i represents the initial score of the i-th student.
  • Lines 3 through 2 + M contain the details of the updates (if M = 0, this part does not exist).
  • Line 2 + j contains the student number P_j whose score is changed in the j-th update and the new score V_j, separated by a space.

Output

After all updates are completed, output in a single line the number of students whose score is strictly less than K points and are therefore required to attend supplementary lessons.

Sample Input 1

5 3 60
45 72 58 81 39
1 65
3 62
5 55

Sample Output 1

1

Sample Input 2

3 0 50
30 50 70

Sample Output 2

1

Sample Input 3

10 6 70
85 42 67 91 55 78 63 49 72 88
2 75
4 68
5 70
7 71
8 45
2 69

Sample Output 3

4