Description

In Boai’s Fujin Forest Park, there is a long Fujin mountain range made up of giant rocks lined up and numbered from $1$ to $N$. Each rock has an elevation. The mountain range lies in a basin that can hold water, and the water has its own elevation. All rocks strictly lower than this water elevation will be submerged and hidden beneath the surface.

Due to crustal movements, rock elevations may change at any time, with a single rock taking on a new elevation. Of course, the water level may also change at any time.

Because of this geological wonder, many tourists visit. As a visitor, uim can tell you the current water level elevation, and you must tell him how many contiguous visible parts there are on the mountain range. (Rocks exactly at the water level are also considered visible.)

Input Format

The first line contains two integers $N$ and $M$, representing $N$ rocks and $M$ queries.

The next line contains $N$ integers $A_i$ representing the initial elevation of each rock.

Then follow $M$ lines. Each line has two or three numbers:

• If the first number is 1, it is followed by a single $B_j$, representing the water level elevation.
• If the first number is 2, it is followed by two integers $C_j$ and $D_j$, meaning the elevation of rock numbered $C_j$ becomes $D_j$.

Output Format

For each 1 query, output a single integer: the number of contiguous visible segments.

5 4
8 6 3 5 4
1 5
2 4 1
1 5
1 3

2
1
2

Hint

• For $10\%$ of the testdata, $N, M \le 2000$.
• Additionally, for $30\%$ of the testdata, there are only 1 queries.
• For $100\%$ of the testdata, $1 \le N, M \le 200000$, $1 \le A_i, B_j, D_j \le 10^9$, and there is at least one 1 query.

Translated by ChatGPT 5