Задана последовательность целых чисел a1, a2, ..., an (0 ≤ ai ≤ 108, 2 ≤ n ≤ 105). К ней применяются операции двух типов:

Update:

Операция обозначается символом 'U', за которым следуют два целых числа i и x.

U i x, 1 ≤ i ≤ n и 0 ≤ x ≤ 108

Эта операция устанавливает значение ai равным x.

Query:

Операция обозначается символом 'Q', за которым следуют два целых числа i и j.

Q x y, 1 ≤ x < y ≤ n

Необходимо найти такие i и j, что x ≤ i, j ≤ y и i ≠ j, для которых сумма ai + aj максимальна. Вывести значение суммы ai + aj.

Входные данные

Первая строка содержит длину последовательности n. Следующая строка содержит n целых чисел ai. Следующая строка содержит количество запросов q (q ≤ 105). За ней идут q строк, которые описывают выполняемые на последовательности операции.

Выходные данные

Для каждой Query операции вывести значение максимальной суммы.