Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Вам задана последовательность из n чисел. Найдите количество её возрастающих подпоследовательностей из k + 1 элемента. Гарантируется, что ответ не превосходит величины 8·1018.
Входные данные
В первой строке находятся два целых числа n и k(1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — длина последовательности и количество элементов в возрастающей подпоследовательности. В следующих n строках находится по одному числу ai (1 ≤ ai ≤ n) — элементы последовательности. Все числа в последовательности различны.