Tab Hopping

Interview

Time limit2sMemory limit1024 MB

Summary

Given n tabs in a cycle and a sequence of tabs to visit, find the minimum total number of forward or backward steps starting from tab 1.

Level: Easy2 of 10
Topics: Simulation, Implementation, Math, Greedy
Solved: No attempts yet

Problem

When you work with a web browser, you often have a great many tabs open at once.

A common way to move between them is to ctrl-tab through them in the order they sit in. You can also ctrl-shift-tab through them in reverse order. The tabs can be thought of as sitting in a cycle, so you can ctrl-tab from the last tab to the first, and ctrl-shift-tab from the first tab to the last.

Right now you have n tabs open, numbered from $1$ to $n$ in the order they sit in. Initially tab $1$ is selected. Given a sequence describing which tabs to use and in what order, compute the minimum number of times you must press the tab key to visit them.

Input

The first line contains two positive integers less than $10$ , $n$ and $m$ . The next line contains $m$ integers, each between $1$ and $n$ inclusive. Two adjacent numbers are always different.

Output

Print one integer, the minimum number of times the tab key must be pressed.

Examples2

Example 1
Input
```
5 3
2 5 4
```
Expected output
```
4
```
Example 2
Input
```
9 5
5 9 4 9 8
```
Expected output
```
17
```