Problem Background

A country is experiencing severe economic difficulties due to a freezing disaster, causing people to lose their jobs. However, Sisyphus, the protagonist of this problem, has found a new job for himself. Starting next Monday, Sisyphus will become an assistant locksmith at a hotel. Of course, he first needs to demonstrate his lock-picking skills to the head locksmith.

Problem Description

This is why the head locksmith has given Sisyphus $n$ keys on a large circular pendant, blindfolded him, and led him into a large room. This room contains exactly $n$ locked doors, numbered from $1$ to $n$. Each key on the pendant can open exactly one door, with the $i$-th key able to open the door numbered $v_i$. Sisyphus's task is to unlock and relock each door. He does this by moving along the wall without changing direction until he reaches a door. When he reaches a door, he attempts to unlock it with the first key to his left. If the key does not unlock the door, Sisyphus discards it to the rightmost position and tries the next key to his left, repeating this process until he finds the correct key. His job is complete when all doors are unlocked. The first door Sisyphus unlocks is denoted by $1$, the next by $2$, and so on...

What Sisyphus doesn't know is that the head locksmith is actually testing his endurance, so he has been led into a circular room. Therefore, after unlocking and relocking the last door, Sisyphus will return to unlock and relock the first door again. Being a diligent and persistent individual, Sisyphus has been working silently for several hours. Only after successfully unlocking and relocking for the $k$-th time does he speak: "I wish I knew how many times I've inserted the wrong key into a lock so far!" Your task is to answer his question.

Input Format

The input consists of $n+1$ lines.

The first line contains two integers $n$ and $k$, representing the number of keys Sisyphus has and the number of successful unlock-relock operations he has performed so far, respectively.
The following $n$ lines each contain an integer $v_i$, indicating the door number that the $i$-th key can open.

Output Format

Output a single line containing the number of times Sisyphus has inserted the wrong key into a lock.

Sample Input and Output

Sample Input #1

3 5
1
2
3

Sample Output #1

4

Sample Input #2

4 6
4
2
1
3

Sample Output #2

13

Sample Input #3

10 7
1
3
2
4
5
7
6
8
9
10

Sample Output #3

25

Notes

[Sample 2 Explanation]

Here is how Sisyphus uses the keys, with a red number indicating an incorrect key insertion:

• For door $1$: $\color{Red}4~2~\color{default}1~3$
• For door $2$: $\color{Red}1~3~4~\color{default}2$
• For door $3$: $\color{Red}2~1~\color{default}3~4$
• For door $4$: $\color{Red}3~\color{default}4~2~1$
• For door $1$: $\color{Red}4~2~\color{default}1~3$
• For door $2$: $\color{Red}1~3~4~\color{default}2$

Thus, the total number of incorrect key insertions is $2+3+2+1+2+3=13$.

[Data Range]

For $40\%$ of the data, $1 \leqslant n, k \leqslant 1000$.
For $60\%$ of the data, $1 \leqslant k \leqslant 5 \times 10^4$.
For all data, $1 \leqslant v_i \leqslant n \leqslant 10^5$, $1 \leqslant k \leqslant 10^9$.

[Problem Source]

This problem is from COCI 2014-2015 CONTEST 7 T2 KRIZA, configured with the original data, worth $80$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分