Minimum Stamina Cost Path in a Constrained Grid

You are given a sequence \(H\) of length \(N\) and \(Q\) queries.

For the \(i\)th query, you start at column \(S_i\) on row \(H_{S_i}\) and want to reach column \(T_i\) on row \(H_{T_i}\). You can make as many moves as you wish. In each move you choose two parameters:

• A change in the column: \(-1\) (move left), \(0\) (stay in the same column) or \(+1\) (move right).
• A change in the row: \(-1\), \(0\) or \(+1\).

The cost (stamina consumption) of a move depends only on the vertical change:

• If you choose \(-1\) in the row, the move costs \(1\) stamina.
• If you choose \(0\) in the row, the move costs \(2\) stamina.
• If you choose \(+1\) in the row, the move costs \(4\) stamina.

However, after every move the following conditions must hold:

• The new column \(x\) must satisfy \(1 \le x \le N\).
• The new row \(y\) must satisfy \(y \ge H_x\) (that is, the row is not below the ground level at column \(x\)).

For each query, output the minimum total stamina cost required to travel from the starting position \((S_i, H_{S_i})\) to the target \((T_i, H_{T_i})\).

All formulas are written in \(\LaTeX\) format.

inputFormat

The input begins with two integers \(N\) and \(Q\) on one line. The next line contains \(N\) space‐separated integers \(H_1, H_2, \ldots, H_N\). Each of the following \(Q\) lines contains two integers \(S_i\) and \(T_i\) representing a query.

It is guaranteed that \(1 \le S_i, T_i \le N\) and that the initial and target positions satisfy the grid constraints (i.e. the starting row is \(H_{S_i}\) and the target row is \(H_{T_i}\)).

outputFormat

For each query, output one line containing one integer: the minimum total stamina cost required to reach the target.

sample

2 2
1 2
1 2
2 1

4
1