Троє з Простоквашино 3
- Пєчкін, а я навчився працювати з деревом відрізків.
- Зайнятись тобі нічим просто, Шарик. Краще б допоміг мені листи розносити.
- Ну, Пєчкін, я вже навіть виконав завдання Дядька Федора та Кота Матроскіна, тільки цей Матроскін не захотів перовіряти, чи вірно я зробив.
- Ну ладно, давай я перовірю, що там потрібно було зробити?
- У мене був масив чисел та множина запитів, що являє собою або запит на зміни у масиві, або містить число, для якого мені потрібно було знайти такий проміжок [l; r], що максимум на цьому проміжку був би рівним заданому числу. Можеш прочитати попередню задачу.
- Розберемось…
Вхідні дані
У першому рядку міститься одне число N (1 ≤ N ≤ 10^6) – кількість елементів у масиві. У наступному рядку знаходиться N цілих, невід'ємних чисел, які не перевищують 10^9 – самі елементи масиву. Потім йде число M (1 ≤ M ≤ 10^5) – кількість запитів. Потім М рядків, перше число у кожному з яких означає тип запиту: якщо воно дорівнює одиниці, то далі йде єдине число x, і Шарику потрібно було знайти два числа l та r, такі, що максимум на проміжку [l; r], був рівний x. Якщо ж тип запиту рівний двом, то далі йде два числа pos та val і це означає, що елемент масиву, який стоїть на позиції pos, тепер змінено і він став рівним значенню val. Далі для кожного запиту з номером один міститься по рядку з двома числами l та r – відповіді Шарика.
Вихідні дані
Для кожної відповіді Шарика виведіть "Yes", якщо він відповів вірно і "No", якщо Шарик помилився. Відімітимо, що хоча у попередній задачі було необхідно знайти мінімальні числа l та r, тут Пєчкін перовіряти цього не буде.