While wandering around the city, Molly got distracted by a drone shop, and went in. In the shop there where drones available for purchase. Molly lives in a city where there are building in a line, each with specific heights . Being cheap, the drones from this shop have some weird technical specifications, the height interval that they need to start from. With this in mind, Molly asks you to tell her how many contiguous subsequences of buildings have the shortest building in the specified range of each drone, and .

#### Constraints

For all subtasks:

- where
- where

##### Subtask 1 [5%]

##### Subtask 2 [25%]

##### Subtask 3 [70%]

#### Input Specification

The first line of input will contain two space-separated integers, and .

The second line of input will contain space-separated integers, where .

The next lines of input will each contain two space-separated integers, and .

**Note**: Fast I/O methods are recommended for this problem.

#### Output Specification

Your program should output integers on different lines, representing the number requested for each drone.

#### Sample Input

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

#### Sample Output

`6`

## Comments

RTE bad_allocI am using Segment Tree to solve this problem. However, it is giving me RTE (std::bad_alloc), despite the fact that I only used 54.9 MB. I was wondering why this is happening, and how I may fix this issue? Thank you!

maybe try pre allocating the thing

nvm

Will there be some short editorials or write-ups?

Hi. Although I am just a contestant and I don't know about the editorials, I would like to share my solution, which I hope it helps.

It is obvious that no ranges can include elements less than , and thus, my first idea is to breaking the cities into several parts, only parts of contiguous ranges that no elements are less than .

By considering arrays with no elements less than . It is easy to observe that the number of valid subarrays is the number of subarrays can be built, minus the number of subarrays with all elements greater than .

Using the above observations, we can precompute the number of subarrays with all elements greater than for each . Let's denote this result as . And thus, the answer for each query is .

Thank You.

If I submit multiple solutions will all of them be counted during system tests or just the last one?

All submissions made during your contest window will be judged on system tests. Your score will be based on the highest scoring submission.

Edit: However, resubmitting can increase the time for the problem, which is considered when tie-breaking contestants with the same number of points.

If I submit at 1:00:00 and submit again at 1:30:00, and actually both passes system test, which submission is considered?

If multiple submissions have the same score, the system currently considers the one with the latest time, so the 1:30:00 submission will be used.

is the entire sequence not a subsequence?

edit: I cant read