F. Lantern Hopping
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Xinyu the dragon is excited to attend the Lunar New Year festival to welcome in the new year!

At the festival there are $$$n$$$ lanterns lined up in a row, with the $$$i$$$th lantern being at height $$$a_i$$$. Xinyu the dragon loves hopping around on the lanterns, but he can only hop to adjacent lanterns that are the same height as the lantern he is currently on.

Fortunately, his powers of firebreathing give him the ability to do the following any number of times as he hops about:

  • If his energy is above 0, consume 1 unit of energy to breathe fire into the lantern he is currently on, raising the lantern's height by 1.
  • Absorb some fire from the lantern he is currently on, gaining 1 unit of energy and lowering the lantern's height by 1.
Note: Xinyu's energy can be 0, but it cannot ever be allowed to go below 0.

Xinyu's goal is to pick some lantern to start on and then hop around to visit all of the lanterns. He is curious about how much energy he needs to do so, so he will ask you questions over time of the form $$$1\ p$$$, meaning he wants to know if he starts at lantern $$$p$$$, what is the minimum energy he needs to start with to be able to visit all the lanterns.

Additionally, as the festival progresses, the heights of individual lanterns may fluctuate, and these events will be presented in the form $$$2\ p\ x$$$, meaning that lantern $$$p$$$ now has a new height of $$$x$$$.

Please process each event and help answer Xinyu's questions as the festival progresses!

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n, q\leq 2\cdot10^5)$$$ — the number of lanterns and the number of events.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (0\leq a_i\leq 10^9)$$$ — the starting heights of each lantern in the row.

Each of the following $$$q$$$ lines will describe an event in one of the following formats:

  • $$$1\ p\ (1\leq p\leq n)$$$
  • $$$2\ p\ x\ (1\leq p\leq n,\ 0\leq x\leq 10^9)$$$
The first type of event means Xinyu is asking a question about lantern $$$p$$$, and the second type of event means lantern $$$p$$$ now has a height of $$$x$$$.

There is guaranteed to be at least one event of the first type.

Output

For each question that Xinyu asks, please print the answer on its own line.

Examples
Input
3 2
3 1 3
1 1
1 2
Output
0
2
Input
2 5
1000000000 0
1 2
2 2 10
1 2
2 1 10
1 2
Output
1000000000
999999990
0
Note

In the first test case, if Xinyu starts on lantern 1 with 0 energy, he can absorb fire 2 times to decrease the lantern's height by 2 and increase his energy by 2, then hop to lantern 2, spend 2 energy to raise its height from 1 to 3, then hop to lantern 3.

If he starts on lantern 2 with 2 energy, he can spend 2 energy to raise its height from 1 to 3, then hop freely to lanterns 1 and 3.