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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class CF136E implements Runnable {
	
	private int BIT[], BIT1[];
	private int n;
	
	private void add(int x, int y, int BIT[])
	{
		++x;
		while (x <= n)
		{
			BIT[x] += y;
			x += x & -x;
		}
	}
	
	private int sum(int x, int BIT[])
	{
		++x;
		int ret = 0;
		while (x > 0)
		{
			ret += BIT[x];
			x -= x & -x;
		}
		
		return ret;
	}
	
    private void solve() throws IOException {
    	n = nextInt();
    	long k = nextLong();
    	int a[] = new int[n];
    	for (int i = 0; i < n; ++i)
    		a[i] = nextInt();
    	
    	long cur = 0;
    	BIT = new int[n+1];
    	BIT1 = new int[n+1];
    	
    	HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
    	int ord[] = a.clone();
    	Arrays.sort(ord);
    	
    	int total = 0;
    	for (int i = 0; i < n; ++i)
    		if (i == 0 || ord[i] != ord[i-1])
    			hash.put(ord[i], total++);
    	for (int i = 0; i < n; ++i)
    		a[i] = hash.get(a[i]);

    	Arrays.fill(BIT, 0);
    	for (int i = 0; i < n; ++i)
    	{
    		cur += i - sum(a[i], BIT);
    		add(a[i], 1, BIT);
    	}
    	
    	Arrays.fill(BIT, 0);
    	Arrays.fill(BIT1, 0);
    	
    	for (int i = 0; i < n; ++i)
    		add(a[i], 1, BIT1);
    	
    	int pointer = 0;
    	long ans = 0;
    	for (int i = 0; i < n; ++i)
    	{
    		if (pointer > i)
    		{
    			cur += i - sum(a[i], BIT);
    			cur += sum(a[i]-1, BIT1);
    		}
    		else
    		{
    			++pointer;
    			add(a[i], -1, BIT1);
    		}
    		
    		add(a[i], 1, BIT);
    		
    		while (pointer < n && cur > k)
    		{
    			add(a[pointer], -1, BIT1);
    			
    			cur -= i+1 - sum(a[pointer], BIT);
    			cur -= sum(a[pointer]-1, BIT1);
    			
    			++pointer;
    		}
    		
    		ans += n - pointer;
    	}
    	
    	writer.println(ans);
    }

    public static void main(String[] args) {
        new CF136E().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    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 nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}