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

Input file name: k-inversions.in
Output file name: k-inversions.out
Time limit: 2 s
Memory limit: 256 megabytes

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

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

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

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

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

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

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

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

Пример:

k-inversions.ink-inversions.out
3 1 2 1 3 1
3 2 2 1 3 0
3 2 3 2 1 1



Submit a solution



Printable version