BOJ 1021. 회전하는 큐

[hojongs]

https://www.acmicpc.net/problem/1021

Impl plan

in:
3 3
1 2 3
out:
0
explain:
1,2,3
2,3
3

in:
3 3
2 3 1
out:
1
explain:
1,2,3
2,3,1*
3,1
1

in:
10 3
2 9 5
out:
8
explain:
1,2,3,4,5,6,7,8,9,10
2,3,4,5,6,7,8,9,10,1 (1)
3,4,5,6,7,8,9,10,1 (3 or 6, len=9)
9,10,1,3,4,5,6,7,8 (3 or 6, len=9)
10,1,3,4,5,6,7,8
5,6,7,8,10,1,3,4 (4, len=8)
6,7,8,10,1,3,4

Impl

from collections import deque
import sys
readl = sys.stdin.readline

n, m = [int(i) for i in readl().split()]
nums = [int(i) for i in readl().split()]
que = deque(range(1, n+1))
cnt_total = 0
for num in nums:
    cnt = 0
    while que[0] != num:
        que.append(que.popleft())
        cnt += 1
    cnt_total += min(cnt, len(que)-cnt)
    que.popleft()
print(cnt_total)