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.*;
import java.util.*;
@SuppressWarnings("unchecked")
public class E220 
{
   static long time = System.currentTimeMillis();
   public static void main(String[] args) throws Exception 
   {
      FastReader infile = new FastReader();
      //infile = new FastReader("text.in");
      int n = infile.nextInt();
      long k = infile.nextLong();
      int[] array = new int[n+1];
      int[] compress = new int[n+1];
      for(int x = 1; x <= n; x++)
      {
         compress[x] = array[x] = infile.nextInt();
      }
      Arrays.sort(compress);
      HashMap<Integer, Integer> map = new HashMap();
      int max = 0;
      for(int x = 1; x <= n; x++)
      {
         if(map.get(compress[x])==null)
         {
            map.put(compress[x], ++max);
         }
      }
      for(int x = 1; x <= n; x++)
         array[x] = map.get(array[x]);
      long count = 0;
      long cur = 0;
      long[] seg = new long[4*n+1];
      for(int x = 1; x <= n; x++)
      {
         cur+=sumQuery(1, 1, max, array[x]+1, max, seg);
         sumUpdate(1, 1, max, array[x], 1, seg);
      }
      seg = new long[4*max+1];
      for(int x = n; x >= 1; x--)
      {
         cur+=sumQuery(1, 1, max, 1, array[x]-1, seg);
         sumUpdate(1, 1, max, array[x], 1, seg);
      }
      if(cur%2==1)
      {
         throw new Exception();
      }
      cur/=2;
      long[] segl = new long[4*max+1];
      long[] segr = new long[4*max+1];
      for(int x = n; x >= 2; x--)
      {
         sumUpdate(1, 1, max, array[x], 1, segr);
      }
      sumUpdate(1, 1, max, array[1], 1, segl);
      int l = 1;
      int r = 2;
      cycle: while(l<n)
      {
         while(cur>k)
         {
            if(r==n)
               break cycle;
            cur-=sumQuery(1, 1, max, array[r]+1, max, segl);
            cur-=sumQuery(1, 1, max, 1, array[r]-1, segr);
            sumUpdate(1, 1, max, array[r], -1, segr);
            r++;
         }
         count+=n-r+1;
         sumUpdate(1, 1, max, array[l+1], 1, segl);
         l++;
         if(l==r)
         {
            if(r==n)
               break cycle;
            cur-=sumQuery(1, 1, max, array[r]+1, max, segl);
            cur-=sumQuery(1, 1, max, 1, array[r]-1, segr);
            sumUpdate(1, 1, max, array[r], -1, segr);
            r++;
         }
         cur+=sumQuery(1, 1, max, array[l]+1, max, segl);
         cur+=sumQuery(1, 1, max, 1, array[l]-1, segr);
         if(r>n)
            break;
      }
      StringBuilder sb = new StringBuilder();
      sb.append(count);   
      System.out.println(sb);
      //System.out.println("Time: "+(System.currentTimeMillis()-time));
   }
   public static void sumUpdate(int pos, int left, int right, int target, long add, long[] seg)
   {
      if(target<left||right<target)
      {
         return;
      }
      if(left==target&&right==target)
      {
         seg[pos]+=add;
         return;
      }
      int mid = (left+right)/2;
      sumUpdate(2*pos, left, mid, target, add, seg);
      sumUpdate(2*pos+1, mid+1, right, target, add, seg);
      seg[pos] = seg[2*pos]+seg[2*pos+1];
   }
   public static long sumQuery(int pos, int left, int right, int ltar, int rtar, long[] seg)
   {
      if(rtar<left||right<ltar)
      {
         return 0;
      }
      if(ltar<=left&&right<=rtar)
      {
         return seg[pos];
      }
      int mid = (left+right)/2;
      return sumQuery(2*pos, left, mid, ltar, rtar, seg)+sumQuery(2*pos+1, mid+1, right, ltar, rtar, seg);
   }
}
class FastReader
{
   BufferedReader br;
   StringTokenizer st;

   public FastReader(String file) throws FileNotFoundException
   {
      br = new BufferedReader(new FileReader(file));
   }
   
   public FastReader() throws FileNotFoundException
   {
      br = new BufferedReader(new InputStreamReader(System.in));
   }
 
   String next()
   {
      while (st == null || !st.hasMoreElements())
      {
         try
         {
            st = new StringTokenizer(br.readLine());
         }
         catch (IOException  e)
         {
            e.printStackTrace();
         }
      }
      return st.nextToken();
   }
 
   int nextInt()
   {
      return Integer.parseInt(next());
   }
 
   long nextLong()
   {
      return Long.parseLong(next());
   }
 
   double nextDouble()
   {
      return Double.parseDouble(next());
   }
 
   String nextLine()
   {
      String str = "";
      try
      {
         str = br.readLine();
      }
      catch (IOException e)
      {
         e.printStackTrace();
      }
      return str;
   }
}