P5044 [IOI 2018] meetings Meeting.

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

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.

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 $Q$ lines. Line $1+j$ ($0\leq j\leq Q-1$) contains one integer $C_j$, the minimum possible cost of holding meeting $j$.

### 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