Tahp is studying a way to represent a permutation^∗ by an array of integers. Specifically, consider a permutation ~p_1, p_2, \ldots, p_n~ of the integers from ~1~ to ~n~. For each position ~i~, Tahp defines a value ~f_i~ as follows:

$$f_i = |\{j \mid 1 \le j < i,\ p_j < p_i\}|$$

In other words, ~f_i~ is the number of elements before position ~i~ in the permutation ~p~ whose value is smaller than ~p_i~.

For example, if ~p = [2, 6, 4, 1, 5, 3]~, then:

• ~f_1 = 0~, because there are no elements before position ~1~.

• ~f_2 = 1~, because before ~p_2 = 6~ there is one smaller element, namely ~2~.

• ~f_3 = 1~, because before ~p_3 = 4~ there is one smaller element, namely ~2~.

• ~f_4 = 0~, because before ~p_4 = 1~ there are no smaller elements.

• ~f_5 = 3~, because before ~p_5 = 5~ there are three smaller elements, namely ~2, 4, 1~.

• ~f_6 = 2~, because before ~p_6 = 3~ there are two smaller elements, namely ~2, 1~.

Thus, the array ~f~ corresponding to the permutation above is ~[0, 1, 1, 0, 3, 2]~.

Clearly, for every permutation ~p~, the resulting array ~f~ always satisfies: ~0 \le f_i < i~. Interestingly, the converse is also true. For every array of integers ~f_1, f_2, \ldots, f_n~ satisfying ~0 \le f_i < i~, it can be proven that there exists a unique permutation ~p_1, p_2, \ldots, p_n~ such that the array ~f~ is defined from ~p~ by the formula above.

In this problem, you are given the initial array ~f~. Then, the array ~f~ will change through update operations. After each update, the data always guarantees that the array ~f~ still satisfies ~0 \le f_i < i~, so the permutation corresponding to the current array ~f~ always exists and is unique.

You need to process ~q~ operations. Each operation is of one of the following three types:

• + i: increase ~f_i~ by ~1~.

• - i: decrease ~f_i~ by ~1~.

• ? l r: consider the unique permutation ~p~ corresponding to the current array ~f~, and output the value ~p_l + p_{l+1} + \cdots + p_r~.

∗ A permutation of length ~n~ is an array of ~n~ integers, in which each integer from ~1~ to ~n~ appears exactly once.

Input

The first line contains two integers ~n~ and ~q~ ~(2 \le n \le 5 \cdot 10^5;\ 1 \le q \le 5 \cdot 10^5)~ — the length of the array ~f~ and the number of operations.

The second line contains ~n~ integers ~f_1, f_2, \ldots, f_n~ ~(0 \le f_i < i~ for all ~1 \le i \le n)~.

Each of the next ~q~ lines describes one operation of one of the following three types:

• + i ~(1 \le i \le n)~: increase ~f_i~ by ~1~.

• - i ~(1 \le i \le n)~: decrease ~f_i~ by ~1~.

• ? l r ~(1 \le l \le r \le n)~: ask for the sum ~p_l + p_{l+1} + \cdots + p_r~, where ~p~ is the unique permutation corresponding to the current array ~f~.

It is guaranteed that at all times, the array ~f~ satisfies ~0 \le f_j < j~ for all ~1 \le j \le n~, and that there is at least one query operation ?.

Output

For each operation of type ? l r, output on a separate line an integer equal to ~p_l + p_{l+1} + \cdots + p_r~, where ~p~ is the unique permutation corresponding to the current array ~f~.

Scoring

Sample Input 1

6 10
0 1 1 0 3 2
? 2 5
+ 4
- 5
+ 3
- 2
? 1 4
+ 6
- 4
+ 5
? 2 5

Sample Output 1

16
14
14

Notes

Initially, the array ~f~ is ~[0, 1, 1, 0, 3, 2]~. The corresponding permutation is ~p = [2, 6, 4, 1, 5, 3]~. Therefore, the query ? 2 5 has answer ~p_2 + p_3 + p_4 + p_5 = 6 + 4 + 1 + 5 = 16~.

After the operations + 4, - 5, + 3, - 2, the array ~f~ becomes ~[0, 0, 2, 1, 2, 2]~. The corresponding permutation is now ~p = [5, 1, 6, 2, 4, 3]~. Therefore, the query ? 1 4 has answer ~p_1 + p_2 + p_3 + p_4 = 5 + 1 + 6 + 2 = 14~.

After the operations + 6, - 4, + 5, the array ~f~ becomes ~[0, 0, 2, 0, 3, 3]~. The corresponding permutation is now ~p = [3, 2, 6, 1, 5, 4]~. Therefore, the final query ? 2 5 has answer ~p_2 + p_3 + p_4 + p_5 = 2 + 6 + 1 + 5 = 14~.