Mountain Meeting Cost Minimization

You are given N mountains arranged in a row, numbered from 0 to N-1. The height of the i-th mountain is \(H_i\) (for \(0 \le i \le N-1\)). Exactly one person lives on the top of each mountain.

You plan to hold Q meetings, numbered from \(0\) to \(Q-1\). For meeting \(j\) (\(0 \le j \le Q-1\)), all persons living on mountains from \(L_j\) to \(R_j\) (inclusive) are invited. You must choose a mountain \(x\) with \(L_j \le x \le R_j\) to host the meeting. The cost for the meeting is determined as follows:

• For every mountain \(y\) with \(L_j \le y \le R_j\), the cost for the participant from mountain \(y\) is equal to the maximum height among all mountains on the segment between \(x\) and \(y\) (inclusive). In particular, the cost for the person at mountain \(x\) is \(H_x\).
• The total meeting cost is the sum of the costs for all participants.

Your task is to choose the host mountain \(x\) (within [\(L_j,R_j\)]) for each meeting so that the total cost is minimized. Note that the meetings are independent, and the participants always return to their own mountains after each meeting.

The key challenge is to compute, for each meeting query, the minimum possible cost defined by

[ C(x) = \left( \sum_{y=x}^{R_j} \max{H_k: x \le k \le y} \right) + \left( \sum_{y=L_j}^{x} \max{H_k: y \le k \le x} \right) - H_x, ]

where \(x\) is chosen from \(L_j\) to \(R_j\). Output the minimum cost for every meeting.

inputFormat

The first line contains two integers N and Q.

The second line contains N integers \(H_0, H_1, \ldots, H_{N-1}\), where \(H_i\) is the height of the i-th mountain.

Each of the next Q lines contains two integers \(L_j\) and \(R_j\) (with \(0 \le L_j \le R_j \le N-1\)), describing a meeting query.

outputFormat

For each meeting query, output a single line with the minimum total cost of holding that meeting.

sample

3 1
2 1 3
0 2

6