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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

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

class TaskE {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
		int n = in.readInt();
		long K = in.readLong();
		int[] a = in.readIntArray(n);
		int[] axis = Arrays.copyOf(a, n);
		ArrayUtil.sort(axis);
		axis = ArrayUtil.unique(axis);
		int[] s1 = new int[axis.length + 1];
		int[] s2 = new int[axis.length + 1];
		Arrays.fill(s1, 0);
		Arrays.fill(s2, 0);
		long sum = 0, ans = 0;
		for (int i = n - 1; i >= 1; i --) {
			int x = Arrays.binarySearch(axis, a[i]);
			for (int j = x; j > 0; j -= j & -j) sum += s2[j];
			for (int j = x + 1; j <= axis.length; j += j & -j) s2[j] ++;
		}
		for (int i = 0, j = 1; i < n; i ++) {
			int x = Arrays.binarySearch(axis, a[i]);
			sum += i;
			for (int k = x + 1; k > 0; k -= k & -k) sum -= s1[k];
			for (int k = x; k > 0; k -= k & -k) sum += s2[k];
			for (int k = x + 1; k <= axis.length; k += k & -k) s1[k] ++;
			while (j < n && (sum > K || j <= i)) {
				int y = Arrays.binarySearch(axis, a[j]);
				for (int k = y; k > 0; k -= k & -k) sum -= s2[k];
				sum -= i + 1;
				for (int k = y + 1; k > 0; k -= k & -k) sum += s1[k];
				for (int k = y + 1; k <= axis.length; k += k & -k) s2[k] --;
				j ++;
			}
			ans += n - j;
		}
		out.printLine(ans);
	}
}

class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1000];
	private int curChar;
	private int numChars;

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

	private 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++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] readIntArray(int length) {
		int[] res = new int[length];
		for (int i = 0; i < length; i ++) res[i] = readInt();
		return res;
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

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

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}
}

class ArrayUtil {
	private ArrayUtil() {
	}

	public static int[] unique(int[] data) {
		if (data.length == 0) return data;
		for (int i = 0; i < data.length - 1; i ++)
			if (data[i] > data[i + 1]) throw new RuntimeException();
		ArrayList<Integer> l = new ArrayList<Integer>();
		l.add(data[0]);
		for (int i = 1; i < data.length; i ++)
			if (data[i] != l.get(l.size() - 1)) l.add(data[i]);
		int[] res = new int[l.size()];
		for (int i = 0; i < l.size(); i ++) res[i] = l.get(i);
		return res;
	}

	private static void swap(int[] data, int i, int j) {
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	private static void quickSort(int[] data, int l, int r, Random rnd) {
		int x = rnd.nextInt(r - l + 1) + l;
		swap(data, (l + r) / 2, x);
		int mid = data[(l + r) / 2];
		int i = l, j = r;
		do {
			while (data[i] < mid) i ++;
			while (data[j] > mid) j --;
			if (i <= j) {
				swap(data, i, j);
				i ++;
				j --;
			}
		} while (i <= j);
		if (l < j) quickSort(data, l, j, rnd);
		if (i < r) quickSort(data, i, r, rnd);
	}

	public static void sort(int[] data) {
		quickSort(data, 0, data.length - 1, new Random());
	}

	}

