### PROBLEM LINK:

**Author:** Rishabh

**Tester:** Kevin Charles Atienza

**Editorialist:** Vaibhav Tulsyan

### DIFFICULTY:

Medium

### PREREQUISITES:

Stacks, Binary Search

### PROBLEM:

For an array of N integers, you are asked to answer M queries. In each query, you are asked the first number in the p^{th} sub-array,

after sorting all numbers in each sub-array in descending order and then sorting the sub-arrays in descending order.

### QUICK EXPLANATION:

For each i (1 \le i \le N), calculate the number of subarrays for which a_i is the maximum element.

Store indexes j (1 \le j \lt i) and k (i + 1 \le k \le N), such that:

- a_j > a_i
- a_k > a_i
- All integers between i and j are smaller than a_i.
- All integers between i and k and smaller than a_i.

Number of subarrays for which a_i is max is equal to (i - j) * (k - i).

Sort the elements in descending order and maintain a cumulative sum of no. of subarrays uptil the i^{th} index.

Use binary search to find the value associated with the p^{th} sub-array.

### EXPLANATION:

**Subtask 1:**

- Iterate over all possible sub-arrays of length 1, 2, 3, ... , N.
- After fixing the end-points, iterate over the array to find the maximum element.
- Store the maximum element of each subarray in a list L.
- Sort L in descending order.
- The maximum element of the p^{th} sub-array would be the p^{th} element in this list L.

Complexity: O(N^3 + N^2.log_2(N) + M)

This naive solution would time out for Subtasks 2 and 3 and would hence fetch only 20 points.

**Subtask 2:**

- Maintain a list L to store the maximum values of all sub-arrays.
- Iterate over all possible sub-arrays by fixing the end-points of the array, say X and Y.
- Keep a running maximum element present in all sub-arrays whose left boundary is X.
- For each sub-array, store the newly computed maximum in the list L.
- Sort L in descending order.
- The maximum element of the p^{th} sub-array would be the p^{th} element in this list L.

Complexity: O(N^2 + N^2.log_2(N) + M)

This solution would give a total of 50 points.

**Subtask 3:**

In order to find the number of subarrays whose max is a_i, we can make a useful observation.

For each i, we can determine a left boundary j and a right boundary k such all integers a_x (j \lt x \lt i) and a_y (i \lt x \lt k)

are less than or equal to a_i.

In other words, let [j+1 .. k-1] represent the longest segment in which no element is greater than a_i.

Then, the no. of sub-arrays in which a_i is maximum is equal to (i - j) * (k - i).

*How do we find these boundaries for all i in O(N) or O(N.log(N)) time?*

We will use a stack to find the boundaries.

Let’s try to find only the *left boundary* for each i first.

If the current element being processed, say Z, is less than or equal to the element at the top of the stack, say T,

then the left boundary of Z would be the index of T.

Otherwise, we keep popping elements from the stack until we find a suitable boundary.

Pseudo-code:

```
stack = [-1]
left_boundary = [null for i in (1..n)]
for i in [1..n]:
while (stack is not empty) and (stack.top <= a[i]):
stack.pop()
left_boundary[i] = stack.top
stack.push(i)
```

Similarly, we can also compute the right boundary for each i.

We have computed the boundaries of all i in O(N) time. This was the slowest step in our previous naive solutions.

Now, we need to store the no. of subarrays for which each a_i is maximum, and sort this list in descending order of a_i.

The next question is: how do we find the maximum element associated with the p^{th} sub-array?

Since N can be 10^5, the number of subarrays can be of the order 10^10. A linear search would result in TLE.

If we maintain a cumulative sum of the no. of subarrays processed in this sorted list, we will get a monotonically increasing sequence.

We can apply binary search on this sequence to find the required answer.

Pseudo-code:

```
data = [(a[1], count[1]), (a[2], count[2]), ... , (a[k], count[k])]
for i in [1..len(data) - 1]:
count[i + 1] += count[i]
for query in [1..m]:
p = input()
low = 0, high = n
while high - low > 1:
mid = (low + high) >> 1
if count[mid] > p:
low = mid
else:
high = mid
return a[high]
```

Complexity: O(N + log_2(N)

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

Setter’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.