While wandering around the city, Molly got distracted by a drone shop, and went in. In the shop there where ~Q~ drones available for purchase. Molly lives in a city where there are ~N~ building in a line, each with specific heights ~h_i~. 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, ~x_k~ and ~y_k~.
For all subtasks:
- ~1 \le h_i \le 1\,000\,000~ where ~1 \le i \le N~
- ~1 \le x_k \le y_k \le 1\,000\,000~ where ~1 \le k \le Q~
Subtask 1 [5%]
Subtask 2 [25%]
- ~1 \le N \le 1\,000~
- ~1 \le Q \le 15\,000~
Subtask 3 [70%]
- ~1 \le N \le 1\,000\,000~
- ~1 \le Q \le 100\,000~
The first line of input will contain two space-separated integers, ~N~ and ~Q~.
The second line of input will contain ~N~ space-separated integers, ~h_i~ where ~1 \le i \le N~.
The next ~Q~ lines of input will each contain two space-separated integers, ~x_k~ and ~y_k~.
Note: Fast I/O methods are recommended for this problem.
Your program should output ~Q~ integers on different lines, representing the number requested for each drone.
5 1 3 2 4 5 3 3 4