Three from Prostokvashino 3
- Pechkin, I've learned how to work with segment trees.
- You must have too much free time, Sharik. You should help me deliver the letters instead.
- But Pechkin, I've already completed the task given by Uncle Fyodor and Cat Matroskin, though Matroskin didn't want to verify if I did it correctly.
- Alright, let me take a look. What was the task?
- I had an array of numbers and a series of queries. These queries either requested changes to the array or asked me to find an interval [l; r] where the maximum value in that interval matched a given number. You can refer to the previous task for more details.
- Let's sort this out…
Input
The first line contains a single integer N (1 ≤ N ≤ 10^6), representing the number of elements in the array. The next line contains N non-negative integers, each not exceeding 10^9, which are the elements of the array. Following this is an integer M (1 ≤ M ≤ 10^5), indicating the number of queries. The subsequent M lines each start with a number specifying the type of query: if it is one, a single number x follows, and Sharik needs to find two numbers l and r such that the maximum in the interval [l; r] equals x. If the type is two, two numbers pos and val follow, indicating that the element at position pos in the array should be updated to val. For each query of type one, a line with two numbers l and r is provided as Sharik's response.
Output
For each of Sharik's responses, print "Yes" if his answer is correct, and "No" if he made a mistake. Note that although the previous task required finding the smallest possible l and r, Pechkin will not be checking for that here.