23833번 - F1ow3rC0n

문제

인문예술탐사주간에 세종호수공원에 가서 사진도 찍고 사용할 꽃잎도 나무에서 딴 태영이는, 나중에 이 나무의 꽃잎을 뜯으면 안 된다는 사실을 들었다. 그래서 태영이는 본드를 이용해서 꽃잎을 나무에 다시 붙이려는 계획을 세웠다.

세종호수공원에는 일렬로 나열된 나무가 총 $N$ 그루 있으며, $i$ 번째 나무에 핀 꽃의 종류 번호는 $K_i$이다. 태영이는 다음과 같은 방법을 사용해서 $Q$ 일 동안 꽃잎을 나무에 붙일 예정이다.

$i$ 번째 날에는 다음의 두 일 중 하나가 일어난다.

• 태영이가 본드를 이용해서 $A_i, A_i+1, \cdots, B_i$ 번째 나무에 순서대로 꽃잎을 붙인다.
• $A_i$ 번째 나무에 핀 꽃의 종류 번호가 $B_i$로 바뀐다.

태영이는 꽃잎의 구조를 살펴보던 중에, 나무에 핀 꽃의 종류 번호와 같은 종류 번호의 본드를 사용해야 한다는 사실을 깨달았고, $i$ 번째 날에는 다음과 같은 방법으로 꽃잎을 본드에 붙이기로 했다. 매일, 처음에 태영이는 본드를 들고 있지 않다.

• 태영이는 $A_i$ 번째부터 $B_i$ 번째까지의 나무에 순서대로 꽃잎을 붙인다. 꽃잎을 붙이는 순서가 정해져 있음에 유의하여라.
• 태영이가 본드를 들고 있지 않은 경우, 원하는 종류의 본드를 하나 구매할 수 있다.
• 태영이가 본드를 들고 있는 경우, 해당 본드를 버릴 수 있다.
• 태영이가 꽃잎을 붙이려는 나무의 꽃의 종류 번호와 태영이가 들고 있는 본드의 종류 번호가 같은 경우에만 꽃잎을 붙일 수 있다.

태영이는 꽃잎을 붙이는 각 날마다, 본드를 최소 몇 개 구매해야하는지 궁금해졌다.

입력

첫번째 줄에는 나무의 개수 $N$과, 태영이가 꽃잎을 붙이는 일수 $Q$가 공백으로 구분되어 주어진다.

두번째 줄에는 각 나무의 꽃의 종류 번호 $K_1, K_2, \cdots, K_N$이 공백으로 구분되어 주어진다.

다음 $Q$ 개의 줄의 $i$번째 줄에는 일어나는 일의 종류 $T_i$와 일에 해당하는 $A_i,ドル $B_i$가 공백으로 구분되어 주어진다.

• $T_i = 1$이면, $A_i$ 번째부터 $B_i$ 번째 까지의 나무에 차례로 꽃잎을 붙인다.
• $T_i = 2$이면, $A_i$ 번째 나무에 핀 꽃의 종류 번호가 $B_i$로 바뀐다.

출력

$T_i = 1$인 날에 대해, 구매해야 하는 본드의 최소 개수를 한 줄에 하나씩 출력하여라.

제한

• 1ドル \le N, Q \le 100,000円$
• 1ドル \le K_i \le 100$ (1ドル \le i \le N$)
• 1ドル \le T_i \le 2$ (1ドル \le i \le Q$)
• $T_i = 1$일 때, 1ドル \le A_i \le B_i \le N$ (1ドル \le i \le Q$)
• $T_i = 2$일 때, 1ドル \le A_i \le N$ (1ドル \le i \le Q$)
• $T_i = 2$일 때, 1ドル \le B_i \le 100$ (1ドル \le i \le Q$)
• $T_i = 1$인 $i$가 적어도 하나 존재한다. (1ドル \le i \le Q$)

힌트