У Маленького Слоника есть массив 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-ый элемент.
Помогите Маленькому Слонику посчитайте количество описанных пар.