405437: GYM101962 I Colonial Mansions

After a year of hard work, Mano finally had a month off. He decided to take his grandmother to Soteropolis during this time. As soon as they arrived at the airport, Mano bought one of these "10 things to do in Soteropolis" travel guides. His grandmother instantly felt in love with pictures of the colonial mansions of Pelourinho, a historic neighborhood in western Soteropolis.

Pelourinho is a very big neighborhood. It is full of slopes and can be very trick for an elderly lady to explore. We can simplify its structure by imagining it as a line. The colonial mansions can be imagined as equally spaced spots on these lines: that is, from the $$$i$$$-th mansion (from left to right), you can go to mansions $$$i-1$$$ and $$$i+1$$$, if such mansions exist. These mansions are called neighbors of mansion $$$i$$$. Also, the $$$i$$$-th mansion is $$$h_i$$$ meters above sea level.

Mano knows that his grandmother will have serious difficulties in this kind of terrain. Your task is to write a computer program to answer some queries and help Mano plan his trip to Pelourinho. The two types of queries are described below:

• 1 $$$i$$$ $$$H$$$: the height of the $$$i$$$-th mansion should be set to $$$H$$$;
• 2 $$$i$$$ $$$H$$$: how many mansions Mano and his grandmother can visit if they start their trip at mansion $$$i$$$ and his grandmother can handle going from a mansion $$$u$$$ to a neighbor mansion $$$v$$$ iff $$$|h_u - h_v| \leq H$$$?

Write a program to process these queries.

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^5$$$) - the number of colonial mansions and the number of queries you are asked to process, respectively.

The second line of the input contains $$$n$$$ integers. The $$$i$$$-th of them is $$$h_i$$$ ($$$0 \leq h_i \leq 10^{9}$$$) – the height above the sea level of the $$$i$$$-th mansion.

The next $$$q$$$ lines of the input will each describe a query, which will have the format shown in the statement ($$$1 \leq i \leq n$$$; $$$0 \leq H \leq 10^9$$$).

For each operation of type 2, print a line with an integer – the number of colonial mansions Mano and his grandmother can visit in such scenario.

The queries should be processed in the order they are given in the input file.

4 3
1 2 1 3
2 2 1
1 4 1
2 3 1

3
4

4 5
1 10 2 11
2 3 1
2 4 1
1 3 8
2 2 3
2 1 9

1
1
3
4