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.*;
import java.io.*;

public class LittleElephantInversions {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int n = scanner.nextInt();
        long k = scanner.nextLong();
        int[] arr = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            set.add(arr[i]);
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] getind = new int[n];
        int cnt = 1;
        for(int vv: set) map.put(vv, cnt++);
        for(int i = 0; i < n; i++) {
            getind[i] = map.get(arr[i]);
        }
        BIT right = new BIT(n+1);
        BIT left = new BIT(n+1);
        long tot = 0;
        for(int i = n-1; i >= 0; i--) {
            tot += right.pref(getind[i]-1);
            right.update(getind[i], 1);
        }
        int r = 1;
        long cur = tot;
        //add in 0
        right.update(getind[0], -1);
//        //remove 1
//        right.update(getind[1], -1);
//        cur-= left.range(getind[1] + 1, left.sz-1);
//        cur-= right.pref(getind[1]-1);
        long ans = 0;
        boolean[] rem = new boolean[n];
        //assumption is the (l,r) is removed
        for(int l = 0; l < n-1; l++) {
            if (rem[l]) {
                cur += left.range(getind[l] + 1, left.sz - 1);
                cur += right.pref(getind[l] - 1);
                rem[l] = false;
            }
            left.update(getind[l], 1);
            if (l == r) {
                right.update(getind[r], -1);
                r++;
            }
            while(cur > k && r < n) {
                //remove r
                cur -= left.range(getind[r]+1, left.sz -1);
                cur -= right.pref(getind[r]-1);
                right.update(getind[r], -1);
                rem[r] = true;
                r++;
            }
            ans += n-r;
            //add left back in
        }
        out.println(ans);
        out.flush();
    }
    static class BIT {
        long[] table;
        int sz;
        public BIT(int ss) {
            sz = ss;
            table = new long[ss];
        }
        void update(int loc, long amt) {
            while(loc < sz) {
                table[loc]+=amt;
                loc += loc & - loc;
            }
        }
        long pref(int loc) {
            long ret = 0;
            while(loc > 0) {
                ret += table[loc];
                loc -= loc & - loc;
            }
            return ret;
        }
        long range(int l, int r) {
            return pref(r) - pref(l - 1);
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
