首先，这个题卡内存。开10000000大小的数组会直接MLE，short都不行。
其次，有重复数据，不能简单地用bool数据记录某一个位置是否有洞。
第三，O(10000000)的线性时间（尽管常数也不大）会爆。有些同样1s的题，也许O(N^2),N<10000可以轻松水过，
这个题10^7的线性会TLE，关于这一点我想了一会，估计是因为这里的10^7是实打实的10^7，也就是
对每一组厕试数据都是10^7（单组数据在笨地运行还是很快的）。

由于以上3点，直接开10000000的壮態数组扫一遍是不可行的，因此需要离散化

记录N个洞的位置，并排好序。首先容易证明最后移动到的最优位置一定在某个洞处（这是因为，无论最终选在神马位置，从这个位置的对面（即相距5000000的点）拆开，可以化成熟知的直线上最短距离和问题）。因此可以对这100000个点扫描，复杂度是O(10^6)
一种比较妈的情况是，存在两个相邻点之间的顺时针距离大于等于5000000，这个时猴以它们为端点展开成直线问题即可（注意这种情况也涵盖了所有点乡党的极端情形）

一般情况下，设好初始值为第0个洞点之后，在每一次往顺时针方向移动的过程中，圆周被分成4个小段。每个小段中的点，对于原来的和即将选取的合并点或者均为顺时针较近，或者均为逆时针较近。
每次分别计算这四个段中的距离的改变值，然后更新分割四个段的临界下标即可。

最后，我的代妈长度是2333B，yeah~

#include <iostream>
#include <stdio.h>
using namespace std;

int pos[100000];

int gs = 0;

int mn(int a, int b){
	return (a>b) ? b : a;
}

int cwDist(int i1, int i2){
	if(i1 <= i2) return pos[i2]-pos[i1];
	return pos[i2] + 10000000 - pos[i1];
}

int dist(int i1, int i2){
	int cwd = cwDist(i1, i2);
	if(cwd <= 5000000) return cwd;
	return 10000000-cwd;
}

int geshu(int i1, int i2){
	//i1到i2的前闭后开区间的数的个数
	if(i1 <= i2) return i2-i1;
	return i2+gs-i1;
}

void quickSort(int s[], int l, int r)
{
    if (l< r)
    {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j]>= x)
                j--;
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i]< x)
                i++;
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        quickSort(s, l, i - 1);
        quickSort(s, i + 1, r);
    }
}

int main() {
	scanf("%d", &gs);
	for(int i = 0; i < gs; i++){
		int temp;
		scanf("%d", &temp);
		temp --;
		pos[i] = temp;
	}
	quickSort(pos, 0, gs-1);
	int zg = -1, xg = -1;
	for(int i = 0; i < gs; i++){
		int xyg = (i+1)%gs;
		if(cwDist(i, xyg) >= 5000000){
			zg = i;
			xg = xyg;
			break;
		}
	}
	if(zg != -1){
		//存在两个点，下标分别为zg和xg，顺时针相邻，且相距大于一半。此时它们一定是端点。
		long long int res = 0;
		for(int i = 0; i < gs/2; i++){
			res += cwDist((xg+i)%gs, (zg+gs-i)%gs);
		}
		printf("%I64d\n", res);
		return 0;
	}
	int idx = 0;
	int cwIdx = 0;
	long long int res = 0;
	for(int i = 0; i < gs; i++){
		int tempDis = cwDist(0, i);
		if(tempDis < 5000000){
			cwIdx ++;
			res += tempDis;
		}
		else{
			res += (10000000-tempDis);
		}
	}
	long long int tempRes = res;
	while(1){
		int newIdx = idx;
		while(pos[newIdx] == pos[idx]){
			newIdx ++;
		}
		if(newIdx >= gs) break;
		long long int L = pos[newIdx] - pos[idx];
		//idx和newIdx把圆周分成4段
		//第一段：
		tempRes += ((long long int)(newIdx - idx)) * L;
		//第三段：
		int newCwIdx = cwIdx;
		while(cwDist(newIdx, newCwIdx) < 5000000){
			tempRes -= dist(idx, newCwIdx);
			tempRes += dist(newIdx, newCwIdx);
			newCwIdx = (newCwIdx + 1) % gs;
		}
		//第二段：
		tempRes -= L * ((long long int)(geshu(newIdx, cwIdx)));
		//第四段：
		tempRes += L * ((long long int)(geshu(newCwIdx, idx)));
		if(tempRes < res) res = tempRes;
		idx = newIdx;
		cwIdx = newCwIdx;
	}
	printf("%I64d\n", res);
	return 0;
}