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 static java.lang.Math.*;
import static java.lang.System.currentTimeMillis;
import static java.lang.System.exit;
import static java.lang.System.arraycopy;
import static java.util.Arrays.sort;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.fill;
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main().run();
				} catch (Throwable e) {
					e.printStackTrace();
					exit(999);
				}
			}
		}, "1", 1 << 23).start();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	final int maxn = 100 * 1000 + 100;

	int n;
	long k;
	int a[] = new int[maxn];

	TreeSet<Integer> set = new TreeSet<Integer>();
	TreeMap<Integer, Integer> numberToInteger = new TreeMap<Integer, Integer>();

	int cl[] = new int[maxn]; // ���-�� ������� �����
	int cr[] = new int[maxn]; // ���-�� ������� ������
	long countReverse;

	void renumeric() {
		for (int i = 0; i < n; i++)
			set.add(a[i]);
		int currentIndex = 0;
		for (int e : set)
			if (!numberToInteger.containsKey(e))
				numberToInteger.put(e, currentIndex++);
		for (int i = 0; i < n; i++)
			a[i] = numberToInteger.get(a[i]);
	}

	// void calcReverse() {
	// RMQ rmq = new RMQ(n);
	// countReverse = 0;
	// for (int i = 0; i < n; i++) {
	// countReverse += (cl[i] = rmq.getSumRight(a[i] + 1));// , n - 1));
	// rmq.add(a[i], 1);
	// }
	// rmq.clear();
	// for (int i = n - 1; i >= 0; i--) {
	// cr[i] = rmq.getSumLeft(a[i] - 1);
	// rmq.add(a[i], 1);
	// }
	// }

	private void run() throws IOException {
//		in = new BufferedReader(new FileReader("input.txt"));
		// out = new PrintWriter("output.txt");
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);

		n = nextInt();
		k = nextLong();
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		renumeric();
		// for (int i = 0; i < n; i++)
		// System.err.print(a[i] + " ");
		// System.err.println();
		// calcReverse();
		// System.err.println("count = " + countReverse);
		// long ans = 0;
		// if (countReverse <= k) {
		// ans = ((long) n) * (n - 1) / 2;
		// } else {
		// for (int l = 0, r = 1; l < n - 1; l++) {
		// while (r < n - 1 && countReverse > k) {
		// countReverse -= cr[r++];
		// }
		// System.err.println(l + " " + r);
		// ans += (n - r);
		// countReverse += cl[l + 1];
		// }
		// }
		long ans = 0;

		RMQ sl = new RMQ(n);

		countReverse = 0;
		for (int i = 0; i < n; i++) {
			countReverse += sl.getSumRight(a[i] + 1);
			sl.add(a[i], 1);
		}
//		System.err.println(countReverse);
		sl.clear();
		sl.add(a[0], 1);
		RMQ sr = new RMQ(n);
		for (int i = 1; i < n; i++)
			sr.add(a[i], 1);

		if (countReverse <= k)
			ans = ((long) n) * (n - 1) / 2;
		else {
			for (int l = 0, r = 1; l < n - 1; l++) {
				while (r < n - 1 && countReverse > k) {
					countReverse -= sr.getSumLeft(a[r] - 1);
					countReverse -= sl.getSumRight(a[r] + 1);
					sr.add(a[r], -1);
					r++;
				}
				if (l < r && countReverse <= k){
					ans += (n - r);
				}
				countReverse += sr.getSumLeft(a[l + 1] - 1);
				countReverse += sl.getSumRight(a[l + 1] + 1);
				sl.add(a[l + 1], 1);
			}
		}

		out.println(ans);

		in.close();
		out.close();
	}

	class RMQ {
		int tree[];
		int n;

		public RMQ(int size) {
			n = 1;
			while (n < size)
				n <<= 1;
			tree = new int[n << 1];
			fill(tree, 0);
		}

		private void add(int v, int l, int r, int index, int e) {
			if (l == r) {
				tree[v] += e;
				return;
			}
			int m = (l + r) >> 1;
			if (index <= m)
				add(v << 1, l, m, index, e);
			else
				add(2 * v + 1, m + 1, r, index, e);
			tree[v] = tree[v << 1] + tree[2 * v + 1];
		}

		public void add(int index, int e) {
			add(1, 0, n - 1, index, e);
		}

		private int getSum(int v, int l, int r, int ll, int rr) {
			if (l == ll && r == rr)
				return tree[v];
			int m = (l + r) >> 1;
			if (rr <= m)
				return getSum(v * 2, l, m, ll, rr);
			else if (ll > m)
				return getSum(v * 2 + 1, m + 1, r, ll, rr);
			return getSum(v * 2, l, m, ll, m)
					+ getSum(v * 2 + 1, m + 1, r, m + 1, rr);
		}

		public int getSum(int l, int r) {
			return getSum(1, 0, n - 1, l, r);
		}

		public int getSumRight(int index) {
			if (index >= n)
				return 0;
			return getSum(1, 0, n - 1, index, n - 1);
		}

		public int getSumLeft(int index) {
			if (index < 0)
				return 0;
			return getSum(1, 0, n - 1, 0, index);
		}

		public void clear() {
			fill(tree, 0);
		}
	}

	void chk(boolean b) {
		if (b)
			return;
		System.out.println(new Error().getStackTrace()[1]);
		exit(999);
	}

	void deb(String fmt, Object... args) {
		System.out.printf(Locale.US, fmt + "%n", args);
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

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

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

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

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
}
