The inversion number of a given number sequence a1,a2,...,an is the number of pairs (ai,aj) that satisfy i<j and ai>aj.
For a given sequence of numbers a1,a2,...,an, if we move the first m>=0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
$a_1, a_2, …, a_{n-1}, a_n $(where m=0 - the initial seqence)
$a_2, a_3, …, a_n, a_1 $(where m=1)
$a_3, a_4, …, a_n, a_1, a_2 $(where m=2) ... an,a1,a2,...,an−1 (where m=n−1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n(n<=5000); the next line contains a permutation of the n integers from 0 to n−1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
Translation
给一个长度为n的数列,数列中的元素是${\text{0}} \sim n - 1$,将数列的前m(m∈[0,n−1])项删去,拼接到数列的末尾,加上初始数列共能得到n个数列,求这n个数列中逆序对最少的数列的逆序对个数。
bobo has a sequence a1,a2,…,an. He is allowed to swap two adjacent numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and ai>aj.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k(1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an(0≤ai≤109).
Output
For each tests:
A single integer denotes the minimum number of inversions.