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.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.TreeMap;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.TreeSet;
import java.io.Writer;
import java.util.StringTokenizer;
import java.math.BigInteger;
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;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
        
        int n = in.nextInt();
        long k = in.nextLong();
        int i, j;
        int a[] = in.nextIntArray(n);
        
        TreeMap<Integer,Integer> c = ArrayUtils.compress(a);
        int m = c.size();
        SegmentTrees.SegmentTreeSum L = new SegmentTrees.SegmentTreeSum(m);
        SegmentTrees.SegmentTreeSum R = new SegmentTrees.SegmentTreeSum(m);
        
        long inversions = 0;
        long ans = 0;

        int ii, jj;
        for(j=n-1; j>=0; --j){
            jj = c.get(a[j]);
            int add = R.get(0, jj-1);
            if(inversions+add>k) break;
            inversions+=add;
            R.add(jj, 1);
        }
        ++j;
        
        for(i=0;i<n-1;++i){
            ii = c.get(a[i]);
            inversions += L.get(ii+1, m-1) + R.get(0, ii-1);
            L.add(ii, 1);
            
            while(j<n && (i>=j || inversions>k)){
                jj = c.get(a[j]);
                inversions -= L.get(jj+1, m-1) + R.get(0, jj-1);
                R.add(jj, -1);
                ++j;
            }
            
            if(j<n && i<j && inversions<=k){
                ans += n-j;
            }
        }
        
        out.write(ans);
	}
}

class InputReader{
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    
    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next(){
        while(tokenizer==null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public int nextInt(){
        return Integer.parseInt(next());
    }

    public long nextLong(){
        return Long.parseLong(next());
    }
    
    public int[] nextIntArray(int size){
        int array[] = new int[size];
        for(int i=0; i<size; ++i) array[i] = nextInt();
        return array;
    }
}

class OutputWriter{
    private PrintWriter out;
    
    public OutputWriter(Writer out){
        this.out = new PrintWriter(out);
    }

    public OutputWriter(OutputStream out){
        this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
    }
    
    public void close(){
        out.flush();
        out.close();
    }

    public void write(Object ... o){
        for(Object x : o) out.print(x);
    }

    }

class ArrayUtils{
    
    public static TreeMap<Integer, Integer> compress(int a[]){
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int x : a) set.add(x);
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        int i = 0;
        for(int x : set){
            map.put(x, i);
            ++i;
        }
        return map;
    }
}

class SegmentTrees{

    public static class SegmentTreeSum{
        int t[], d;

        public SegmentTreeSum(int n){
            d = Integer.highestOneBit(n-1)<<1;
            t = new int[d<<1];
        }

        public SegmentTreeSum(int[] array){
            int n = array.length, i;
            d = Integer.highestOneBit(n-1)<<1;
            t = new int[d<<1];
            for(i=d; i<n+d; ++i) t[i] = array[i-d];
            for(i=n+d; i<d+d; ++i) t[i] = 0;
            for(i=d-1; i>0; --i) t[i] = t[i*2]+t[i*2+1];
        }

        public void add(int index, int value){
            for(index+=d; index>0; index>>=1) t[index] += value;
        }

        public int get(int left, int right){
            int res = 0;
            for(left+=d, right+=d; left<=right; left>>=1, right>>=1){
                if((left&1)==1){
                    res += t[left]; ++left;
                }
                if((right&1)==0){
                    res += t[right]; --right;
                }
            }
            return res;
        }
    }
}

