Reading List

Mirko is a model student, yet he has always struggled with his required reading. This year he decided to put an end to it. He got hold of all $N$ books that the teacher can assign as required reading, numbered from $1$ to $N$. He stacked them all into a single tower from the smallest number to the largest, so book $1$ is at the top of the tower.

Each time the teacher assigns book $L_i$, Mirko has to pull it out of the tower to read it. He does this by lifting all the books above book $L_i$, pulling out book $L_i$, and putting the lifted books back down on the tower. After Mirko finishes reading book $L_i$, he puts it back on top of the tower. Book $L_i$ also counts as a lifted book.

Mirko reads the book numbered $3$

For example, look at the tower in the figure. If the first assigned book is book $3$, Mirko lifts three books, numbered $1$, $2$ and $3$. He then puts books $1$ and $2$ back down. After he reads book $3$, he places it on top of the tower.

You are given the sequence $L$ of books the teacher will assign. Compute how many books Mirko lifts in total this school year to read all the assigned books.

The first line contains two positive integers $N$ and $Q$ ($1 \le N, Q \le 100000$), the number of books and the number of assignments.

The second line contains $Q$ positive integers $L_1, L_2, \ldots, L_Q$ ($1 \le L_i \le N$), the assigned books in order.

Some books may never be assigned. A book may also be assigned more than once, in which case Mirko must read it again.

Print a single positive integer on the first line: the total number of books Mirko lifts.

Consider $4$ books assigned in the order $1$, $3$, $2$. Listing the tower from top to bottom, it changes as follows.

• $(1, 2, 3, 4) \to (1, 2, 3, 4)$: only book $1$ is lifted.
• $(1, 2, 3, 4) \to (3, 1, 2, 4)$: books $1$, $2$ and $3$ are lifted.
• $(3, 1, 2, 4) \to (2, 3, 1, 4)$: books $1$, $2$ and $3$ are lifted.

In total Mirko lifts $1 + 3 + 3 = 7$ books.