Hai giá trị lớn nhất trong đoạn

Bối cảnh và bài toán

Một chuỗi chỉ số thay đổi theo thời gian. Với mỗi đoạn truy vấn, hệ thống cần tổng lớn nhất có thể tạo bởi hai vị trí khác nhau trong đoạn đó. Xen kẽ với truy vấn là các cập nhật điểm.

Yêu cầu

Xử lý các cập nhật và truy vấn tổng của hai phần tử lớn nhất trong đoạn.

Input

• Dòng 1 chứa n.
• Dòng 2 chứa n số.
• Dòng 3 chứa q.
• U i x: gán vị trí i bằng x.
• Q l r: in tổng lớn nhất của hai phần tử khác vị trí trong [l,r].

Output

In một dòng cho mỗi truy vấn Q.

Ràng buộc

• 2 <= n <= 10^5
• 0 <= a[i], x <= 10^8
• 1 <= q <= 10^5
• Với truy vấn, 1 <= l < r <= n.

Chấm điểm

Ví dụ 1

Input

5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5

Output

7
9
11
12

Giải thích. Mỗi truy vấn chọn hai giá trị lớn nhất khác vị trí.

Ví dụ 2

Input

4
5 5 1 2
3
Q 1 2
U 2 0
Q 1 4

Output

10
7

Giải thích. Giá trị bằng nhau ở hai vị trí khác nhau vẫn có thể cùng được chọn.

Thông tin bài tập

Nguồn: Phỏng theo SPOJ KGSS – Maximum Sum (Kurukshetra 2009 OPC).