Problem K: 循环逆序对

Problem K: 循环逆序对

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

给定一个长度为 lns="http://www.w3.org/1998/Math/MathML">n 的数列 lns="http://www.w3.org/1998/Math/MathML">a1,a2,,an 和一个整数 lns="http://www.w3.org/1998/Math/MathML">k。将数列 lns="http://www.w3.org/1998/Math/MathML">a 重复 lns="http://www.w3.org/1998/Math/MathML">k 次,得到长度为 lns="http://www.w3.org/1998/Math/MathML">n×k 的循环数列 lns="http://www.w3.org/1998/Math/MathML">Alns="http://www.w3.org/1998/Math/MathML">A 的正式定义如下:

  • lns="http://www.w3.org/1998/Math/MathML">A 的前 lns="http://www.w3.org/1998/Math/MathML">n 项等于 lns="http://www.w3.org/1998/Math/MathML">a 的前 lns="http://www.w3.org/1998/Math/MathML">n 项——对于 lns="http://www.w3.org/1998/Math/MathML">1in,有 lns="http://www.w3.org/1998/Math/MathML">Ai=ai
  • 之后每个 lns="http://www.w3.org/1998/Math/MathML">A 的元素 lns="http://www.w3.org/1998/Math/MathML">Ai,都有 lns="http://www.w3.org/1998/Math/MathML">Ai=Ain

如果能够找到一对整数 lns="http://www.w3.org/1998/Math/MathML">(i,j),满足 lns="http://www.w3.org/1998/Math/MathML">i<j 且 lns="http://www.w3.org/1998/Math/MathML">Ai>Aj,则 lns="http://www.w3.org/1998/Math/MathML">(i,j) 就是一对逆序对。请求出 lns="http://www.w3.org/1998/Math/MathML">A 中的逆序对数量。

Input

  • 第一行:两个整数 lns="http://www.w3.org/1998/Math/MathML">n 与 lns="http://www.w3.org/1998/Math/MathML">k
  • 第二行:lns="http://www.w3.org/1998/Math/MathML">n 个整数 lns="http://www.w3.org/1998/Math/MathML">a1,a2,,an

数据范围

  • 对于 lns="http://www.w3.org/1998/Math/MathML">20% 的数据,保证 lns="http://www.w3.org/1998/Math/MathML">1k10
  • 对于 lns="http://www.w3.org/1998/Math/MathML">40% 的数据,保证 lns="http://www.w3.org/1998/Math/MathML">1k5000
  • 对于 lns="http://www.w3.org/1998/Math/MathML">60% 的数据,保证 lns="http://www.w3.org/1998/Math/MathML">1k100000
  • 对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据,保证 lns="http://www.w3.org/1998/Math/MathML">1k1000000
  • lns="http://www.w3.org/1998/Math/MathML">1n5000lns="http://www.w3.org/1998/Math/MathML">1ai5000

Output

  • 单个整数:表示 lns="http://www.w3.org/1998/Math/MathML">A 中逆序对数量。

Sample Input Copy

3 2
3 1 4

Sample Output Copy

5