Инверзије након избацивања сегмената

Дат је низ \(a\), који се састоји од \(n\) позитивних целих бројева. Написати програм који ће да преброји колико има парова бројева \(l\) и \(r\) таквих да је \(1 \leq l < r \leq n\) и да низ \(b = a_1a_2\ldots a_la_ra_{r+1}\ldots a_n\) нема више од \(k\) инверзија.

Два цела броја у низу \(b\) образују инверзију када се већи број појављује пре мањег броја, тј. за пар \(b_i, b_j\) чланова низа \(b\) кажемо да образују инверзију ако важи да је \(1 \leq i < j \leq |b|\) и \(b_i > b_j\), где је \(|b|\) величина низа \(b\).

Улаз

У првој линији стандардног улаза дата су два цела броја \(k\) и \(n\) (\(2 \leq n \leq 10^5, 0 \leq k \leq 10^{18}\)) – максималан број дозвољених инверзија и величина низа \(a\). Следећа линија садржи \(n\) позитивних целих бројева раздвојених са по једним размаком \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) – елементи низа \(a\).

Излаз

У јединој линији стандардног излаза исписати само један број – број парова (решење задатка).

Пример 1

Улаз

1
3
1 3 2

Излаз

3

Пример 2

Улаз

0
3
1 3 2

Излаз

1

Пример 3

Улаз

2
5
1 5 4 1 100

Излаз

6

Пример 4

Улаз

4
5
1 5 4 1 100

Излаз

10