Cho dãy \(X_1,X_2,\ldots,X_N\) và \(Q\) thao tác thuộc hai loại:

• 0 a b c: đếm các phần tử \(X_i\ge c\) với \(a\le i\le b\).
• 1 a b: gán \(X_a=b\).

Hãy trả lời các thao tác đếm theo thứ tự xuất hiện.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• Dòng tiếp theo chứa \(N\) số \(X_1,\ldots,X_N\).
• Dòng thứ ba chứa \(Q\).
• \(Q\) dòng sau chứa các thao tác theo định dạng trên.

Dữ liệu ra

Với mỗi thao tác loại 0, in kết quả trên một dòng. Thao tác loại 1 không có dòng kết quả.

Ràng buộc

• \(1\le N\le5\cdot10^5\), \(1\le Q\le10^5\).
• \(1\le X_i\le10^9\).
• Loại 0: \(1\le a\le b\le N\), \(1\le c\le10^9\).
• Loại 1: \(1\le a\le\min(N,10^5)\), \(2\le b\le10^9\).

Ví dụ

5
1 2 3 4 5
3
0 1 5 10
1 2 20
0 1 3 10

0
1

Nguồn

SPOJ GIVEAWAY — Give Away.