Palm trees
Palm trees are very beautiful trees, usually associated with vacations and warm climates. There are different species of palm trees, but almost all of them live in tropical or subtropical areas, where there are no cold winters.
The government of Macedonia decided to make the entire coast of Ohrid full of palm trees. Unfortunately, after the planting of the trees, some of them managed to grow much taller than others. Macedonians don't like all of their trees to have the same height (because that is boring), so they're pretty happy with the fact that all trees don't look the same (i.e. some are tall, some moderate and some short).
In order to make the coast even more interesting, the government wants to analyze how pretty some parts of the coast are, and what will happen if we replace some tree with a tree which is taller or shorter than the one that is already there. In particular, we're interested in intervals of trees which alternate in height (for example, if the second tree is strictly taller than the first tree, the third tree should be strictly shorter than the second tree, the fourth tree should be taller than the third tree, etc.). For example, 3 5 2 7 6 8 5 is a valid alternating interval, because 3 < 5 > 2 < 7 > 6 < 8 > 5.
Given that we know the height of every palm tree on the coast, and their order from left to right, we want to create a program that can execute the following queries:
REPLACE X H - Replace the tree on position X, with a tree which has height H.
COUNT A B - Check the interval of trees between positions A and B (inclusive). Calculate what is the minimum number of trees that we need to remove, so that the trees that remain (the ones that aren't removed) alternate in height?
Can you write a program that can quickly execute the queries given above?
Input
The first line of input contains two integers: N (1 <= N <= 200 000), the number of trees on the coast, and Q (1 <= Q <= 20 000), the number of queries.
In the second line, there are N integers Ti (1 <= Ti <= 1 000 000), which indicate the height of each tree (from left to right).
Each of the following Q lines contains one of the queries:
REPLACE X H (where 1 <= X <= N, and 1 <= H <= 1 000 000)
COUNT A B (where 1 <= A <= B <= N).
Output
The output consists of several lines: one for each COUNT query. The answer for each COUNT query is an integer (the number of trees that need to be removed), and the queries must be answered in the same order that they're given in the input.
Constraints
Time limit: 1 second
Memory limit: 256 megabytes
Examples
input 7 10 3 5 2 7 6 8 5 COUNT 1 2 COUNT 1 7 COUNT 4 7 REPLACE 3 8 COUNT 1 7 REPLACE 3 4 REPLACE 5 7 REPLACE 6 4 COUNT 1 7 COUNT 1 1 | output 0 0 0 2 1 0 |
The first REPLACE query replaces the third palm tree with a new one with height 8. After the execution of this query, the state of the coast is 3 5 8 7 6 8 5.
After the execution of the second REPLACE query, the state of the coast is 3 5 4 7 6 8 5.
After the execution of the third REPLACE query, the state of the coast is 3 5 4 7 7 8 5.
After the execution of the fourth REPLACE query, the state of the coast is 3 5 4 7 7 4 5.
Scoring
- In test cases worth at least 10% of all points, 1 <= N <= 10 and 1 <= Q <= 100.
- In test cases worth an additional 40% of all points, 1 <= N <= 500 and 1 <= Q <= 100.