Giải bài trực tuyến

Cho dãy số nguyên a 1 , a 2 , ..., a N và số nguyên M. Xét thuật toán đưa M số nhỏ nhất về đầu dãy như sau:

for i<-1 to M do
  for j<-i+1 to N do
    if a[i]>a[j] then
      swap(a[i],a[j])

Trong đó swap là hàm đổi giá trị của 2 biến cho nhau.

Cho số nguyên M và dãy số nguyên a 1 , a 2 , ..., a N . Hãy đếm số lần thực hiện hàm swap sau khi

thuật toán kết thúc.

Input

Gồm nhiều bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng 1: Hai số nguyên dương N và M với 0 < N, M <= 10^5 .

Dòng 2: N số nguyên thể hiện dãy a, mỗi số cách nhau ít nhất 1 dấu cách. -10^9 ≤ a i ≤ 10^9.

Output

Ứng với mỗi test, in ra 1 dòng duy nhất chứa số lần thực hiện hàm swap theo yêu cầu bài toán

Example

Input:
3 3
2 1 3
4 1
3 2 -1 -10

Output:
1

3