The state of the economy is bad, the crisis is striking the country and people are losing their jobs. However, Sisyphus, the main hero of this task, has found himself a new job. Starting next Monday, Sisyphus will be an assistant locksmith in a hotel. Naturally, first he needs to demonstrate his locksmithing abilities to the head locksmith.

This is why the head locksmith has given Sisyphus ~N~ keys on a big round pendant, blindfolded him and led him into a big room. That room contains ~N~ locked doors, denoted with numbers from ~1~ to ~N~. Each of the keys on the pendant unlocks precisely one door.

Sisyphus' job is to unlock and lock each door again. He does this in a way that he moves along the wall, not changing direction, until he reaches a door. When he reaches a door, he tries unlocking it using the first (leftmost) key. In the case when the key doesn't unlock the door, Sisyphus moves it to the other (right) side of pendant and repeats this procedure until he finds the right key. His work is done when he goes through all the doors. The first door Sisyphus unlocked is denoted with 1, the next with 2, the one after with 3 and so on…

What Sisyphus doesn't know is that the head locksmith is, in fact, testing his endurance so he led him into a circular room. Therefore, Sisyphus will, after unlocking and locking the last door, go unlocking and locking the first door again. Because he's a hardworking and persistent fellow, Sisyphus has been doing this job for hours and hours without saying a single word. Only after the ~K^{th}~ successful unlocking and locking of a door he spoke: "If only I knew how many times so far I've put a wrong key in a door's lock!" Your task is to answer his question!

Input

The first line of input contains the integers ~N~ ~(1 \le N \le 10^5)~ and ~K~ ~(1 \le K \le 10^9)~ from the task.

The ~i^{th}~ of the following ~N~ lines contains the integer ~v_i~ ~(1 \le v_i \le N)~ which denotes that the ~i^{th}~ key on the pendant (from left to right) unlocks the door ~v_i~.

Output

The first and only line of output must contain an integer representing the answer to Sisyphus' question.

Scoring

In test cases worth 40% of total points, it will hold ~1 \le N, K \le 1\,000~.

In test cases worth 60% of total points, it will hold ~1 \le K \le 50\,000~.

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

Explanation for Sample Output 2

The first locking/unlocking (door 1) – keys (left to right): 4 2 1 3

The second locking/unlocking (door 2) – keys (left to right): 1 3 4 2

The third locking/unlocking (door 3) – keys (left to right): 2 1 3 4

The fourth locking/unlocking (door 4) – keys (left to right): 3 4 2 1

The fifth locking/unlocking (door 1) – keys (left to right): 4 2 1 3

The sixth locking/unlocking (door 2) – keys (left to right): 1 3 4 2

The misplaced keys are bolded.

Sample Input 3

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

Sample Output 3

25