Sắp xếp

Điểm: 1,82 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

HSPC 2014

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy số nguyên ~a_1~, ~a_2~, ..., ~a_N~ và số nguyên ~M~. Xét thuật toán đưa ~M~ số nhỏ nhất về đầu dãy như 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 đó ~swap~ là hàm đổi giá trị của ~2~ biến cho nhau.

Cho số nguyên ~M~ và dãy số nguyên ~a_1~, ~a_2~, ..., ~a_N~. Hãy đếm số lần thực hiện hàm ~swap~ sau khi thuật toán kết thúc.

Input

Gồm nhiều bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng ~1~: Hai số nguyên dương ~N~ và ~M~ với ~0 < N~, ~M \le 10^{5}~.

Dòng ~2~: ~N~ số nguyên thể hiện dãy ~a~, mỗi số cách nhau ít nhất ~1~ dấu cách. ~- 10^{9} \leq a_i \leq 10^{9}~.

Output

Ứng với mỗi test, in ra ~1~ dòng duy nhất chứa số lần thực hiện hàm ~swap~ theo yêu cầu bài toán.

Sample Input

Sample Output

1
3

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.