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

public class CodeForces {
    static boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    class Point implements Comparable<Point>  {
        public int value;
        public int pos;


        @Override
        public int compareTo(Point point) {
            if (this.value == point.value)
                return this.pos - point.pos;
            return this.value - point.value;
        }
    }

    int cnt = 0;

    void update(long[] c, int pos, long v) {
        while (pos > 0) {
            c[pos] += v;
            pos -= (pos & (-pos));
        }
    }

    long sum(long[] c, int pos) {
        long res = 0;
        while (pos <= cnt) {
            res += c[pos];
            pos += pos & (-pos);
        }
        return res;
    }

    void runCase(int caseNum) throws IOException {
        int n = nextInt();
        long k = nextLong();

        Point[] p = new Point[n];
        for (int i = 0; i < n; ++i) {
            p[i] = new Point();
            p[i].pos = i;
            p[i].value = nextInt();
        }

        Arrays.sort(p);

        int[] s = new int[(int)n];

        int pre = -1;
        cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (p[i].value != pre)
                ++cnt;
            s[p[i].pos] = cnt;
        }

        long[] left = new long[cnt + 1];
        long[] right = new long[cnt + 1];
        long res = 0;
        long curRev = 0;
        int p2 = n;

        for (int p1 = 0; p1 < n; ++p1) {
            curRev += sum(left, s[p1] + 1);
            curRev += sum(right, cnt - s[p1] + 2);
            update(left, s[p1], 1);

            while (p1 + 1 < p2 && curRev <= k) {
                --p2;
                curRev += sum(left, s[p2] + 1);
                curRev += sum(right, cnt - s[p2] + 2);
                update(right, cnt - s[p2] + 1, 1);
            }

            while (p2 <= p1 || (p2 < n && curRev > k)) {
                curRev -= sum(left, s[p2] + 1);
                curRev -= sum(right, cnt - s[p2] + 2);
                update(right, cnt - s[p2] + 1, -1);
                ++p2;
            }
            res += n - p2;
        }
        out.println(res);
    }


    public static void main(String[] args) throws IOException {
        if (ONLINE_JUDGE){
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }else{
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
        new CodeForces().runIt();
        out.flush();
        out.close();
        return;
    }

    static BufferedReader in;
    private StringTokenizer st;
    static PrintWriter out;

    String next() throws IOException {
        while (!st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line, " ");
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }


    void runIt() throws IOException {
        st = new StringTokenizer("");

//        int N = nextInt();
//        for (int i = 0; i < N; i++) {
//            runCase(i + 1);
//        }
        runCase(0);

        out.flush();
    }

}
