Three from Prostokvashino 3#4493
- 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.
The first line contains a single integer (1 \leq N \leq 10^6), representing the number of elements in the array. The next line contains non-negative integers, each not exceeding 10^9, which are the elements of the array. Following this is an integer (1 \leq M \leq 10^5), indicating the number of queries. The subsequent lines each start with a number specifying the type of query: if it is , a single number follows, and Sharik needs to find two numbers and such that the maximum in the interval [l; r] equals . If the type is , two numbers and follow, indicating that the element at position in the array should be updated to . For each query of type , a line with two numbers and is provided as Sharik's response.
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 and , Pechkin will not be checking for that here.
Example 1