Tổng hai phần tử lớn nhất (Maximum Sum)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Cho dãy $A_1,A_2,\ldots,A_N$. Có hai loại thao tác:

• U i x: gán $A_i=x$.
• Q x y: với $1\le x<y\le N$, hãy tìm tổng lớn nhất của hai phần tử ở hai vị trí khác nhau trong đoạn $[x,y]$.

Với mỗi thao tác Q, in giá trị lớn nhất tìm được.

Input

Dòng đầu chứa $N$.

Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Dòng thứ ba chứa $Q$, số thao tác.

$Q$ dòng tiếp theo, mỗi dòng là một thao tác U i x hoặc Q x y.

Output

Với mỗi thao tác Q, in một dòng chứa tổng lớn nhất của hai phần tử khác vị trí trong đoạn được hỏi.

Subtask

• Subtask 1 — 20%: $2\le N,Q\le 50$, $0\le A_i,x\le 10^4$.
• Subtask 2 — 30%: $2\le N,Q\le 5000$, $0\le A_i,x\le 10^8$.
• Subtask 3 — 50%: $2\le N\le 10^5$, $1\le Q\le 10^5$, $0\le A_i,x\le 10^8$.

Ví dụ

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

Trong truy vấn đầu, đoạn $[2,4]$ có hai giá trị lớn nhất là $4$ và $3$, nên đáp án là $7$. Các cập nhật sau đó thay đổi trực tiếp phần tử được chỉ định.