Find Min Sync Time (Circular Servers)

Servers numbered 1..total form a ring, and moving between adjacent servers takes 1. You may start at any server in the list to visit. Find the shortest time to visit all the specified servers.

输入格式

The first line contains total n (1≤n≤total≤100000); the second line contains the n server numbers to visit (1..total). A repeated number only needs to be visited once.

输出格式

Output a single integer, the answer.

样例 1

输入：

8 3
2 4 7

输出：

5

样例 2

输入：

5 1
3

输出：

0

样例 3

输入：

4 4
1 2 3 4

输出：

3

样例说明

Example 1: the largest gap has length 3, and the ring length 8 minus 3 gives 5; for example, going from 4 toward 2 and then around to 7 takes 5 steps in total. Example 2: there is only one target, so you start there and the time is 0. Example 3: walking 3 consecutive steps along the ring visits all four points.