对于给定的具有 n 个不同元素的序列,找到具有 k + 1 个元素的递增子序列的数量。保证答案不大于8·1018。
输入
第一行包含两个整数值 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — 序列的长度和递增子序列中的元素数量。
接下来的 n 行每行包含一个整数 ai (1 ≤ ai ≤ n) — 序列的元素。所有值 ai 都不同。
输出
打印一个整数——问题的答案。
示例
输入 #1
5 2 1 2 3 5 4
输出 #1
7
对于给定的具有 n 个不同元素的序列,找到具有 k + 1 个元素的递增子序列的数量。保证答案不大于8·1018。
第一行包含两个整数值 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — 序列的长度和递增子序列中的元素数量。
接下来的 n 行每行包含一个整数 ai (1 ≤ ai ≤ n) — 序列的元素。所有值 ai 都不同。
打印一个整数——问题的答案。
5 2 1 2 3 5 4
7