Giggle opens its new office in Sudislavl and you are invited for an interview. Your task — solve the problem.
You need to create a data structure that is an array of integers. The array is initially empty. You need to support two operations:
- request: "
? i j» — returns the minimum element between the i-th and j-th, inclusive;
- change: "
+ i x" — add element x after i-th element of the list. If i=0, then the element is added to the beginning of the array.
Of course, this structure should be good enough.
Input
The first line of the input file contains a single integer n — number of operations on the array (1<=n<=200000). The following n lines describe the operations themselves. All add operations are valid. All numbers stored in the array do not exceed 109.
Output
For each operation print its result on a separate line.
Comment to example tests
The following table shows the process of changing the array from the example.
| Operation |
Array after its execution |
| originally |
empty |
+ 0 5 |
5 |
+ 1 3 |
5, 3 |
+ 1 4 |
5, 4, 3 |
+ 0 2 |
2, 5, 4, 3 |
+ 4 1 |
2, 5, 4, 3, 1 |
Examples
| # |
Input |
Output |
| 1 |
8
+ 0 5
+ 1 3
+ 1 4
? 12
+ 0 2
? 24
+ 4 1
? 3 5
|
4
3
1
|