递增子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个互不相同的元素组成的序列，求其中长度恰好为 $k+1$ 的严格递增子序列个数。

保证答案不超过 $8\times 10^{18}$。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，每行包含一个整数 $a_i$。所有 $a_i$ 互不相同。

输出格式

输出一个整数，表示长度恰好为 $k+1$ 的严格递增子序列个数。

样例输入 1

5 2
1
2
3
5
4

样例输出 1

7

数据范围

• $1\le n\le 10^5$；
• $0\le k\le 10$；
• $1\le a_i\le n$；
• 所有 $a_i$ 互不相同；
• 答案不超过 $8\times10^{18}$。