Description

Orange非常讨厌逆序对。现在给定你一个长度为n对序列，你可以最多进行k次交换相邻元素。请你最小化逆序对的数量。最后报告这个逆序对的数量。

逆序对：我们把满足 $i<j$ 且 $a_i > a_j$ 的索引对 $(i,j)$ 称为一个逆序对。

Format

Input

输入第1行为2个整数n和k，表示序列长度和操作次数。

输入第2行为一个整数序列 $a_i$。

数据范围

对于50%的数据：

$1 \le n \le 1000$

对于所有数据：

$1 \le n \le 10^5$

$1 \le k \le \frac{n(n-1)}{2}$

$1 \le a_i \le 10^9$

Output

输出1个整数表示答案。

Samples

5 3
5 4 3 2 1

7