F. K-инверсии

Никита изучает комбинаторику. Недавно он познакомился с такими забавными объектами, как перестановки. Напомним, что перестановкой чисел от 1 до n называется последовательность чисел от 1 до n в каком-то порядке, в которой каждое из этих чисел встречается ровно один раз.

Также Никите рассказали про инверсии. Инверсия – это такая ситуация, когда в перестановке бОльшее число идёт перед меньшим. Например, в перестановке 2 1 3 есть инверсия из чисел 2 и 1.

А недавно Никита узнал про k-инверсии. Это такие ситуации, когда одно число в перестановке идёт раньше другого, и при этом первое больше второго не менее, чем на k. Таким образом, обычные инверсии являются 1-инверсиями. Более формально, k-инверсия – это пара индексов (i, j) таких, что i < j и p_i ≥ p_j + k.

Никита просит Вас посчитать количество k-инверсий в заданной перестановке.

Формат входного файла

Первая строка входного файла содержит числа n и k. (1 ≤ k ≤ n ≤ 10⁵) Во второй строке находится n чисел – перестановка p.

Формат выходного файла

Выведите единственное число – количество k-инверсий в заданной перестановке.

Пример:

Отправить решение



Версия для печати