Перестановки в перестановці

Limits: 2 sec., 256 MiB

Марічка має перестановку \(p\) із \(n\) різних цілих чисел від 1 до \(n\) включно. Але їй не подобається ця перестановка. Дівчина хоче якось її змінити, проте ще не впевнена як саме.

Зі зміною перестановки Марічці допоможе Зеник. За одну секунду хлопець може поміняти місцями два сусідні елементи перестановки з індексами \(i\) та \(i+1\) якщо \(p_i - p_{i+1} \le d\), де \(d\) — задане ціле додатне число.

У Марічки є \(q\) варіантів як вона хоче змінити свою перестановку. Кожен такий варіант можна описати двома числами: \(pos\) та \(val\). Ці числа означають, що Марічка хоче, щоб на позиції \(pos\) (\(1 \le pos \le n\)) в перестановці було значення \(val\), тобто щоб виконувалося \(p_{pos} = val\). Ваше завдання — допомогти Зенику визначити скільки найменше часу (в секундах) йому доведеться витратити на переставляння елементів перестановки, щоб задовольнити кожну із забаганок Марічки.

Зверніть увагу, Марічка ще не прийняла остаточного рішення про те, як має виглядати фінальна перестановка, тому кожен з \(q\) варіантів потрібно розглядати незалежно, а саму перестановку модифікувати не треба, лише порахувати необхідну мінімальну кількість змін.

Input

У першому рядку задано три цілі числа \(n\), \(d\) та \(q\) розділені пробілами — кількість елементів перестановки, обмеження на різницю сусідніх елементів котрі можна міняти місцями і кількість запитів відповідно.

Наступний рядок містить \(n\) цілих чисел розділених пробілами — перестановку \(p\).

Наступні \(q\) рядків містять по два цілі числа \(pos_i\) та \(val_i\) розділені пробілом — запити Марічки.

Output

Виведіть \(q\) рядків — відповіді на запити Марічки в такому порядку як вони задані на вході.

Якщо котрийсь із запитів не можливо задовольнити, виведіть -1.

Constraints

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

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

усі \(p_i\) різні.

Samples