P5023 - Subsequences

内存限制：256 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：3

提交提交记录统计 Web Board

C. Subsequences

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

对于具有n个不同元素的给定序列，找出具有k+1个元素的递增子序列的数量。保证答案不大于8*1e18。

输入
第一行包含两个整数值n和k（1≤n≤1e5,0≤k≤10）−序列长度和递增子序列中元素的数量。
接下来的n行包含一个整数ai（1≤ai≤n），每个−序列元素。所有值ai都不同。
输出
打印一个整数–问题的答案。

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¹⁸.

Input

First line contain two integer values n and k (1≤n≤10⁵,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.

Output

Print one integer − the answer to the problem.

Examples

Input

Output

597C 1900 data structures, dp

5023: Subsequences

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签