e-olymp
Задачи

Приключения кота Леопольда

Приключения кота Леопольда

prb4495

- Выходи, подлый трус!

- Ребята, давайте жить дружно…

В этой задаче Леопольд решил проучить мышей, для этого он хочет сыграть с ними в следующую игру: будет дана последовательность неотрицательных чисел, состоящая из K элементов. Тогда за один ход можно уменьшить любой элемент последовательности, кроме первого, так чтобы он остался неотрицательным, и при этом увеличить элемент, стоящий на предыдущей позиции на такое же значение. Тот, кто не сможет сделать ход, проигрывает. Для того чтобы каждый раз не придумывать новые числа, они будут пользоваться общим массивом, который состоит из N натуральных чисел и из него получать игровую последовательность. При этом ленивые мыши выписывают подряд все числа, начиная с позиции l до позиции r, а хитрый Леопольд выбирает из оставшихся чисел еще одно и приписывает его в конец последовательности, которую образовали мыши. Эта последовательность и будет являться исходной для игры. Известно, что мыши всегда ходят первыми.

Вам необходимо ответить на вопрос – сможет ли Леопольд выбрать такое число, что поставив его в конец последовательности, образованной мышами, он гарантировано сможет выиграть?

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

В первой строке находится число N (1N106) – длина массива, которым будут пользоваться Леопольд и мыши для выбора последовательности для игры. В следующей строке находится N чисел – сам массив. Далее следует M (1M105) – количество запросов. Каждая из следующих M строк представляет собой один запрос и состоит из трех натуральных чисел, не превышающих 109x, l, r. Если x равен единице, числа l и r – границы подпоследовательности, выбранной мышами и Вам необходимо вывести "Yes", если Леопольд может выбрать последнее число и гарантировано победить, и "No" иначе. Гарантируется, что осталось хоть одно число, не выбранное мышами. Если же x равен двум, это значит, что элемент, стоящий на позиции l изменился и теперь равен r.

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

Для каждого запроса, где значение x равно единице, выведите "Yes" или "No".

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