페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7035
서브태스크

등수 조작 1초 1024MB

문제

N명의 학생의 성적은 1번 학생부터 N번 학생까지 각각 A_1, A_2,\ ...\ , A_N 점으로 결정되었다.

학생들의 등수는 본인보다 더 점수가 높은 학생들의 수 + 1로 결정된다.

해커들은 총 Q번의 수정 작업과 등수 확인 작업을 하였는데, 그 결과를 출력하는 프로그램을 작성하시오.


입력

첫 줄에 두 정수 N과 Q가 주어진다.

두 번째 줄에 N개의 정수 A_1, A_2,\ ...\ , A_N 가 주어진다.

세 번째 줄부터 Q줄에 걸쳐 해커들의 작업이 주어진다.

  • 1 x : x번 학생의 등수를 확인한다.

  • 2 x y : x번 학생의 점수를 y로 바꾼다.

[제한 조건]

  • 1 \le N,Q \le 10^5

  • 모든 점수는 1 이상 10^5 이하의 정수다.


출력

해커가 학생의 등수를 확인할 때 마다 해당 등수를 출력한다.


부분문제

번호 점수 조건
#120점

N,Q,A_i \le 100

#240점

A_i \le 100

#340점

추가 제한없음


예제1

입력
55
52341
11
213
11
211
11
출력
1
2
4

출처

@klee

역링크