小象有数组 a,由 n 个正整数组成,索引从 1 到 n。我们将索引为 i 的数字表示为 ai。
小象想数一下,有多少对整数 l 和 r,使得 1 ≤ l < r ≤ n 且序列 b = a1a2... alarar + 1... an 的反转不超过 k 个。
序列 b 中的反转是序列 b 的一对元素,在序列稳定排序后改变它们的相对顺序。换句话说,反转是一对整数 i 和 j,使得 1 ≤ i < j ≤ |b|且 bi > bj,其中 |b|是序列b的长度,bj是其第j个元素。
帮助小象数一数所描述的对的数量。
输入
第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 0 ≤ k ≤ 1018) — 分别是数组 a 的大小和允许的最大反转次数。下一行包含 n 个正整数,用单个空格分隔,a1, a2, ..., an (1 ≤ ai ≤ 109) — 数组 a 的元素。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
在一行中打印一个数字——问题的答案。
示例
输入 #1
3 1 1 3 2
输出 #1
3
输入 #2
5 2 1 3 2 1 7
输出 #2
6