Problems
Range Minimum Query
Range Minimum Query
The Giggle company opens their office in Sudislavl 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: "**? i j**" - returns the minimum element between the
i
-th andj
-th inclusively; - update: "**+ i x**" - add element x after the i-th element in array. If i = 0, the element is added to the beginning of array.
Of course, this structure should be good enough.
Input
The first line contains the number of operations n (1 ≤ n ≤ 200000) on array. Next n lines describe the operations. All update operations are correct. All numbers stored in the array do not exceed 109
.
Output
For each operation ? print on a separate line its result.
Input example #1
8 + 0 5 + 1 3 + 1 4 ? 1 2 + 0 2 ? 2 4 + 4 1 ? 3 5
Output example #1
4 3 1