Permutations in a permutation

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka has a permutation \(p\) of \(n\) distinct integers from 1 to \(n\) inclusive. However, she doesn’t like this permutation. The girl wants to change it somehow, but is not yet sure how exactly.

Zenyk will help Marichka with changing the permutation. In one second, the boy can swap two adjacent elements of the permutation with indices \(i\) and \(i+1\) if \(p_i - p_{i+1} \le d\), where \(d\) is a given positive integer.

Marichka has \(q\) options for how she wants to change her permutation. Each such option can be described by two numbers: \(pos\) and \(val\). These numbers mean that Marichka wants the value at position \(pos\) (\(1 \le pos \le n\)) in the permutation to be \(val\), i.e., that \(p_{pos} = val\) holds. Your task is to help Zenyk determine the minimum amount of time (in seconds) he will have to spend on rearranging the elements of the permutation to satisfy each of Marichka’s whims.

Pay attention, Marichka has not yet made a final decision on what the final permutation should look like, so each of the \(q\) options should be considered independently, and the permutation itself does not need to be modified, only the necessary minimum number of swaps needs to be calculated.

Input

The first line contains three integers \(n\), \(d\), and \(q\) separated by spaces — the number of elements in the permutation, the limit on the difference of adjacent elements that can be swapped, and the number of queries, respectively.

The next line contains \(n\) space-separated integers — the permutation \(p\).

The next \(q\) lines contain two integers \(pos_i\) and \(val_i\) separated by a space — Marichka’s queries.

Output

Output \(q\) lines — the answers to Marichka’s queries in the order they are given in the input.

If any of the queries cannot be satisfied, output -1.

Constraints

\(1 \le n, q \le 2\cdot10^5\),

\(1 \le d, p_i, pos_i, val_i \le n\),

all \(p_i\) are distinct.

Samples