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.*; 
import java.util.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	class SegmentTree {
		
		int n;
		int t [];
		
		public SegmentTree(int n) {
			this.n = n;
			t = new int [4 * n];
		}
		
		private void update (int v, int tl, int tr, int pos, int add) {
			if (tl == tr) {
				t [v] += add;
			} else {
				int tm = (tl + tr) >> 1;
				if (pos <= tm) {
					update (v * 2, tl, tm, pos, add);
				} else {
					update (v * 2 + 1, tm + 1, tr, pos, add);
				}
				t [v] = t[v * 2] + t[v * 2 + 1];
			}
		}
		
		private int get (int v, int tl, int tr, int l, int r) {
			if (l > r) return 0;
			if (l == tl && r == tr) return t [v];
			int tm = (tl + tr) >> 1;
			return get (v * 2, tl, tm, l, min (r, tm)) + get (v * 2 + 1, tm + 1, tr, max (tm + 1, l), r);
		}
		
		public void update (int pos, int add) {
			update (1, 0, n - 1, pos, add);
		}
		
		public int get (int l, int r) {
			return get (1, 0, n - 1, l, r);
		}
		
	}
	
	public void solve () throws Exception {
		int n = nextInt();
		long k = nextLong();
		int a [] = new int [n];
		int b [] = new int [n];
		
		for (int i = 0; i < n; i++) {
			a [i] = nextInt();
			b [i] = a[i];
		}
		
		Arrays.sort(b);
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		int m = 0;
		for (int i = 0; i < n; i++)
			if (!map.containsKey(b[i]))
				map.put(b[i], m++);
		
		for (int i = 0; i < n; i++) {
			a [i] = map.get(a[i]);
		}
		
		SegmentTree treeRight = new SegmentTree(m);
		SegmentTree treeLeft = new SegmentTree(m);
		
		
		int r = 1;
		long sum = 0;
		long ans = 0;

		for (int i = 0; i < n; i++) {
			treeRight.update(a[i], 1);
			sum += treeRight.get(a[i] + 1, m - 1);
		}
		
		treeLeft.update(a[0], 1);
		treeRight.update(a[0], -1);
		
		for (int l = 0; l < n - 1; l++) {
			while (r < n && sum > k) {
				sum -= treeLeft.get(a[r] + 1, m - 1);
				sum -= treeRight.get(0, a[r] - 1);
				treeRight.update(a[r], -1);
				r++;
			}

			if (sum <= k) {
				ans += (n - r);
			}
			
			if (l + 1 == r) {
				sum -= treeLeft.get(a[l + 1] + 1, m - 1);
				sum -= treeRight.get(0, a[l + 1] - 1);
				treeRight.update(a[l + 1], -1);
				r++;
			}
			
			sum += treeLeft.get(a[l + 1] + 1, m - 1);
			sum += treeRight.get(0, a[l + 1] - 1);
			treeLeft.update(a[l + 1], 1);
		}
		
		out.println(ans);
		
	}
	
	private static final String fname = "";
	private static long stime = 0;
	
	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;
	
	private String nextToken () throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}
	
	private int nextInt () throws Exception {
		return Integer.parseInt(nextToken());
	}
	
	private long nextLong () throws Exception {
		return Long.parseLong(nextToken());
	}
	
	private double nextDouble () throws Exception {
		return Double.parseDouble(nextToken());
	}
	
	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve ();
		} catch (Exception e) {
			throw new RuntimeException(e);
		} finally {
			out.close();
		}
	}
	
	public static void main(String[] args) {
		new Thread(null, new Solution(), "", 1<<26).start();
	}

}