물고기 2

JOI군은 번호가 1부터 $N$까지인 물고기 $N$마리를 기르고 있다. 물고기 $i$ ($1 \le i \le N$)의 크기는 $A_i$이다.

물고기를 기를 때는 다음 사실에 주의해야 한다. 인접한 두 물고기가 있으면 시간이 지남에 따라 한 물고기가 다른 물고기를 먹는다. 두 물고기 사이에 다른 물고기가 없으면 두 물고기는 인접한 것이다. 정확히 말하면, 물고기 $x$의 크기가 물고기 $y$의 크기 이상이고 두 물고기가 인접하면 $x$가 $y$를 먹는다. 그러면 $x$의 크기는 원래 크기에 $y$의 크기를 더한 값이 된다. 두 물고기의 크기가 같으면 둘 중 어느 쪽이든 상대를 먹을 수 있다.

JOI군은 $Q$일 동안 사고 실험을 하며 물고기를 기른다. $j$일째 ($1 \le j \le Q$)에 다음 중 한 가지 행동을 한다.

• 1번 행동: 물고기 $X_j$에게 특별한 사료를 준다. 그 뒤 물고기 $X_j$의 크기는 $Y_j$가 된다.
• 2번 행동: 번호가 $L_j$부터 $R_j$까지인 물고기만 골라 왼쪽에서 오른쪽 순서로 수족관에 넣는다. 위 규칙에 따르면 물고기는 한 마리만 살아남는다. 살아남는 물고기는 어떤 물고기가 언제 먹히는지에 따라 달라진다. 물고기의 순서는 바뀌지 않으며, 같은 물고기를 두 마리가 동시에 먹는 일은 없다. JOI군은 살아남을 수 있는 물고기 번호의 가짓수를 알고 싶어 한다.

이것은 사고 실험일 뿐이며, 실제로 물고기가 먹히지는 않는다.

첫 줄에 $N$이 주어진다. 둘째 줄에는 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. 다음 줄에 $Q$가 주어진다. 이어지는 $Q$개의 줄은 각각 $T_j$로 시작하는 질의이다.

$T_j = 1$이면 한 줄에 정수 $X_j$와 $Y_j$가 주어진다. 이는 $j$일째의 1번 행동으로, 물고기 $X_j$의 크기가 $Y_j$가 된다.

$T_j = 2$이면 한 줄에 정수 $L_j$와 $R_j$가 주어진다. 이는 $j$일째의 2번 행동으로, 물고기 $L_j$부터 $R_j$까지를 대상으로 한다.

2번 행동이 나올 때마다 입력 순서대로, 살아남을 수 있는 물고기 번호의 가짓수를 한 줄에 하나씩 출력한다.

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le A_i \le 1000000000$ ($1 \le i \le N$)
• $T_j$는 1 또는 2이다 ($1 \le j \le Q$)
• $1 \le X_j \le N$ ($1 \le j \le Q$)
• $1 \le Y_j \le 1000000000$ ($1 \le j \le Q$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)