Subsequences

题意翻译

- 给定一个 $1\sim n$ 的排列 $a$，求 $a$ 中长度为 $k+1$ 的上升子序列个数。 - $1\le n\le 10^5$，$0\le k\le 10$，答案不超过 $8\times 10^{18}$。

题目描述

For the given sequence with $ n $ different elements find the number of increasing subsequences with $ k+1 $ elements. It is guaranteed that the answer is not greater than $ 8·10^{18} $ .

输入输出格式

输入格式

First line contain two integer values $ n $ and $ k $ $ (1<=n<=10^{5},0<=k<=10) $ — the length of sequence and the number of elements in increasing subsequences. Next $ n $ lines contains one integer $ a_{i} $ ( $ 1<=a_{i}<=n $ ) each — elements of sequence. All values $ a_{i} $ are different.

输出格式

Print one integer — the answer to the problem.

输入输出样例

输入样例 #1

5 2
1
2
3
5
4

输出样例 #1

7

题意翻译

- 给定一个 $1\sim n$ 的排列 $a$，求 $a$ 中长度为 $k+1$ 的上升子序列个数。 - $1\le n\le 10^5$，$0\le k\le 10$，答案不超过 $8\times 10^{18}$。