JOI-kun có \(N\) con cá, được đánh số từ \(1\) đến \(N\). Kích thước của con cá \(i\) là \(A_i\).

Khi nuôi cá, cần chú ý rằng hai con cá ở cạnh nhau có thể ăn nhau theo thời gian. Hai con cá được coi là ở cạnh nhau nếu không có con cá nào nằm giữa chúng. Cụ thể, nếu cá \(x\) có kích thước lớn hơn hoặc bằng cá \(y\) và hai con ở cạnh nhau, cá \(x\) có thể ăn cá \(y\). Sau đó, kích thước của cá \(x\) bằng tổng kích thước trước đó của hai con. Nếu hai con có cùng kích thước, con nào cũng có thể ăn con còn lại.

JOI-kun sẽ nuôi cá trong \(Q\) ngày. Để giết thời gian, cậu thực hiện các thí nghiệm tưởng tượng. Vào ngày thứ \(j\), cậu thực hiện một trong hai thao tác:

• Loại 1: Cho cá \(X_j\) ăn một loại thức ăn đặc biệt. Sau đó, kích thước của cá \(X_j\) trở thành \(Y_j\).
• Loại 2: Chỉ lấy những con cá có chỉ số từ \(L_j\) đến \(R_j\) và tưởng tượng đặt chúng vào bể theo thứ tự \(L_j,L_j+1,\ldots,R_j\) từ trái sang phải. Theo quy luật trên, cuối cùng chỉ còn một con sống sót. Chỉ số của con sống sót phụ thuộc vào việc chọn con nào bị ăn và thời điểm các lần ăn xảy ra. JOI-kun muốn biết có bao nhiêu chỉ số có thể là chỉ số của con sống sót. Trong thí nghiệm, thứ tự các con cá không thay đổi và không có hai con cá cùng ăn một con khác tại cùng một thời điểm.

Hãy tính số chỉ số có thể sống sót cho từng thao tác loại \(2\). Các thí nghiệm này chỉ diễn ra trong tưởng tượng: không có con cá nào thực sự bị ăn, và thí nghiệm không làm thay đổi kích thước của các con cá trong những ngày sau.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N
A_1 A_2 ... A_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

Mỗi truy vấn nằm trên một dòng, gồm các số nguyên cách nhau bởi dấu cách. Số đầu tiên là \(T_j\):

• Nếu \(T_j=1\), dòng có dạng 1 X_j Y_j, nghĩa là đặt kích thước cá \(X_j\) thành \(Y_j\).
• Nếu \(T_j=2\), dòng có dạng 2 L_j R_j, nghĩa là thực hiện thí nghiệm tưởng tượng với đoạn cá từ \(L_j\) đến \(R_j\).

Dữ liệu ra

Với mỗi truy vấn loại \(2\), theo đúng thứ tự xuất hiện, xuất một dòng chứa số chỉ số có thể là chỉ số của con cá sống sót.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le Q\le 100\,000\).
• \(1\le A_i\le 10^9\) với mọi \(1\le i\le N\).
• \(T_j\in\{1,2\}\).
• Với truy vấn loại \(1\): \(1\le X_j\le N\) và \(1\le Y_j\le 10^9\).
• Với truy vấn loại \(2\): \(1\le L_j\le R_j\le N\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N\le 500\), \(Q\le 500\).
2. \(8\) điểm: \(Q=1\) và truy vấn duy nhất là loại \(2\) với \(L_1=1\), \(R_1=N\).
3. \(12\) điểm: \(Q\le 1000\).
4. \(23\) điểm: Mọi truy vấn đều là loại \(2\).
5. \(35\) điểm: Với mọi truy vấn loại \(2\), \(L_j=1\) và \(R_j=N\).
6. \(17\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
6 4 2 2 6
6
2 1 5
2 1 3
1 3 1
2 2 5
2 1 5
2 2 4

5
2
2
3
1

13
10 4 2 5 20 5 4 8 20 10 3 3 7
1
2 1 13

7

12
32 32 4 1 1 1 1 4 4 16 32 128
7
2 1 12
2 2 6
2 8 10
2 1 9
2 3 8
2 5 9
2 2 12

12
1
1
2
6
2
1

10
2 3 5 10 1 3 4 9 5 2
8
2 1 10
1 10 5
2 1 10
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10

4
6
1
6

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.