Максимальная сумма

Задана последовательность целых чисел $a_1,a_2,...,a_n(0\le a_i\le 10^8,2\le n\le 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\le 10^5)$. За ней идут $q$ строк, которые описывают выполняемые на последовательности операции.

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

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

Примеры