Gọi \(\pi=\left(p_1, p_2,..., p_n\right)\) là một hoán vị của \((1, 2,...,n)\), một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) nhưng \(p_i > p_j\).

Cho một hoán vị \(\pi_0\) và số nguyên dương \(k\), xét \(k\) hoán vị liên tiếp \(\pi_0\), \(\pi_1\),..., \(\pi_{k-1}\) kể từ hoán vị \(\pi_0\), hãy tính tổng \(f(\pi_0)+f(\pi_1)+...+f(\pi_{k-1})\) với \(f(\pi)\) là số lượng cặp nghịch thế trong hoán vị \(\pi\).

Input

Dòng đầu chứa hai số nguyên dương \(n\), \(k\) lần lượt là kích thước của hoán vị \(\pi_0\) và số lượng hoán vị liên tiếp cần xét.

Dòng tiếp theo chứa \(n\) số nguyên dương \(p_1\), \(p_2\),..., \(p_n\) mô tả hoán vị \(\pi_0\).

Dữ liệu đảm bảo luôn tồn tại ít nhất \(k\) hoán vị hợp lệ kể từ hoán vị \(\pi_0\) trở đi.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Input

5 4
1 2 3 4 5

Output

4

Giải thích

• Hoán vị \(\pi_0=(1,2,3,4,5)\) không có cặp nghịch thế nào.
• Hoán vị \(\pi_1=(1,2,3,5,4)\) có một cặp nghịch thế là \((4, 5)\).
• Hoán vị \(\pi_2=(1,2,4,3,5)\) có một cặp nghịch thế là \((3, 4)\).
• Hoán vị \(\pi_3=(1,2,4,5,3)\) có hai cặp nghịch thế là \((3, 5)\) và \((4, 5)\).

Vậy tổng số nghịch thế là \(0+1+1+2=4\).

Ràng buộc

• Subtask 1 (40 điểm): \(n\leq 10^3, k\leq 10\).
• Subtask 2 (40 điểm): \(n\leq 10^5, k\leq 10\).
• Subtask 3 (20 điểm): \(n\leq 10^5, k\leq 10^5\).