Most of the surface of an alien planet is desert, so it rarely rains. All plants on this planet are cacti. Since rain is so scarce, the cacti have evolved a way to cooperate to store water.

One region of the planet is a two-dimensional plane with only up-down and left-right directions. In this region, $N$ cacti stand side by side in a row. Each cactus is $1$ meter wide, and their heights may differ. For landscaping, only cacti $S$ through $E$ are left. Then enough rain falls to fill every area above the cacti that can hold water. Water collects as shown below. In the figure, assume that all cacti outside the range marked by arrows have been removed.

Write a program that takes the cactus heights and a range of surviving cacti, and computes the trapped water as an area. At most $Q$ ranges are given. Each range is always applied to the initial state in which all cacti exist.

You must implement the following functions.

• void init( int H[] ): Called exactly once at the beginning. $H$ is an array (vector) of size $N$, containing the cactus heights in order from left to right. $N$ is the number of cacti.
• int query( int S, int E ): Return the area of water trapped after sufficient rain falls when only cacti $S$ through $E$ remain ($1 \le S \le E \le N$). This function is called at most $Q$ times. All calls are independent: removing cacti in one call has no effect on another.

Implementation Details

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 behave as described above. You may define and use other functions internally. Your submitted code must not perform input or output or access other files.

Sample grader

The provided grader reads input in the following format.

• Line 1: $N$, $Q$.
• Next line: $N$ positive integers, the cactus heights from left to right.
• Next $Q$ lines: two positive integers $S,E$, meaning that rain falls with only cacti $S$ through $E$ remaining ($1 \le S \le E \le N$).

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

Constraints

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$; each cactus height is at least $1$ and at most $10^9$.

Subtasks

Subtasks 1 (13 points)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

Subtasks 2 (12 points)

• $1 \le N \le 5\,000$

Subtasks 3 (22 points)

• Each cactus height is at most $20$.

Subtasks 4 (34 points)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

Subtasks 5 (69 points)

• No additional constraints beyond the original constraints.

Examples

Input 1

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

Note

An example execution of your code on the input above is shown below.