codeforces C. Ryouko's Memory Note

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <cmath>
 7 #define maxn 100010
 8 #define ll __int64
 9 using namespace std;
10 const int mod=1000000007;
11 const int inf=1<<30;
12 
13 int n,m;
14 ll a[maxn];
15 int sum[maxn];
16 int p[maxn];
17 vector<int>g[maxn];
18 
19 int main()
20 {
21     cin>>n>>m;
22     ll sum=0,max1=0;
23     for(int i=1; i<=m; i++)
24     {
25         scanf("%I64d",&a[i]);
26         max1=max(max1,a[i]);
27         if(i==1)continue;
28         if(a[i]!=a[i-1])
29         {
30             g[a[i-1]].push_back(a[i]);
31             g[a[i]].push_back(a[i-1]);
32             sum+=abs(a[i]-a[i-1]);
33         }
34     }
35     ll ans=sum;
36     for(int i=1; i<=max1; i++)
37     {
38         ll tem=sum;
39         if(!g[i].size()) continue;
40         sort(g[i].begin(),g[i].end());
41         int xx=g[i][g[i].size()/2];
42         for(int j=0; j<(int)g[i].size(); j++)
43         {
44            tem+=(abs(xx-g[i][j])-abs(i-g[i][j]));
45         }
46         ans=min(ans,tem);
47     }
48     printf("%I64d\n",ans);
49     return 0;
50 }