https://www.acmicpc.net/problem/1021
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
deque<int> dq;
queue<int> v;
int N, M, tmp, answer = 0;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> tmp;
v.push(tmp);
}
for (int i = 1; i <= N; i++)
{
dq.push_back(i);
}
while (!v.empty())
{
int target = v.front();
int front_cnt = 0;
int back_cnt = 0;
int min_cnt = 0;
deque<int> dq_cp1 = dq, dq_cp2 = dq;
tmp = dq_cp1.front();
while (1)
{
if (dq_cp1.front() == target)
break;
front_cnt++;
dq_cp1.pop_front();
dq_cp1.push_back(tmp);
tmp = dq_cp1.front();
}
tmp = dq_cp2.front();
while (1)
{
if (dq_cp2.back() == target)
break;
back_cnt++;
tmp = dq_cp2.back();
dq_cp2.pop_back();
dq_cp2.push_front(tmp);
tmp = dq_cp2.back();
}
answer += min(front_cnt, back_cnt + 1);
if (front_cnt <= back_cnt)
{
for (int i = 0; i < front_cnt; i++)
{
tmp = dq.front();
dq.pop_front();
dq.push_back(tmp);
}
dq.pop_front();
}
else
{
for (int i = 0; i < back_cnt; i++)
{
tmp = dq.back();
dq.pop_back();
dq.push_front(tmp);
}
dq.pop_back();
}
v.pop();
}
cout << answer;
return 0;
}