Sắc màu phố chợ 2112

Vào năm 2112, thế giới đã tiến tới một kỷ nguyên hoàng kim. Nhờ sự bùng nổ của công nghệ và trí tuệ nhân tạo, năng suất lao động đạt đến mức cực thịnh, của cải dư thừa đủ để cung cấp cho gấp đôi dân số toàn cầu. Xã hội vận hành theo lý tưởng: mọi người làm việc theo năng lực và hưởng thụ theo nhu cầu. Tuy nhiên, bản năng trao đổi và thú vui mua sắm của con người vẫn không hề mất đi.

Tại "Đại lộ Bình Minh", có \(n\) cửa hàng xếp kề nhau thành một đường thẳng, đánh số từ \(1\) tới \(n\). Mỗi cửa hàng ở đây vô cùng chuyên môn hóa: cửa hàng \(i\) chỉ bán duy nhất một loại mặt hàng đặc trưng với giá niêm yết là \(a_i\). Để đảm bảo trật tự kinh doanh và giúp khách hàng dễ dàng hoạch định chi tiêu, các chủ tiệm đã ký kết một hiệp ước: các mặt hàng được sắp xếp sao cho giá của chúng không tăng khi đi từ đầu phố đến cuối phố, tức là \(a_i \ge a_{i+1}\) với mọi \(1 \le i < n\).

Mặc dù vậy, sự biến động của chuỗi cung ứng vẫn khiến giá cả hàng hóa thay đổi. Sở Giao dịch Hàng hóa (MXV) sẽ cập nhật mức giá sàn mới theo từng giai đoạn. Khi có một thông báo điều chỉnh giá, thông tin sẽ được truyền từ đầu phố (cửa hàng \(1\)) lan dần xuống cuối phố. Tuy nhiên, do mạng lưới truyền dẫn đôi khi bị nhiễu, thông tin chỉ lan đến cửa hàng thứ \(x\) rồi dừng lại. Khi đó, tại mỗi cửa hàng \(i\) (\(1 \le i \le x\)), giá sẽ được cập nhật lại thành:

Lưu ý rằng sau mỗi lần điều chỉnh, tính chất không tăng của dãy giá vẫn luôn được bảo toàn.

Cư dân năm 2112 cũng có thói quen mua sắm rất đặc biệt. Một người mua hàng khi ghé thăm đại lộ sẽ mang theo một số tiền \(c\) và bắt đầu hành trình từ một cửa hàng \(u\) bất kỳ, sau đó đi bộ dọc theo chiều tăng của số thứ tự cho đến cuối phố. Tại mỗi cửa hàng \(i\) đi ngang qua, nếu số tiền còn lại đủ để mua mặt hàng \(a_i\), họ sẽ lập tức mua nó và cập nhật số tiền còn lại:

Nếu không đủ tiền, họ lẳng lặng bỏ qua và đi tiếp sang cửa hàng tiếp theo với hy vọng tìm được món hàng rẻ hơn ở phía cuối phố. Nhiệm vụ của bạn là ghi lại kết quả của \(q\) hoạt động diễn ra trên đại lộ.

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 3 \cdot 10^5\)) --- số lượng cửa hàng.

Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 2 \cdot 10^{13}\)) --- giá ban đầu của các mặt hàng (\(a_i \ge a_{i+1}\)).

Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 3 \cdot 10^5\)) --- số lượng hoạt động.

\(q\) dòng tiếp theo, mỗi dòng mô tả một hoạt động thuộc một trong hai loại:

• 1 x y: Thông tin giá sàn \(y\) lan đến cửa hàng \(x\). Cập nhật giá các cửa hàng từ \(1\) đến \(x\). (\(1 \le x \le n, 1 \le y \le 2 \cdot 10^{13}\)).
• 2 u c: Khách hàng xuất phát từ cửa hàng \(u\) với số tiền \(c\) (\(1 \le u \le n, 1 \le c \le 2 \cdot 10^{13}\)).

Output

Với mỗi hoạt động loại 2, in ra một số nguyên duy nhất trên một dòng là số lượng món hàng khách hàng mua được.

Example

8
1919 1650 1496 849 674 565 98 20
9
2 6 2356
1 1 236
1 7 1122
2 7 4086
2 5 6863
1 8 1532
1 8 825
1 2 1890
2 1 10000

3
2
4
6

Scoring

• Subtask 1 (20% số điểm): \(n, q \le 5000\).
• Subtask 2 (20% số điểm): \(a_i\) và \(y\) luôn có dạng \(2^k\) với \(k\) là một số nguyên không âm.
• Subtask 3 (15% số điểm): Không có hoạt động loại 1.
• Subtask 4 (15% số điểm): Tất cả hoạt động loại 1 xảy ra trước các hoạt động loại 2.
• Subtask 5 (30% số điểm): Không có ràng buộc gì thêm.