Minimizing Distinct Final Robot Cells in Funnyland

In Funnyland the world is modeled as a grid of size \( (h+2) \times (w+2) \). The rows are numbered from \(0\) to \(h+1\) (top to bottom) and the columns from \(0\) to \(w+1\) (left to right). Every cell is identified by its coordinates \((r, c)\). Initially, all cells are colored white except those in the rightmost column (column \(w+1\)), which are all black.

For each column \(j\) (\(1 \le j \le w\)) there is exactly one special cell located in some row between \(1\) and \(h\) (i.e. not on the border). You are allowed to color each special cell either red or blue.

Several robots will be placed in the leftmost column. A query is given by two integers \(a\) and \(b\) with \(1 \le a < b \le h\). For each row \(c\) with \(a \le c \le b\), a robot is placed at cell \((c, 0)\). The robots move independently following these rules:

• If a robot is on a white cell, it moves right.
• If on a red cell, it moves upward (i.e. row number decreases by \(1\)).
• If on a blue cell, it moves downward (i.e. row number increases by \(1\)).
• If on a black cell, it does not move.

The only cells whose colors you control are the special cells (one per column \(1\) to \(w\)). All other non‐boundary cells remain white, and the rightmost column remains black.

Your task is to choose a coloring (i.e. decide red or blue for each special cell) so that, when all the robots finish their movement (they stop once reaching a black cell in column \(w+1\)), the number of distinct final cells they occupy is minimized. Output that minimum possible number.

Note: The order of the columns is fixed. When a robot passes through column \(j\), if its current row equals the special cell's row in that column, then it is forced to move up (if the cell is red) or down (if the cell is blue). Otherwise, it simply moves right. Because the robots start in consecutive rows, you can think of your choices as a way to "squeeze" the range of rows they occupy. In particular, an optimal strategy is to only make a move when a robot is exactly at one of the boundaries of the current range of possible rows. When a robot at the lower boundary \(L\) encounters a special cell at row \(L\), choose blue (so that \(L\) increases by \(1\)); similarly, if a robot at the upper boundary \(R\) encounters a special cell at row \(R\), choose red (so that \(R\) decreases by \(1\)). After processing all columns, if the final range is \([L, R]\), the answer is \(R - L + 1\).

inputFormat

The input begins with two integers \(h\) and \(w\) on one line, describing the grid (remember that the grid has \(h+2\) rows and \(w+2\) columns). The next line contains \(w\) integers \(p_1, p_2, \dots, p_w\), where \(p_j\) (with \(1 \le p_j \le h\)) indicates the row of the special cell in the \(j\)th column. The next line contains an integer \(q\), the number of queries.

Then \(q\) lines follow; each line contains two integers \(a\) and \(b\) (with \(1 \le a < b \le h\)), representing a query where a robot is placed at \((c, 0)\) for every \(c\) from \(a\) to \(b\) (inclusive).

outputFormat

For each query, output a single integer on a new line — the minimum number of distinct final cells that the robots can occupy if the special cells are colored optimally.

sample

5 3
1 3 5
3
2 4
1 3
2 5

3
1
3