Задача №3319. Номер максимума на подотрезке с изменением элемента

Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять номер максимального элемента из нескольких подряд идущих элементов.

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

В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.

Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить номер максимума, u — обновить значение элемента).

Следом за s вводятся два числа — номера левой и правой границы отрезка.

Следом за u вводятся два числа — номер элемента и его новое значение.

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

Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.

Примеры
Входные данные
5
2 4 1 3 5
3
s 2 4
u 1 10
s 1 3
Выходные данные
2 1
Сдать: для сдачи задач необходимо войти в систему