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.util.Arrays;
import java.util.PriorityQueue;

public class CF_LittleElephantAndInversions {
    static int n;
    static long k, sK, res;
    static int[]a;
    static int[]inversions, countL, countR;
    static ST s1, s2;
    static PriorityQueue<Pair> ord;
    static int l,r;
    static boolean change;
    public static void main(String[]args) throws IOException{
        String[]data;
        try (BufferedReader f = new BufferedReader(new InputStreamReader(System.in))) {
            data = f.readLine().split(" ");
            n = Integer.valueOf(data[0]);
            k = Long.valueOf(data[1]);
            data = f.readLine().split(" ");
        }
        ord = new PriorityQueue<>();
        //Paso 0: Cambiar los elementos del arreglo de 0 a 10^9, a 0 a n-1 como máximo
        for(int i = 0 ; i < n ; ++i)
            ord.add(new Pair(Integer.valueOf(data[i]), i));
        a = new int[n];
        Pair prev = ord.peek(), p;
        int cont = 0;
        while(!ord.isEmpty()){
            p = ord.poll();
            if(prev.x == p.x){
                
            }else{
                ++cont;
                prev = p;
            }
            a[p.y] = cont;
        }
//        System.out.println(Arrays.toString(a));
        //Paso 1: Calcular las inversions totales, y acumularlas
        s1 = new ST(0, n-1);
        
        countL = new int[n];
        countR = new int[n];
        inversions = new int[n];
        for(int i = 0 ; i < n ; ++i){
            ++countL[a[i]];
            s1.update(a[i], countL[a[i]]);
            inversions[i] = s1.getQuery(a[i]+1, n-1);
            sK+=inversions[i];
        }
//        System.out.println(Arrays.toString(inversions));
        s2 = new ST(0,n-1);
        //Paso 2: Resolver el problema mediante two-pointers
        l = n-2;
        r = n-1;

        countR[a[r]] = 1;
        
        s2.update(a[r], countR[a[r]]);    
        --countL[a[r]];
        s1.update(a[r], countL[a[r]]);
        while(l>=0){
//            System.out.println("Conteo: "+sK  +" " + k);
//            System.out.println("Pointers: " + l +" " + r);
            if(sK<=k){
                
                res+= l+1;
//                System.out.println("sume a la respuesta");
                if(r-l!=1){
                    //--r;
                    //Paso 2.1: Realizar lo que involucra disminuir r
                    minusR();
                }else{
                    minusL();
                    minusR();
                }
            }else{
                //--l;
                //Paso 2.2: Realizar lo que involucra disminuir l
                minusL();
            }
//            System.out.println("");
        }
        
        System.out.println(res);
    }

    private static void minusL() {
        //Paso 2.2.1: Quitar a[l] del segment tree s1, para que se puedan calcular las inversiones de los futuros a[r] correctamente
        --countL[a[l]];
        s1.update(a[l], countL[a[l]]);
        //Paso 2.2.2: Contar cuantos valores menores a a[l] hay entre a[r] y a[n], y quitarlos de las inversiones totales
        sK = sK - s2.getQuery(0, a[l] - 1);
        //Paso 2.2.3: Quitar las inversiones de a[l] al total
        sK = sK - inversions[l];
        //Paso 2.2.4: Desplazar l
        --l;
    }

    private static void minusR() {
        //Paso 2.1.1: Desplazar r y quitar a[r] de s1 para poder calcular las inversiones de a[r] futuros correctamente
//        --countL[a[r]];
//        System.out.println(countL[a[r]]);
//        change = true;
//        s1.update(a[r], countL[a[r]]);
        --r;
        //Paso 2.1.2: Añadir las inversiones de a[r-1]
        sK = sK + s1.getQuery(a[r] + 1, n-1);
        //Paso 2.1.3: Contar cuantos elementos son menores a a[r-1] en el intervalo a[r] y a[n], y sumarlas
        sK = sK + s2.getQuery(0, a[r] -1);
        //Paso 2.1.4: Introducir a[r-1] a s2
        ++countR[a[r]];
        s2.update(a[r], countR[a[r]]);
    }
    static class Pair implements Comparable<Pair>{
        int x, y;
        public Pair(int x, int y) { this.x = x; this.y = y;}

        @Override
        public int compareTo(Pair t) {
            if(x - t.x!=0)
                return x - t.x;
            else
                return y - t.y;
        }     
    }
    static class ST{
        int begin, end, mid;
        ST left, right; 
        int value;
        public ST( int i, int j){
            begin = i;
            end = j;
            mid = (i+j)/2;
            if(i!=j){
                left = new ST(i, mid);
                right = new ST(mid+1, j);
                value = append(left.value, right.value);
            }else{
                value = 0;
            } 
        }
        public int getQuery(int i, int j){
            if(i > j)
                return 0;
            if(i == begin && j == end){
                return value;
            }else
                if(i <= mid)
                    if(j <= mid) return left.getQuery(i, j);
                    else return append(left.getQuery(i, mid),right.getQuery(mid+1, j)); 
                else
                    return right.getQuery(i, j); 
            
        }
        public void update(int i, int a){
            if(begin == end){
                value = a;
            }  
            else{
                if(i <= mid) left.update(i, a);  
                else right.update(i, a);
                value = append(left.value, right.value);
            }
        }

        public int append(int left, int right){ 
            return left+right;
        }
        public int find(int k){
            if(begin == end) return begin;
            else
                if(left.value >= k)
                    return left.find(k);
                else
                    return right.find(k - left.value);
        }

    }
}