책 정리 로봇

일렬로 놓인 $N$ 개의 칸으로 이루어진 책장이 있다. 책장의 각 칸에 책이 한 개씩 총 $N$ 개의 책이 놓여있다. 맨 왼쪽 칸의 위치는 $1$이고, 맨 오른쪽 칸의 위치는 $N$이다. 위치 $i$에 놓인 책에는 정수 $A_i$가 적혀있다.

에띠는 책 정리 로봇을 개발하고 있다. 이 로봇은 처음에 위치 $1$에서 시작하여 각 칸 사이를 이동하며 책을 선택하여 바구니에 담는다.

로봇이 책장의 모든 책을 바구니에 담을 때, 담는 책에 적힌 수는 단조증가이어야 한다. 다시 말해, $1$ 이상 $N$ 미만인 $i$에 대해 $i$ 번째로 선택한 책에 적힌 수는 $i+1$ 번째로 선택한 책에 적힌 수보다 같거나 작아야 한다. 이렇게 로봇이 책을 바구니에 담을 때, 로봇의 최소 이동 거리를 구하자.

입력 형식

첫 줄에 책장의 칸 수와 책의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

둘째 줄에 각 책에 적힌 수를 나타내는 정수 $N$ 개가 공백으로 구분되어 주어진다. $i$ 번째로 주어지는 수는 위치 $i$에 놓인 책에 적혀있는 수 $A_i$를 의미한다. ($1 \le A_i \le 1\,000\,000\,000$)

출력 형식

책 정리 로봇이 위치 $1$에서 시작하여 책에 적힌 수에 대해 단조증가 순서로 바구니에 담을 때, 로봇의 최소 이동 거리를 출력한다.

예제 1

6
2 1 2 2 1 3

13

예제 2

10
1 2 3 4 5 6 4 3 2 1

29

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설