220_E. Little Elephant and Inversions
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
```python
'''
Created on 19/07/2018

@author: ernesto
'''

# XXX: http://codeforces.com/problemset/problem/220/E
#  XXX: https://practice.geeksforgeeks.org/problems/magic-triplets/0


# XXX: https://gist.github.com/robert-king/5660418
class RangeBit:

    def __init__(self, n):
        sz = 1
        while n >= sz:
            sz *= 2
        self.size = sz
        self.dataAdd = [0] * sz
        self.dataMul = [0] * sz

    def sum(self, i):
        r = 0
        if i > 0:
            add = 0
            mul = 0
            start = i
            while i > 0:
                add += self.dataAdd[i]
                mul += self.dataMul[i]
                i -= i & -i
            r = mul * start + add
        return r

    def add(self, left, right, by):
        assert 0 < left <= right
        self._add(left, by, -by * (left - 1))
        self._add(right, -by, by * right)

    def _add(self, i, mul, add):
        assert i > 0
        while i < self.size:
            self.dataAdd[i] += add
            self.dataMul[i] += mul
            i += i & -i
    
    def sum_range(self, i, j):
#        print("j {} s {}".format(j, self.sum(j)))
#        print("i {} s {}".format(i, self.sum(i)))
        return self.sum(j) - self.sum(i - 1)

    def sum_back(self, i):
        return self.sum_range(i, self.size - 1)
    
    def add_point(self, i, by):
        self.add(i, i, by)

    
class numero():

    def __init__(self, valor, posicion_inicial):
        self.valor = valor
        self.posicion_inicial = posicion_inicial
        self.posicion_final = -1;
    
    def __lt__(self, other):
        if self.valor == other.valor:
            r = self.posicion_inicial < other.posicion_inicial
        else:
            r = self.valor < other.valor
        return r

    def __repr__(self):
        return "{}:{}:{}".format(self.valor, self.posicion_inicial, self.posicion_final)


def swap(a, i, j):
    a[i], a[j] = a[j], a[i]


def crea_arreglo_enriquecido(nums):
    numse = list(sorted(map(lambda t:numero(t[1], t[0]), enumerate(nums))))
    r = [0] * len(nums)
#    print("numse {}".format(numse))
    for i, n in enumerate(numse):
        r[n.posicion_inicial] = i + 1
    return r


def fuerza_bruta(a):
    a_len = len(a)
    r = 0
    for i in range(a_len):
        for j in range(i):
            if a[i] < a[j]:
                r += 1
    return r


def quita(bi, bd, a, i):
    return modifica(bi, bd, a, i, False)


def anade(bi, bd, a, i):
    return modifica(bi, bd, a, i, True)


def modifica(bi, bd, a, i, anade):
    if anade:
        bc = bi
        fac = 1
    else:
        bc = bd
        fac = -1
        
    inv = bi.sum_back(a[i] + 1) + bd.sum(a[i] - 1)
#    print("num {} parte de i {} de d {} fact {}".format(a[i], bi.sum(a[i] + 1), bd.sum(a[i] - 1), fac))
    bc.add_point(a[i], fac)
    
    return inv


def core(nums, nmi):
    numse = crea_arreglo_enriquecido(nums)
#    print("numse {}".format(numse))
    a = numse
#    print("a {}".format(list(map(lambda x:x - 1, a))))
    i = 0
    j = 0
    ni = 0
    r = 0
    a_len = len(a)
    
    bitch_izq = RangeBit(a_len + 2)
    bitch_der = RangeBit(a_len + 2)
    
    nif = 0
    for i, x in enumerate(a):
        nif += bitch_der.sum_range(x + 1, a_len)
        bitch_der.add(x, x, 1)
#        print("en x {} ({}) nif {}".format(x, numse[i].valor , nif))

    j = 0
    ni = nif
#    print("ni ini {}".format(ni))
    ni += anade(bitch_izq, bitch_der, a, 0)
    for i in range(1, a_len):
        while j < a_len and (j < i or ni > nmi):
            ni -= quita(bitch_izq, bitch_der, a, j)
#            print("en j {} se kito {} {}".format(j, nums[j], ni))
            j += 1
        r += a_len - j
#        print("en i {} j {} anadido {} inv {}".format(i, j, a_len - j, ni))
        ni += anade(bitch_izq, bitch_der, a, i)
#        print("en i {} se puso {}".format(i, ni))
        
#    print("r f aora {}".format(r))
        
    return r


_, k = [int(x) for x in input().strip().split(" ")]
nums = [int(x) for x in input().strip().split(" ")]
# nums = [6, 8, 6, 7, 2, 4, 2, 1, 7, 6, 2, 1, 2, 3, 2, 5, 3, 7, 1, 7, 7]
# nums = [1, 3, 2, 1, 7]
# nums = [1, 3, 2]
# k = 0

print(core(nums, k))

```