Most of the surface of a certain alien planet is desert, so it rarely rains. All plants living on this planet are cacti. Because it rains so rarely, the cacti have evolved to cooperate with each other to store water.

One region of the planet is a 2D plane with only vertical and horizontal directions. In that region, $N$ cacti stand in a row. The width of each cactus is 1 meter. The heights of the cacti can be different. For landscaping purposes, it is assumed that only the cacti from the $S$-th cactus to the $E$-th cactus remain, and then it rains sufficiently. It is said that water collects in all areas above the cacti where water can be held. In other words, water collects as shown in the figure below. In the figure below, cacti outside the range indicated by the arrows should be considered as having disappeared.

Write a program that takes the heights of the cacti and the range of remaining cacti as input and calculates the amount of collected water as an area. The range of remaining cacti is given at most $Q$ times. The given range is always applied to the initial state where all cacti exist. You must write the following functions.

• void init( int H[] ): A function called exactly once at the beginning. H is an array (vector) of size $N$ that stores the heights of the cacti in order from the leftmost cactus. $N$ is the number of cacti.
• int query( int S, int E ): When only the cacti from the $S$-th to the $E$-th remain, this function should return the amount of collected water as an area when it rains sufficiently. ($1 \le S \le E \le N$) This function is called at most $Q$ times. All calls are independent. That is, the disappearance of cacti in one call is irrelevant to other calls.

Implementation Details

You must submit exactly one file named cactus.cpp. This file must implement the following functions:

• void init( int H[] )
• long long query( int S, int E )

These functions must operate as described above. You may, of course, create other functions to use internally. The submitted code must not perform input/output or access other files.

Examples

The provided grader receives input in the following format:

• Line 1: $N, Q$.
• Next line: $N$ natural numbers, which are the heights of the cacti in order from the left.
• Next $Q$ lines: 2 natural numbers $S, E$, meaning it rained with only the cacti from the $S$-th to the $E$-th remaining. ($1 \le S \le E \le N$)

The provided grader prints the values returned by your query() function, one per line.

Constraints

• $1 \le N \le 500,000$, $1 \le Q \le 500,000$, cactus heights are between $1$ and $10^9$.

Subtasks

• Subtask 1 [13 points]: $1 \le N \le 5,000$, $1 \le Q \le 5,000$
• Subtask 2 [12 points]: $1 \le N \le 5,000$
• Subtask 3 [22 points]: Cactus heights are $20$ or less
• Subtask 4 [34 points]: $1 \le N \le 100,000$, $1 \le Q \le 100,000$
• Subtask 5 [69 points]: No additional constraints other than the original constraints

Examples

Input 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

Output 1

6
1
0

Note

The execution example based on how your code operates for the input above is shown below.