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.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskE {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        long k = in.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();
        int[] unique = ArrayUtils.getUniqueElements(a);
        for (int i = 0; i < n; i++)
            a[i] = Arrays.binarySearch(unique, a[i]);
        SegmentTreeRange treeLeft = new SegmentTreeRange(unique.length);
        SegmentTreeRange treeRight = new SegmentTreeRange(unique.length);
        long ans = 0;
        long inversions = 0;
        // Count all inversions
        for (int i = 0; i < n; i++)
            treeLeft.add(a[i], +1);
        for (int i = 0; i < n; i++) {
            inversions += treeLeft.getLowerCount(a[i]);
            treeLeft.add(a[i], -1);
        }
        // Count answer
        treeLeft.set(a[0], 1);
        for (int i = 1; i < n; i++)
            treeRight.add(a[i], +1);
        int l = 0, r = 1;
        while (l < n - 1) {
            while (inversions > k) {
                if (r + 1 == n) break;
                inversions -= treeLeft.getGreaterCount(a[r]);
                inversions -= treeRight.getLowerCount(a[r]);
                treeRight.add(a[r], -1);
                r++;
            }
            if (inversions <= k)
                ans += n - r;
            if (l == r - 1) {
                treeLeft.add(a[r], +1);
                treeRight.add(a[r], -1);
                r++;
            } else {
                inversions += treeLeft.getGreaterCount(a[l + 1]);
                inversions += treeRight.getLowerCount(a[l + 1]);
                treeLeft.add(a[l + 1], +1);
            }
            l++;
        }
        out.println(ans);
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

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

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

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
}

class ArrayUtils {
    public static int[] getUniqueElements(int[] a) {
        int n = a.length;
        Integer[] diff = new Integer[n];
        for (int i = 0; i < n; i++)
            diff[i] = a[i];
        Arrays.sort(diff);
        int newLen = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j + 1 < n && diff[j + 1].equals(diff[i]))
                j++;
            diff[newLen++] = diff[i = j];
        }
        int[] ret = new int[newLen];
        for (int i = 0; i < newLen; i++)
            ret[i] = diff[i];
        return ret;
    }
}

class SegmentTreeRange {
    private int n; // Length of the range
    private long[] t; // Number of elements in range

    public SegmentTreeRange(int size) {
        build(size, null);
    }

    public SegmentTreeRange(int size, long[] initValue) {
        build(size, initValue);
    }

    public void add(int pos, long delta) {
        add(pos, delta, 1, 0, n - 1);
    }

    public void set(int pos, long value) {
        set(pos, value, 1, 0, n - 1);
    }

    public long getLowerCount(long value) {
        return getLowerCount(value, 1, 0, n - 1);
    }

    public long getGreaterCount(long value) {
        return getGreaterCount(value, 1, 0, n - 1);
    }

    private void build(int size, long[] initValue) {
        n = size;
        t = new long[4 * n + 1];
        build(1, 0, n - 1, initValue);
    }

    private void build(int i, int l, int r, long[] initValue) {
        if (l == r) {
            t[i] = initValue == null ? 0 : initValue[l];
            return;
        }
        int m = (l + r) / 2;
        build(i * 2, l, m, initValue);
        build(i * 2 + 1, m + 1, r, initValue);
        t[i] = t[i * 2] + t[i * 2 + 1];
    }

    private void add(int pos, long delta, int i, int tl, int tr) {
        if (tl == tr) {
            t[i] += delta;
            return;
        }
        int m = (tl + tr) / 2;
        if (pos <= m) add(pos, delta, i * 2, tl, m);
        else add(pos, delta, i * 2 + 1, m + 1, tr);
        t[i] += delta;
    }

    private void set(int pos, long value, int i, int tl, int tr) {
        if (tl == tr) {
            t[i] = value;
            return;
        }
        int m = (tl + tr) / 2;
        if (pos <= m) set(pos, value, i * 2, tl, m);
        else set(pos, value, i * 2 + 1, m + 1, tr);
        t[i] = t[i * 2] + t[i * 2 + 1];
    }

    private long getLowerCount(long value, int i, int tl, int tr) {
        if (tl == tr) return tl < value ? t[i] : 0;
        int m = (tl + tr) / 2;
        if (value <= m) return getLowerCount(value, i * 2, tl, m);
        else return t[i * 2] + getLowerCount(value, i * 2 + 1, m + 1, tr);
    }

    private long getGreaterCount(long value, int i, int tl, int tr) {
        if (tl == tr) return tl > value ? t[i] : 0;
        int m = (tl + tr) / 2;
        if (value <= m) return t[i * 2 + 1] + getGreaterCount(value, i * 2, tl, m);
        else return getGreaterCount(value, i * 2 + 1, m + 1, tr);
    }
}
