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.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collection;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
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_Inversions solver = new TaskE_Inversions();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE_Inversions {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        long K = in.nextLong();
        int[] a = Utils.readIntArray(in, n);
        CompressData compressData = new CompressData(a);
        FenwickTreeSum fenwickTreeSumPrefix = new FenwickTreeSum(2 * n);
        long totalInv = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = compressData.originalToMapping(a[i]);
            totalInv += fenwickTreeSumPrefix.getSum(a[i] + 1, n);
            fenwickTreeSumPrefix.update(a[i], 1);
        }
        FenwickTreeSum fenwickTreeSumSuffix = new FenwickTreeSum(2 * n);
        int l = n - 1;
        long res = 0;
        for (int r = n - 1; r >= 1; --r) {
            while (l >= r) {
                totalInv -= fenwickTreeSumPrefix.getSum(a[l] + 1, n);
                totalInv -= fenwickTreeSumSuffix.getSum(0, a[l] - 1);
                fenwickTreeSumPrefix.update(a[l], -1);
                --l;
            }
            fenwickTreeSumSuffix.update(a[r], 1);
            totalInv += fenwickTreeSumPrefix.getSum(a[r] + 1, n);
            totalInv += fenwickTreeSumSuffix.getSum(0, a[r] - 1);
            while (totalInv > K && l > 0) {
                totalInv -= fenwickTreeSumPrefix.getSum(a[l] + 1, n);
                totalInv -= fenwickTreeSumSuffix.getSum(0, a[l] - 1);
                fenwickTreeSumPrefix.update(a[l], -1);
                --l;
            }
            if (totalInv <= K) {
                res += l + 1;
            }
        }
        out.println(res);
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

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

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

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

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

}

class Utils {
    public static int[] readIntArray(InputReader in, int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        return a;
    }

}

class CompressData {
    List<Integer> x;

    public CompressData(int[] x) {
        this.x = new ArrayList<Integer>(x.length);
        for (int i = 0; i < x.length; ++i) {
            this.x.add(x[i]);
        }
        CollectionUtils.unique(this.x);
    }

    public int originalToMapping(int original) {
        return Collections.binarySearch(x, original);
    }

}

class FenwickTreeSum {
    long[] sum;
    int n;

    public FenwickTreeSum(int n) {
        this.n = n;
        sum = new long[n+1];
        Arrays.fill(sum, 0);
    }

    public void update(int position, long value) {
        ++position;
        for (int i = position; i <= n; i = next(i)) {
            sum[i] += value;
        }
    }

    public long getSum(int from, int to) {
        return getPrefixSum(to) - getPrefixSum(from-1);
    }

    public long getPrefixSum(int position) {
        ++position;
        long result = 0;
        for (int i = position; i > 0; i = prev(i)) {
            result += sum[i];
        }
        return result;
    }

    private static int prev(int x) {
        return (x & (x - 1));
    }

    private static int next(int x) {
        return (x << 1) - prev(x);
    }
}

class CollectionUtils {

    public static void unique(List<Integer> a) {
        Collections.sort(a);
        int size = 1;
        for (int i = 1; i < a.size(); i++) {
            if (!a.get(i).equals(a.get(size - 1))) {
                a.set(size++, a.get(i));
            }
        }
        for (int i = a.size() - 1; i >= size; i--) {
            a.remove(i);
        }
    }


}

