### PROBLEM LINK:

**Author:** Vamsi Kavala

**Tester:** Anton Lunyov

**Editorialist:** Anton Lunyov

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

### PROBLEM:

Getting rid of the storyline and special input format, the problem can be formulated as follows. You are given an array **A[1], …, A[N]** and a number **C**. Denote **osc[i, j] = max(A[i], …, A[j]) − min(A[i], …, A[j])** (**osc** is due to oscillation). Further, denote by **F[k]**, where **1 ≤ k ≤ N**, the number of those **i** from **1** to **N − k + 1** for which **osc[i, i + k − 1] ≤ C**. You are also given several values of **M**. For each of these values you need to find the smallest **k** such that **F[k] ≤ M** and the corresponding value **F[k]**.

### QUICK EXPLANATION:

Denote by **beg[i]**, where **1 ≤ i ≤ N**, the smallest positive number for which **osc[beg[i], i] ≤ C**. Values **beg[i]** can be found in **O(N)** using two deques like in sliding RMQ. Denote by **cnt[j]** the number of those **i** for which **i − beg[i] + 1 = j**. Then, **F[k] = cnt[k] + … + cnt[N]**. After that the queries can be answered in **O(log N)** time using binary search. Alternatively one can compute answers for all queries in **O(N)** time and answer them in **O(1)** time after that.

### EXPLANATION:

Note, that if the segment **[i<sub>1</sub>, j<sub>1</sub>]** lies inside the segment **[i<sub>2</sub>, j<sub>2</sub>]**, that is, **i _{2} ≤ i_{1} ≤ j_{1} ≤ j_{2}**, then

**osc[i<sub>1</sub>, j<sub>1</sub>] ≤ osc[i<sub>2</sub>, j<sub>2</sub>]**. Hence

**beg[i] ≤ beg[i +1]**. Indeed, if

**beg[i] > beg[i +1]**then

**osc[beg[i +1], i] ≤ osc[beg[i +1], i + 1] ≤ C**. So

**beg[i]**is not the smallest index satisfying the property

**osc[j, i] ≤ C**.

It allows us to use the following method to find **beg[i]** for all **i**. Initially we have **beg[1] = 1**. Consider some **i > 1** and assume that **beg[i − 1]** is already found. Then we move the index **j** starting from **beg[i − 1]** forward and check the condition **osc[j, i] ≤ C**. We assign **beg[i] = j** for the first index **j** which satisfies this condition. It is clear, that the total number of checks we perform is **O(N)**. So with naive check of condition **osc[j, i] ≤ C** we obtain **O(N * N)** solution.

To obtain an **O(N)** solution we need data structure that allows to answer the following queries in **O(1)** time in average. We have two pointers **j** and **i**. At each time we can either increase **i** by one, increase **j** by one (but only if **j** was less than **i**), or need to find minimum and maximum among the numbers **A[j], …, A[i]**. In average here means that **Q** such queries can be answered in **O(Q)** time. Then the previous solution can be represented by the following pseudo-code

i = 1 j = 1 while i <= N while osc[j, i] <= C // query of the 3rd type increase j by 1 // query of the 2nd type assign beg[i] = j increase i by 1 // query of the 1st type

The proper data structure for this is two deques **minQ** and **maxQ** of successive minimums and maximums in the sequence **A[i], A[i − 1], …, A[j]**. Namely, the head element **minQ[1]** of **minQ** will be **i**, the second element **minQ[2]** will be the largest index **h < i** such that **A[h] < A[i]**. In general **minQ[k]** is the largest positive integer **h < minQ[k − 1]** such that **A[h] < A[minQ[k − 1]]**. For the last (tail) element of **minQ** there will be no such **h ≥ j**. Note, that **minQ** can contain only one element **i** in some situations. The deque **maxQ** is defined in a similar way.

We will use C++ syntax for standard deque operations (see here).

The queries can be implemented now as follows. We consider only how **minQ** will be affected. **maxQ** will be changed in a similar way.

For the first query (increase **i** by one) we should possibly remove first several elements in **minQ** until the condition **A[minQ[1]] < A[i]** will be satisfied and after that make **i** as a head element:

query1() i = i + 1 while minQ is non-empty and A[minQ.front()] ≥ A[i] minQ.pop_front() minQ.push_front(i)

For the second query (increase **j** by one) we should simply remove the last element if it coincides with **j**:

query2() if minQ.back() = j then minQ.pop_back() j = j + 1

Finally, for the third query (take minimum) we need to take the last element of **minQ**:

query3() return A[minQ.back()]

It seems that such solution can have complexity **O(N * Q)** for answering **Q** queries due to the loop in the `query1()`

but it is easy to see that since we always increase either **i** or **j**, we add and delete each index from **1** to **N** at most once in our deques. So the total number of operations performed in these loops during all queries is at most **2 * N**.

Alternatively you can check CHEFTOWN - editorial or this article for another exposition of this method.

Now when we find **beg[i]** for all **i** we can find **cnt[k]** for all **k** in one simple loop after proper initialization:

for k = 1 to N do cnt[k] = 0 for i = 1 to N do increase cnt[i – beg[i] + 1] by 1

Clearly, **F[k]** is the number of those **i** for which **osc[i − k + 1, i] ≤ C**. Due to definition of **beg[i]** this is equivalent to **beg[i] ≤ i − k + 1** or **i − beg[i] +1 ≥ k**. Clearly, the number of such **i** equals to **cnt[k] + … + cnt[N]**. Hence **F[k] = cnt[k] + … + cnt[N] = cnt[k] + F[k + 1]** and can be found in one simple loop:

F[N] = cnt[N] for k = N – 1 downto 1 F[k] = cnt[k] + F[k + 1]

As was mentioned, now to answer the queries we can either use binary search (see author’s solution) or compute all answers in **O(N)** time and answer the queries in **O(1)** time (see tester’s solution).

### ALTERNATIVE SOLUTION:

Instead of using deques that we discuss above, which may appear to be quite unusual for many of you, some more standard data structures can be used.

For example, balanced binary search tree allows to perform each query in **O(log N)** time. So we get **O(N * log N)** solution. Namely, now `query1()`

is inserting the pair **(A[i], i)** into the tree, `query2()`

is deleting the pair **(A[j], j)** from the tree and `query3()`

as before is finding of minimum of maximum. It shouldn’t pass within the time limit but some contestants cram it after proper optimizations. You can use STL set in C++ or TreeSet in Java as a ready to use implemented balanced binary search tree.

Another approach is to use segment tree. It can be constructed in **O(N)** time, needs **O(N)** memory and allows to find minimum or maximum on the segment in **O(log N)** time. So our main pseudo-code for the solution remains the same but each **osc[j, i]** will require **O(log N)** time. The entire solution will have a complexity **O(N * log N)** and shouldn’t pass the time limit. But again, after proper optimizations maybe it is possible to cram it within the time limit.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

### RELATED PROBLEMS:

CHEFTOWN

SPOJ - 7739. Sound - BOI7SOU

Timus - 1126. Magnetic Storms

UESTC - 1221. Sliding Window