bobo has a sequence a ₁,a ₂,…,a _n. He is allowed to swap twoadjacent 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 a _i>a _j.

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<memory>

#include<bitset>

#include<string>

#include<functional>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int MAXN = 1e5 + ;

#define INF 0x3f3f3f3f

//

LL n, k, cnt = ;

LL a[MAXN], L[MAXN/], R[MAXN];

void merge(LL l, LL r)

{

    LL mid = (l + r) / ;

    LL t1 = , t2 = ;

    for (LL i = l; i <= mid; i++)

        L[t1++] = a[i];

    for (LL i = mid + ; i <= r; i++)

        R[t2++] = a[i];

    LL i = , j = , pos = l;

    while (i < t1&&j < t2)

    {

        if (L[i] > R[j])

        {

            cnt += (t1 - i);

            a[pos++] = R[j++];

        }

        else

            a[pos++] = L[i++];

    }

    while (i < t1)

        a[pos++] = L[i++];

    while (j < t2)

        a[pos++] = R[j++];

}

void merge_sort(LL l, LL r)

{

    if (l < r)

    {

        LL mid = (l + r) / ;

        merge_sort(l, mid);

        merge_sort(mid + , r);

        merge(l, r);

    }

}

int main()

{

    while (scanf("%lld%lld", &n, &k) != EOF)

    {

        cnt = ;

        for (LL i = ; i < n; i++)

        {

            scanf("%lld", &a[i]);

        }

        merge_sort(, n - );

        if (cnt >= k)

            printf("%lld\n", cnt - k);

        else

            printf("0\n");

    }

}