Background

A certain country is in very bad economic condition. An ice disaster has hit the whole country, and people are losing their jobs. However, Sisyphus, the main character of this problem, has already found himself a new job. Starting next Monday, Sisyphus will become an assistant locksmith in a hotel. Of course, he first needs to show the head locksmith his lock-opening skills.

Problem Description

This is why the head locksmith gave Sisyphus $n$ keys on a large round keychain, blindfolded him, and led him into a large room. In this room there are exactly $n$ locked doors, labeled with numbers from $1$ to $n$. Each key on the keychain can open exactly one door; the $i$-th key can open door $v_i$. Sisyphus’s job is to unlock and then lock each door again. He does this by moving along the wall without changing direction until he reaches a door. When he arrives at a door, he tries to unlock it using the leftmost key at that moment. If the key does not open the lock, Sisyphus moves it to the far right and tries again with the new leftmost key, repeating this process until he finds the correct key. When he has unlocked all doors, his job is done. The first door Sisyphus opens is labeled $1$, the next one is labeled $2$, then $3$, and so on...

What Sisyphus does not know is that the head locksmith is actually testing his endurance, so he brought him into a circular room. Therefore, after unlocking and locking the last door, Sisyphus will again unlock and lock the first door. Since he is a hardworking and persistent guy, Sisyphus keeps doing this job for hours without saying a word. Only after the $k$-th successful unlock-and-lock operation does he speak: "If only I knew how many times so far I have put a wrong key into a door lock!" Your task is to answer his question.

Input Format

The input contains $n+1$ lines.

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

Output Format

Output only one line, the number of times Sisyphus put a wrong key into a door lock.

3 5
1
2
3

4

4 6
4
2
1
3

13

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

25

Hint

[Sample 2 Explanation]

Below is how Sisyphus uses the keys. A red number means he put a wrong key into the lock once:

• Unlocking and locking door $1$: $\color{Red}4~2~\color{default}1~3$
• Unlocking and locking door $2$: $\color{Red}1~3~4~\color{default}2$
• Unlocking and locking door $3$: $\color{Red}2~1~\color{default}3~4$
• Unlocking and locking door $4$: $\color{Red}3~\color{default}4~2~1$
• Unlocking and locking door $1$: $\color{Red}4~2~\color{default}1~3$
• Unlocking and locking door $2$: $\color{Red}1~3~4~\color{default}2$

Therefore, the total number of times he put a wrong key into a lock is $2+3+2+1+2+3=13$.

[Constraints]

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

[Source]

This problem is from COCI 2014-2015 CONTEST 7 T2 KRIZA, using the original testdata settings, with a full score of $80$ points.

Translated and整理 (pinyin: zhengli, edited/organized) by Eason_AC.

Translated by ChatGPT 5