e-olymp
Задачи

Цветик-Семицветик

Цветик-Семицветик

prb4485

Жила была девочка Женя. Как-то раз мама послала ее в магазин за баранками, но по дороге она нашла цветок, да не простой, а волшебный – Цветик-Семицветик, он выполнял любые желания. Как любая маленькая девочка, Женя загадала себе много-много игрушек, а именно n игрушек. Она пронумеровала места на полке от 1 до n и красиво расставила игрушки. Кроме того, для каждой игрушки она определила "красивость" - натуральное число, определяющее степень красоты игрушки. К Жене в гости часто приходят ее друзья, при этом, если приходит девочка, она называет два числа l и r, а затем Женя выбирает самую красивую игрушку из тех, что стоят на полочке на промежутке от l до r, и дарит ей. Если же приходит мальчик, он называет одно число v и дает свою игрушку с красивостью k, после чего Женя меняет его игрушку на ту, которая стоит на полочке с номером v. Если в какой-то момент девочка называет такие числа, что на этих местах нет ни одной игрушки, Женя, чтобы не расстроить ее, дарит ей самую красивую из всех, что у нее есть, если у нее совсем не осталось игрушек, выведите "O-o-ops". Если на промежутке несколько самых красивых игрушек, Женя выбирает игрушку с минимальным местом на полочке. Если в какой-то момент мальчик называет число, и в этом месте не оказывается игрушки, то он просто забирает обратно свою игрушку и сделка не состоится.

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

В первой строке находится количество игрушек n у Жени. Во второй строке расположены n (1 n 106) чисел ai (1ai109) - красивости игрушек. В третьей строке находится количество друзей m (1 m 105) у Жени. В следующих m строках находятся запросы друзей. Если к Жене пришла девочка, то первым будет символ "g", а затем два числа l и r. Если же мальчик, то первым символом будет "b", а затем два числа v и k.

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

Для каждой девочки выведите одно число - красивость игрушки, которую ей подарит Женя или "O-o-ops", если у нее игрушек нет.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
4
1 2 3 4
6
g 1 1
g 2 3
b 2 5
g 1 1
g 2 4
g 1 4
Выходные данные
1
3
5
4
O-o-ops
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года