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