Максимальна сума
Задано послідовність цілих чисел a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^8 , 2 ≤ n ≤ 10^5). До неї застосовуються операції двох типів:
Update:
Операція позначається символом 'U', за яким слідують два цілі числа i та x.
U i x, 1 ≤ i ≤ n и 0 ≤ x ≤ 10^8
Ця операція встановлює значення a[i] рівним x.
Query:
Операція позначається символом 'Q', за яким слідують два цілі числа i та j.
Q x y, 1 ≤ x < y ≤ n
Необхідно знайти такі i та j, що x ≤ i, j ≤ y и i ≠ j, для яких сума a[i] + a[j] максимальна. Вивести значення суми a[i] + a[j].
Вхідні дані
Перший рядок містить довжину послідовності n. Наступний рядок містить n цілих чисел a[i]. Наступний рядок містить кількість запитів q (q ≤ 10^5). Далі q рядків описують операції, що виконуються на послідовності.
Вихідні дані
Для кожної Query операції вивести значення максимальної суми.