E. Маленький Слоник, а также инверсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Маленького Слоника есть массив a, состоящий из n целых положительных чисел, пронумерованных от 1 до n. Обозначим число с номером i через ai.

Маленький Слоник хочет посчитать количество таких пар целых чисел l и r, что 1 ≤ l < r ≤ n и последовательность b = a1a2... alarar + 1... an имеет не более k инверсией.

Инверсией в последовательности b называется пара элементов последовательности b, которые после стабильной сортировки последовательности поменяют свой относительный порядок. Другими словами, инверсия это пара целых чисел i и j таких, что 1 ≤ i < j ≤ |b| и bi > bj, где |b| — длина последовательности b, а bj — ее j-ый элемент.

Помогите Маленькому Слонику посчитайте количество описанных пар.

Входные данные

В первой строке записаны два целых числа n и k (2 ≤ n ≤ 105, 0 ≤ k ≤ 1018) — размер массива a и максимально допустимое количество инверсий, соответственно. В следующей строке записаны n целых положительных чисел, разделенных единичными пробелами, a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива a.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

В единственную строку выведите целое число — ответ на задачу.

Примеры
Входные данные
3 1
1 3 2
Выходные данные
3
Входные данные
5 2
1 3 2 1 7
Выходные данные
6