Range Minimum Query#3615
The Giggle company opens their office in Elmsford and you are invited to interview. Your task is to solve the given problem.
You need to create a data structure that stores an array of integers. Initially, the array is empty. You need to support two operations:
query: "? " - returns the minimum element between the -th and -th inclusively;
update: "+ " - add element after the -th element in array. If = , the element is added to the beginning of array.
Of course, this structure should be good enough.
The first line contains the number of operations (1 \leq n \leq 200000) on array. Next lines describe the operations. All update operations are correct. All numbers stored in the array do not exceed 10^9 in absolute value.
For each operation ? print on a separate line its result.
Example 1