eolymp
bolt
Try our new interface for solving problems
Problems

Maximum Sum

Maximum Sum

Time limit 1 second
Memory limit 128 MiB

You are given a sequence of integers a[1], a[2], ..., a[n] (0a[i]10^8, 2n10^5). There are two types of operations and they are defined as follows:

Update:

This will be indicated in the input by a 'U' followed by space and then two integers i and x.

U i x, 1in and 0x10^8

This operation sets the value of a[i] to x.

Query:

This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.

Q x y, 1x < yn

You must find i and j such that xi, jy and ij, such that the sum a[i] + a[j] is maximized. Print the sum a[i] + a[j].

Input data

The first line consists of an integer n representing the length of the sequence. Next line consists of n integers a[i]. Next line contains an integer q (q10^5), representing the number of operations. Next q lines contain the operations.

Output data

Print in a separate line the maximum sum mentioned above for each Query.

Examples

Input example #1
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 example #1
7
9
11
12