Задача Army

Військові - серйозні люди. Одного разу прапорщик Пупкін виявив, що солдати в строю розміщені не по росту. Ви можете уявити, який крик він підняв, і як дісталось сержанту Васіну, який був відповідальним за шикування. Щоб не бути розжалуваним у рядові, сержант вирішив показати прапорщику, що було не так вже й багато помилок у шикуванні. Сержант доручив рядовому (до призову - учаснику NetOI) Глюкову порахувати, скількома способами можна вибрати К + 1 солдат, що стоять по росту. Не обов'язково, щоб вони стояли підряд. Сержант бачить, що помилок достатньо, тому запевнив Глюкова, що ця кількість не буде перевищувати 8•10¹⁸. Сержант вважає, що це число буде вражаючим, і прапорщик вибачить йому його помилку.

Технічні умови: Програма зчитує з клавіатури число N - кількість солдат у строю (1<= N<=100 000) і число К (0<=К<=10), далі N чисел - номер,який мав би солдат у строю, якби всі стояли на своїх місцях. Всі числа розділені пропусками. У кожного солдата різний зріст, тому є тільки єдиний спосіб вірно розставити солдат.

Приклад.

Введення> 3 2 1 2 3
Виведення> 1

Задача Army

Военные - серьезные люди. Однажды прапорщик Пупкин обнаружил, что солдаты в строю расположены вовсе не по росту. Вы можете представить, какой крик он поднял, и как досталось сержанту Васину, который был ответственным за построение. Чтобы не быть разжалованным в рядовые, сержант решил показать прапорщику, что было не так уж много ошибок в построении. Сержант поручил рядовому (до призыва - участнику NetOI) Глюкову посчитать, сколькими способами можно выбрать К + 1 солдат, стоящих по росту. Не обязательно, чтобы они стояли подряд. Сержант видит, что ошибок предостаточно, поэтому заверил Глюкова, что это количество не будет превосходить 8•10¹⁸. Сержант думает, что это число будет впечатляющим, и прапорщик простит ему его ошибку.

Технические условия: Программа считывет с клавиатуры число N — количество солдат в строю (1 <= N <= 100 000) и число К (0 <= К <= 10), далее N чисел - номер, который бы имел солдат в строю, если бы все стояли на своем месте. Все числа разделены пробелами. У каждого солдата разный рост, поэтому есть только единственный способ правильно расставить солдат. Программа выводит на экран единственное число — ответ на поставленную задачу.

Пример.

Ввод> 3 2 1 2 3
Вывод> 1