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.IOException;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;

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

class TaskE {
    private int[] aLeft, aRight;
    private int N;

	public void solve(int testNumber, StreamInputReader in, PrintWriter out) {
        N = in.readInt();
        long K = in.readLong();
        int[] v = new int[N];
        Integer[] sorted = new Integer[N];
        for(int i = 0; i < N; i++) {
            v[i] = in.readInt();
            sorted[i] = v[i];
        }
        Arrays.sort(sorted);
        TreeMap<Integer, Integer> indexes = new TreeMap<Integer, Integer>();
        for(int i = 0; i < N; i++)
            if(!indexes.containsKey(sorted[i]))
                indexes.put(sorted[i], i + 1);
        for(int i = 0; i < N; i++)
            v[i] = indexes.get(v[i]);

        aLeft = new int[N + 1];
        aRight = new int[N + 1];
        long inv = 0;
        for(int i = 1; i < N; i++) {
            update(aRight, v[i], 1);
            inv += query(aRight, N) - query(aRight, v[i]);
        }

        int rightPos = 1;
        long ans = 0;
        for(int leftPos = 0; leftPos < N - 1 && rightPos < N; leftPos++) {
            if(leftPos == rightPos) {
                inv -= query(aRight, v[rightPos] - 1);
                inv -= query(aLeft, N) - query(aLeft, v[rightPos]);
                update(aRight, v[rightPos], -1);
                rightPos++;
            }

            update(aLeft, v[leftPos], 1);
            inv += query(aLeft, N) - query(aLeft, v[leftPos]);

            inv += query(aRight, v[leftPos] - 1);

            while(inv > K && rightPos < N) {
                inv -= query(aRight, v[rightPos] - 1);
                inv -= query(aLeft, N) - query(aLeft, v[rightPos]);
                update(aRight, v[rightPos], -1);
                rightPos++;
            }

            if(rightPos < N)
                ans += N - rightPos;
        }

        out.print(ans);
	}

    private long query(int[] aib, int poz) {
        long ret = 0;
        while(poz > 0) {
            ret += aib[poz];
            poz -= poz & (-poz);
        }
        return ret;
    }

    private void update(int[] aib, int poz, int val) {
        while(poz <= N) {
            aib[poz] += val;
            poz += poz & (-poz);
        }
    }
}

class StreamInputReader extends InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar, numChars;

    public StreamInputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    }

abstract class InputReader {

    public abstract int read();

    public int readInt() {
        return Integer.parseInt(readString());
    }

    public long readLong() {
        return Long.parseLong(readString());
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

