题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_{n}$ 和一个整数 $k$。将数列 $a$ 重复 $k$ 次，得到长度为 $n\times k$ 的循环数列 $A$，$A$ 的正式定义如下：

• $A$ 的前 $n$ 项等于 $a$ 的前 $n$ 项——对于 $1\leq i\leq n$，有 $A_i = a_{i}$；
• 之后每个 $A$ 的元素 $A_i$，都有 $A_i = A_{i-n}$；

如果能够找到一对整数 $(i,j)$，满足 $i < j$ 且 $A_i > A_j$，则 $(i,j)$ 就是一对逆序对。请求出 $A$ 中的逆序对数量。

输入格式

• 第一行：两个整数 $n$ 与 $k$；
• 第二行：$n$ 个整数 $a_1, a_2, \cdots, a_{n}$。

输出格式

• 单个整数：表示 $A$ 中逆序对数量。

3 2
3 1 4

5

数据范围

• 对于 $20\%$ 的数据，保证 $1 \le k \le 10$；
• 对于 $40\%$ 的数据，保证 $1\le k \le 5000$；
• 对于 $60\%$ 的数据，保证 $1\le k \le 100000$；
• 对于 $100\%$ 的数据，保证 $1 \le k \le 1000000$
• $1\le n \le 5000$, $1\le a_i \le 5000$。