409984: GYM103886 K Terraforming

Timothy has just conquered a cereal planet using his large brain! He immediately decided to terraform it to repurpose it with his spoon for further world domination. However, as the planet is often rains milk, Timothy would like to find out his effect on the planet.

More specifically, the planet is described as an array of $$$n$$$ heights $$$h_1$$$, $$$h_2$$$, $$$\dots$$$ $$$h_n$$$ $$$(0 \le h_i \le n)$$$.

When it rains $$$x$$$ meters of milk, all indices $$$i$$$ such that $$$h_i < x$$$ are "filled with milk".

A lake is defined a continuous series of indices $$$i...j$$$ $$$(1 \le i \le j \le n)$$$ such that all indices $$$k$$$ satisfying $$$i \le k \le j$$$ are filled with milk, and indices $$$i-1$$$ and $$$j+1$$$ are not filled with milk. (Note: indices $$$0$$$ and $$$n+1$$$ are not filled with milk).

Timothy will ask $$$q$$$ queries of $$$2$$$ types. The $$$j$$$-th query begins with an integer $$$t_j$$$, guaranteed to be either $$$1$$$ or $$$2$$$.

If $$$t_j=1$$$, the query will be of the form: $$$1$$$ $$$i$$$ $$$v$$$.

For this query, you should set $$$h_i$$$ to $$$v$$$.

If $$$t_j=2$$$, the query will be of the form: $$$2$$$ $$$x$$$.

For each query of $$$t_j=2$$$, output the number of distinct lakes if it were to rain $$$x$$$ meters.

The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$.

The second line contains $$$n$$$ integers describing $$$h_1$$$, $$$h_2$$$, $$$\dots$$$ $$$h_n$$$.

The third line contains one integer $$$q$$$ $$$(1 \le q \le 2 \cdot 10^5)$$$.

The next $$$q$$$ lines describe $$$q$$$ queries of either $$$1$$$ $$$i$$$ $$$v$$$ or $$$2$$$ $$$x$$$.

For queries of type $$$1$$$, it is guaranteed that $$$1 \le i \le n$$$ and $$$1 \le v \le n$$$.

For queries of type $$$2$$$, it is guaranteed that $$$1 \le x \le n$$$.

For each query of the second type, output the number of distinct lakes.

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

1
1
2

Initially, $$$h = [5, 4, 2, 1, 3]$$$.

When it rains $$$2$$$ meters of milk, index $$$4$$$ is filled with milk, resulting in $$$1$$$ lake, consisting of index $$$4$$$.

When it rains $$$3$$$ meters of milk, indices $$$3$$$ and $$$4$$$ are filled with milk, resulting in $$$1$$$ lake consisting of indices $$$[3, 4]$$$.

Then, $$$h_2$$$ is set to $$$1$$$, resulting in $$$h = [5, 1, 2, 1, 3]$$$.

When it rains $$$2$$$ meters of milk, now indices $$$2$$$ and $$$4$$$ are filled with milk, resulting in $$$2$$$ lakes respectively.

Problem Credits: Eric Hsu