The Little Elephant has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai.

The Little Elephant wants to count, how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = a1a2... alarar + 1... an has no more than k inversions. 

An inversion in sequence b is a pair of elements of the sequence b, that change their relative order after a stable sorting of the sequence. In other words, an inversion is a pair of integers i and j, such that 1 ≤ i < j ≤ |b| and bi > bj, where |b| is the length of sequence b, and bj is its j-th element.

Help the Little Elephant and count the number of the described pairs.

Input

The first line contains two integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ 1018) — the size of array a and the maximum allowed number of inversions respectively. The next line contains n positive integers, separated by single spaces, a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of array a.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output

In a single line print a single number — the answer to the problem.

Examples

Input

3 1
1 3 2


Output

3


Input

5 2
1 3 2 1 7


Output

6


import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class Inversions220E {
    int maxn = 100010;

    class IndexTree {
        int ss[] = new int[maxn + 10];
        int N = maxn;
        int lowbit(int k) {
            return (k & -k);
        }
        void inc(int i, int v) {
            while (i <= N) {
                ss[i] += v;
                i += lowbit(i);
            }
        }
        int get(int i) {
            int res = 0;
            while (i > 0) {
                res += ss[i];
                i -= lowbit(i);
            }
            return res;
        }
    }
    IndexTree all = new IndexTree(), pre = new IndexTree(),
            now = new IndexTree();
    TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>();
    int arr[] = new int[maxn];
    Scanner scan = new Scanner(System.in);
    void run() {
        int n = scan.nextInt();
        long k = scan.nextLong();
        long sum = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt();
            mp.put(arr[i], 0);
        }
        int cnt = 0;
        Set<Integer> set = mp.keySet();
        for (int i : set)
            mp.put(i, ++cnt);
        for (int i = 1; i <= n; i++) {
            arr[i] = mp.get(arr[i]);
            all.inc(arr[i], 1);
            sum += i - all.get(arr[i]);
        }
        if(sum<=k)
        {
            ans=1l*n*(n-1)/2;
            System.out.println(ans);
            return;
        }
        int left = 1, right =1;
        now.inc(arr[1],1);
        long res=sum-all.get(arr[1]-1);
        while (left <= n) {
            while (right <=n && res> k) {   
                right++;    
                now.inc(arr[right], 1);     
                res-=left-1-pre.get(arr[right]);
                res-=all.get(arr[right]-1)-now.get(arr[right]-1)-pre.get(arr[right]-1);
            }
            while (left<right) {
                long temp = left - 1 - pre.get(arr[left]);
                temp += all.get(arr[left] - 1) - pre.get(arr[left] - 1)-now.get(arr[left]-1);
                if(res+temp > k)
                    break;
                pre.inc(arr[left],1);
                now.inc(arr[left],-1);
                res+=temp;
                left++;
            }
            //System.out.println(left+" "+right+" "+res);
            if (res<=k&&left!=1&&right!=n)
                ans += left-1;
            if(right==n)
                break;
            right++;
            now.inc(arr[right], 1);     
            res-=left-1-pre.get(arr[right]);
            res-=all.get(arr[right]-1)-now.get(arr[right]-1)-pre.get(arr[right]-1);
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        new Inversions220E().run();

    }

}
