Background

This is an interactive problem, but here you should submit a complete program.

Problem Description

There are $N$ mountains arranged in a horizontal line, numbered from $0$ to $N-1$ from left to right. The height of mountain $i$ is $H_i$ ($0\leq i\leq N-1$). Exactly one person lives on the top of each mountain.

You plan to hold $Q$ meetings, numbered from $0$ to $Q-1$. The participants of meeting $j$ ($0\leq j\leq Q-1$) are the people living on mountains from $L_j$ to $R_j$ (including $L_j$ and $R_j$) ($0\leq L_j\leq R_j\leq N-1$). For this meeting, you must choose some mountain $x$ as the meeting location ($L_j\leq x\leq R_j$). The cost of holding the meeting depends on your choice, and is computed as follows:

• The cost for each participant coming from a mountain $y$ ($L_j\leq y\leq R_j$) equals the maximum height among all mountains between $x$ and $y$ (including $x$ and $y$). In particular, the cost for the participant from mountain $x$ is $H_x$, i.e. the height of mountain $x$.

• The cost of the meeting equals the sum of the costs of all its participants.

You want to hold each meeting with the minimum possible cost.

Note that all participants return to their own mountains after each meeting, so the cost of a meeting is not affected by previous meetings.

Input Format

The first line contains two positive integers $N$ and $Q$, as described above.

The second line contains $N$ positive integers $H_0,H_1,\cdots, H_{N-1}$, representing the heights of the mountains.

Line $3+j$ ($0\leq j\leq Q-1$) contains two integers $L_j, R_j$, describing the participant range of the meeting.

Output Format

Output $Q$ lines. Line $1+j$ ($0\leq j\leq Q-1$) contains one integer $C_j$, the minimum possible cost of holding meeting $j$.

4 2
2 4 3 5
0 2
1 3

10
12

3 3
2 1 2
0 0
0 1
0 2

2
3
5

5 1
1000000000 1000000000 1 1000000000 1000000000
0 4

4000000001

15 10
10 71 84 33 6 47 23 25 52 64 70 31 22 31 2
5 10
3 7
0 13
8 12
0 0
1 3
7 13
1 13
10 12
1 1

281
180
828
263
10
201
364
744
123
71

Hint

Explanation of Sample #1

Meeting $j=0$ has $L_j=0$ and $R_j=2$, so it will be attended by the people living on mountains $0$, $1$, and $2$. If mountain $0$ is chosen as the meeting location, the cost of meeting $0$ is computed as follows:

• The cost for the participant from mountain $0$ is $\max\lbrace H_0\rbrace=2$.
• The cost for the participant from mountain $1$ is $\max\lbrace H_0,H_1\rbrace=4$.
• The cost for the participant from mountain $2$ is $\max\lbrace H_0,H_1,H_2\rbrace=4$.
• Therefore, the total cost of meeting $0$ is $2+4+4=10$.

It is not possible to hold meeting $0$ at a lower cost, so the minimum cost of meeting $0$ is $10$.

Meeting $j=1$ has $L_j=1$ and $R_j=3$, so it will be attended by the people living on mountains $1$, $2$, and $3$. If mountain $2$ is chosen as the meeting location, the cost of meeting $1$ is computed as follows:

• The cost for the participant from mountain $1$ is $\max\lbrace H_1,H_2\rbrace=4$.
• The cost for the participant from mountain $2$ is $\max\lbrace H_2\rbrace=3$.
• The cost for the participant from mountain $3$ is $\max\lbrace H_1,H_2,H_3\rbrace=5$.
• Therefore, the total cost of meeting $1$ is $4+3+5=12$.

It is not possible to hold meeting $1$ at a lower cost, so the minimum cost of meeting $1$ is $12$.

Constraints

• $1\leq N\leq 750\space000$
• $1\leq Q\leq 750\space000$
• $1\leq H_i\leq1\space000\space000\space000$
• $0\leq L_j\leq R_j\leq N-1(0\leq j\leq Q-1)$
• $(L_j,R_j)\neq(L_k,R_k)(0\leq j<k\leq Q-1)$

Subtasks

1. (4 points) $N\leq3000,Q\leq10$.
2. (15 points) $N\leq5000,Q\leq5000$.
3. (17 points) $N\leq100\space000,Q\leq100\space000,H_i\leq2(0\leq i\leq N-1)$.
4. (24 points) $N\leq100\space000,Q\leq100\space000,H_i\leq20(0\leq i\leq N-1)$.
5. (40 points) No additional constraints.

Author

Riku Kawasaki (Japan).

Source

IOI 2018 D2T3.

Translated by ChatGPT 5