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.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Collection;
import java.io.IOException;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.io.InputStream;

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

class TaskE {
    public void solve(int testNumber, MyScanner in, PrintWriter out) {
        int n = in.nextInt();
        long k = in.nextLong();
        int[] as = new int[n];
        for (int i = 0; i < n; i++) as[i] = in.nextInt();
        ArrayUtils.compress(as);
        BIT left = new BIT(n+10);
        BIT right = new BIT(n+10);
        long allInv = 0;
        for (int i = 0; i < n; i++){
            long inv = right.sum(as[i]+1,n+5);
            allInv += inv;
            right.add(as[i],1);
        }
        if(allInv <= k){
            out.println((long)n*(n-1)/2);return;
        }
        int L=0,R=1;
        left.add(as[0],1);right.add(as[0],-1);
        long res = 0;
//        debug("allInv",allInv);
        while(L<n){
            while(R==L || R<n && allInv > k){
                allInv -= left.sum(as[R]+1,n+5) + right.sum(0,as[R]);
                right.add(as[R],-1);
                R++;
            }
//            debug(L,R,allInv);
            res += R-L-1;
            L++;
            if(L<n){
                allInv += left.sum(as[L]+1,n+5) + right.sum(0, as[L]);
                left.add(as[L],1);
            }
        }
        out.println((long)n*(n-1)/2 - res);
    }
    }

class MyScanner {
    private final InputStream in;
    public MyScanner(InputStream in){
        this.in = in;
    }

    public int nextInt(){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

    public long nextLong(){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }


    }

class ArrayUtils {

    public static int[] toIntArray(Collection<Integer> integerCollection) {
        int[] res = new int[integerCollection.size()];
        int i = 0;
        for (int num : integerCollection) {
            res[i++] = num;
        }
        return res;
    }


    public static void compress(int[] X) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int x : X) set.add(x);
        int[] xs = toIntArray(set);
        for (int i = 0; i < X.length; i++) {
            X[i] = Arrays.binarySearch(xs, X[i]);
        }
    }

    }

class BIT{
    long[] is;
    public BIT(int n){
        is=new long[n+1];
    }
    public long sum(int s, int t){// [s,t)
        if(s>0) return sum(0,t)-sum(0,s);
        long res=0;
        for(int i=t;i>0;i-=i&-i){
            res+=is[i];
        }
        return res;
    }
    
    public void add(int id,long val){
        for(int i=id+1;i<is.length;i+=i&-i){
            is[i]+=val;
        }
    }
    
    }
