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
// package SegmentTree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class LittleElephantAndInversions {
    public static void update(long tree[],int s,int e,int ind,int node,boolean flag){
        if(s==e){
            if(flag)
            tree[node]+=1;
            else{
                tree[node]-=1;
            }
            return;
        }
        int mid=(s+e)/2;
        if(ind<=mid){
            update(tree,s,mid,ind,2*node,flag);
        }
        else{
            update(tree,mid+1,e,ind,2*node+1,flag);
        }
        tree[node]=tree[2*node]+tree[2*node+1];
    }
    public static long query_less(long tree[],int s,int e,int ind,int node){
        if(ind>e){
            return tree[node];
        }
        if(ind<=s){
            return 0l;
        }
        int mid=(s+e)/2;
        long left=query_less(tree,s,mid,ind,2*node);
        long right=query_less(tree,mid+1,e,ind,2*node+1);
        return left+right;
    }
    public static long query_more(long tree[],int s,int e,int ind,int node){
        if(s>ind){
            return tree[node];
        }
        if(e<=ind){
            return 0l;
        }
        int mid=(s+e)/2;
        long left=query_more(tree,s,mid,ind,2*node);
        long right=query_more(tree,mid+1,e,ind,2*node+1);
        return left+right;
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        long k=Long.parseLong(st.nextToken());
        TreeSet<Integer> set=new TreeSet<>();
        int a[]=new int[n+1];
        st=new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(st.nextToken());
            set.add(a[i]);
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        int count=0;
        for(int e:set){
            map.put(e,count++);
        }
        for(int i=1;i<=n;i++){
            a[i]=map.get(a[i]);
//            System.out.println(a[i]);
        }
        long treeright[]=new long[4*count+4];
        long treeleft[]=new long[4*count+4];
        long ans=0;
        long curr=0;
        for(int i=1;i<n;i++){
            curr+=query_more(treeleft,0,count-1,a[i],1);
            update(treeleft,0,count-1,a[i],1,true);
        }
        int l=n-1;
//        System.out.println(curr);
        for(int r=n;r>1;r--){
            update(treeright,0,count-1,a[r],1,true);
            curr+=query_more(treeleft,0,count-1,a[r],1)+
                    query_less(treeright,0,count-1,a[r],1);
            if(l==r){
                curr-=query_less(treeright,0,count-1,a[l],1)+
                        query_more(treeleft,0,count-1,a[l],1);
                update(treeleft,0,count-1,a[l],1,false);
                l--;
            }
            while(curr>k&&l>0){
                curr-=query_less(treeright,0,count-1,a[l],1)+
                query_more(treeleft,0,count-1,a[l],1);
                update(treeleft,0,count-1,a[l],1,false);
                l--;
            }
            ans+=l;
//            System.out.println(ans);
        }
        System.out.println(ans);
    }
}
