고용

당신은 Just Odd Inventions 사를 아는가? 이 회사의 업무는 "단지 기묘한 발명(just odd inventions)"을 하는 것이다. 여기서는 줄여서 JOI 사라고 부른다.

JOI 사는 사업을 확장하기 위해 새로이 사원을 고용하게 되었다.

사원 후보자가 N명 있다. 후보자에게는 각각 1부터 N까지의 번호가 붙어 있으며, 각 후보자에게는 평가값이라는 정수 하나가 정해져 있다.

이번 고용에서는 평가값이 어떤 값 이상인 후보자를 전원 채용한다. 새로 채용된 사원을 몇 개의 그룹으로 나눈다. 새로 채용된 사원의 그룹을 다음 조건을 만족하도록 만든다.

• 후보자 a와 후보자 b (a < b)가 둘 다 채용되었을 때, 이 사원들이 같은 그룹에 들어가는 것은 후보자 c (a ≦ c ≦ b)가 전원 채용된 경우이며, 그때에만 그러하다.

JOI 사의 인사 담당인 당신은 쿼리를 총 M개 순서대로 처리하여 이번 고용에서 만들어지는 그룹의 개수를 추정하게 되었다. j번째 쿼리는 다음 두 종류 중 하나이다.

• 평가값이 Bj 이상인 후보자를 전원 채용할 경우 만들어지는 그룹의 개수를 구한다. 이 종류의 쿼리를 답 쿼리라고 부른다.
• 후보자 Cj의 평가값을 Dj로 갱신한다. 이 종류의 쿼리를 갱신 쿼리라고 부른다.

M개의 쿼리에 대한 정보가 주어졌을 때, 각 답 쿼리에 대한 그룹의 개수를 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 1번째 줄에는 정수 N, M이 공백을 구분으로 쓰여 있다. 이는 사원 후보자가 N명 있고, 당신이 M개의 쿼리를 처리한다는 것을 나타낸다.

• 이어지는 N개 줄 중 i번째 줄 (1 ≦ i ≦ N)에는 정수 Ai가 쓰여 있다. 이는 쿼리를 처리하기 이전에는 후보자 i의 평가값이 Ai라는 것을 나타낸다.

• 이어지는 M개 줄 중 j번째 줄 (1 ≦ j ≦ M)에는 2개 또는 3개의 정수가 공백을 구분으로 쓰여 있다. 1번째 정수를 Tj라고 하면, 이 줄의 내용은 다음 중 하나이다.

  1. Tj = 1일 때. 이 줄에는 정수 Tj, Bj가 공백을 구분으로 쓰여 있다. 이는 j번째 쿼리가 평가값이 Bj 이상인 후보자를 전원 채용할 경우 만들어지는 그룹의 개수를 구하는 답 쿼리라는 것을 나타낸다.
  2. Tj = 2일 때. 이 줄에는 정수 Tj, Cj, Dj가 공백을 구분으로 쓰여 있다. 이는 j번째 쿼리가 후보자 Cj의 평가값을 Dj로 갱신하는 갱신 쿼리라는 것을 나타낸다.

표준 출력에 각 답 쿼리에 대한 그룹의 개수를 순서대로 1줄씩 출력하라.

• 1 ≦ N ≦ 200 000.
• 1 ≦ M ≦ 200 000.
• 1 ≦ Ai ≦ 1 000 000 000 (1 ≦ i ≦ N).
• 1 ≦ Tj ≦ 2 (1 ≦ j ≦ M).
• 1 ≦ Bj ≦ 1 000 000 000 (1 ≦ j ≦ M).
• 1 ≦ Cj ≦ N (1 ≦ j ≦ M).
• 1 ≦ Dj ≦ 1 000 000 000 (1 ≦ j ≦ M).
• Tj = 1인 j (1 ≦ j ≦ M)가 적어도 하나 존재한다.