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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;

public class ProblemE {
    static class BIT {
        long N;
        long[] data;
        BIT(int n) {
            N = n;
            data = new long[n+1];
        }
        
        long sum(int i) {
            long s = 0;
            while (i > 0) {
                s += data[i];
                i -= i & (-i);
            }
            return s;
        }
        
        long range(int i, int j) {
            return sum(j) - sum(i-1);
        }
        
        void add(int i, long x) {
            while (i <= N) {
                data[i] += x;
                i += i & (-i);
            }
        }
    }
    
    static Map<Integer, Integer> compress(int[] a) {
        int n = a.length;
        int[] b = a.clone();
        for (int i = 0 ; i < n ; i++) {
            int j = (int)(Math.random() * n);
            int tmp = b[j];
            b[j] = b[i];
            b[i] = tmp;
        }

        LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
        List<Integer> nadd = new ArrayList<Integer>();
        for (int i = 0 ; i < n ; i++) {
            if (!set.contains(b[i])) {
                set.add(b[i]);
                nadd.add(b[i]);
            }
        }
        Collections.shuffle(nadd);
        Collections.sort(nadd);
        
        Map<Integer, Integer> comp = new HashMap<Integer, Integer>();
        for (int na : nadd) {
            comp.put(na, comp.size());
        }
        return comp;
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String[] line = s.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        long k = Long.valueOf(line[1]);
        
        String[] data = s.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0 ; i < n ; i++) {
            a[i] = Integer.valueOf(data[i])+1;
        }
        
        Map<Integer, Integer> map = compress(a);
        for (int i = 0 ; i < n ; i++) {
            a[i] = map.get(a[i])+1;
        }
        
        
        long answer = 0;
        BIT left = new BIT(map.size()+100);
        BIT right = new BIT(map.size()+100);
        int max = map.size()+10;
        long inv = 0;
        for (int i = 0 ; i < n ; i++) {
            inv += right.range(a[i]+1, max);
            right.add(a[i], 1);
        }
        if (inv <= k) {
            out.println(1L * n * (n + 1) / 2 - n);
            out.flush();
            return;
        }
        
        int lp = 1;
        int rp = 1;
        left.add(a[0], 1);
        right.add(a[0], -1);
        while (rp < n) {
            while (rp < n && inv > k) {
                inv -= right.range(1, a[rp]-1);
                inv -= left.range(a[rp]+1, max);
                right.add(a[rp], -1);
                rp++;
            }
            // debug("rght:" + lp, rp, inv);
            while (lp < rp && inv <= k) {
                answer += n - rp;
                inv += right.range(1, a[lp]-1);
                inv += left.range(a[lp]+1, max);
                left.add(a[lp], 1);
                lp++;
            }
            // debug("left:" + lp, rp, inv);
        }
        
        
        
        
        out.println(answer);
        out.flush();
    }

    public static void debug(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}
