Remote Training on Programming

Дана последовательность n целых чисел a₁, a₂, ..., a_n, которые в процессе работы могут изменяться. Требуется написать программу, умеющую быстро находить минимум на отрезке от i до j, то есть min(a_i, a_i+1, ..., a_j).

Input

В первой строке записано число элементов n. Во второй строке через пробел записаны n целых чисел. В третьей строке записано число запросов m. В следующих m строках записаны запросы двух видов:
UPDATE i v - означает, что a_i становится равным v,
MIN i j - означает, что ваша программа должна вывести минимум элементов на отрезке [i,j], то есть min(a_i, a_i+1, ..., a_j).

Ограничения: n от 1 до 100000, m от 1 до 50000, элементы последовательности - от 0 до 1000000.

Output

Выведите по одному числу в отдельной строке на каждый запрос типа MIN

Sample

5
1 2 3 4 5
3
MIN 2 4
UPDATE 3 1
MIN 2 4

2
1