Задано послідовність цілих чисел 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 операції вивести значення максимальної суми.