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
# 220E
import sys
from collections import defaultdict
 
class BIT():
    def __init__(self, n):
        self.n = n
        self.tree = [0] * n
    
    def _F(self, i):
        return i & (i + 1)
    
    def _get_sum(self, r):
        '''
        sum on interval [0, r)
        '''
        result = 0
        while r > 0:
            result += self.tree[r-1]
            r = self._F(r-1)
        return result
    
    def get_sum(self, l, r):
        '''
        sum on interval [l, r)
        '''
        return self._get_sum(r) - self._get_sum(l)
    
    def _H(self, i):
        return i | (i + 1)
    
    def add(self, i, value=1):
        while i < self.n:
            self.tree[i] += value
            i = self._H(i)

reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

n, k = map(int, input().split())
a = list(map(int, input().split()))

pos = defaultdict(list)
for i, val in enumerate(a):
    pos[val].append(i)

i = 0
prev = -1
for val in sorted(a):
    if prev == val: continue
    for j in pos[val]:
        a[j] = i
    i += 1
    prev = val

left = BIT(n)
right = BIT(n)
total_inv = 0

left.add(a[0])
for t in range(1, n):
    i = a[t]
    total_inv += right.get_sum(i+1, n)
    right.add(i)
    if i < a[0]:
        total_inv += 1

if total_inv <= k:
    print((n*(n-1))>>1)
    sys.exit()

l = 0
r = 1
while r < n and total_inv > k:
    total_inv -= left.get_sum(a[r]+1, n) + right.get_sum(0, a[r])
    right.add(a[r], -1)
    r += 1

pairs = 0
while r < n:
    while True:
        add = left.get_sum(a[l+1]+1, n) + right.get_sum(0, a[l+1])
        if total_inv + add > k:
            pairs += l + 1
            break
        else:
            l += 1
            total_inv += add
            left.add(a[l])
    total_inv -= left.get_sum(a[r]+1, n) + right.get_sum(0, a[r])
    right.add(a[r], -1)
    r += 1
print(pairs)
