Cod sursă (job #143636)

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

#define STANGA 0
#define DREAPTA 1
#define BAZA 10

int D[50][2][2];
bool Ok[50];
long long C[200];
int A[50];
int N, T;
long long Sol;

void mul(long long A[], long long B)
{
	int i;
	long long t = 0;
    for (i = 1; i <= A[0] || t; i++, t /= BAZA)
		A[i] = (t += A[i] * B) % BAZA;
	A[0] = i - 1;
}

long long mod(long long A[], long long B)
{
	int i;
	long long t = 0;
	for (i = A[0]; i > 0; i--)
		t = (t * BAZA + A[i]) % B;
	return t;
}

inline long long rest(long long a, long long b, long long c, long long modulo)
{
	memset(C, 0, sizeof(C));
	C[0] = C[1] = 1LL;
	mul(C, a);
	mul(C, b);
	mul(C, c);
	return mod(C, modulo);
}

inline int sgn(long long a)
{
	if (a < 0LL) return -1;
	return 1;
}

int gcd( long long A, long long B, long long &X, long long &Y )
{
    if (B == 0)
    {
        X = 1LL;
        Y = 0LL;
        return A;
    }
 
    long long X0, Y0, D;
    D = gcd( B, A % B, X0, Y0 );
     
    X = Y0;
    Y = X0 - (A / B) * Y0;
	
	//sa nu sara de long long
	long long div = X / B;
	X -= div * B;
	Y += div * A;
	
    return D;
}

inline void Precalcul()
{
	int poz, dir;
	
	memset(Ok, false, sizeof(Ok));
	Ok[A[1]] = true;
	for (int i = 2; i <= N; ++i){
		//Ultima este dreapta
		poz = A[i - 1]; dir = 1;
		for (int t = 1; t <= 2 * (N - i + 1); ++t){
			do {
				poz += dir;
				if (poz == N+1) {poz = N; dir = -1;}
				if (poz == 0) { poz = 1; dir = 1; }
			}while (Ok[poz]);
			if (poz == A[i]){
				if (dir == -1) D[i][DREAPTA][STANGA] = t;
				if (dir == 1) D[i][DREAPTA][DREAPTA] = t;
			}
		}
		
		//Ultima este stanga
		poz = A[i - 1]; dir = -1;
		for (int t = 1; t <= 2 * (N - i + 1); ++t){
			do {
				poz += dir;
				if (poz == N+1) {poz = N; dir = -1;}
				if (poz == 0) { poz = 1; dir = 1; }
			}while (Ok[poz]);
			if (poz == A[i]){
				if (dir == -1) D[i][STANGA][STANGA] = t;
				if (dir == 1) D[i][STANGA][DREAPTA] = t;
			}
		}
		
		Ok[A[i]] = true;
	}
}

inline void Solve(long long a1, long long b1, long long a2, long long b2, long long &sol1, long long &sol2)
{
	long long B, C, D, alpha, beta;
	D = gcd(b1, b2, B, C);
	B = b1 / D;
	C = b2 / D;
	if ((a1 - a2) % D != 0){
		sol1 = (long long) -1;
		return;
	}
	gcd(B, C, beta, alpha);
	sol2 = B*C*D;
	sol1 = 0LL;
	sol1 += rest(abs(alpha), abs(C), abs(a1), sol2) * sgn(alpha) * sgn(C) * sgn(a1);
	sol1 += rest(abs(beta), abs(B), abs(a2), sol2) * sgn(beta) * sgn(B) * sgn(a2);
	sol1 %= sol2;
	if (sol1 < 0)
		sol1 += sol2;
}

void back(int lv, long long a1, long long b1, int dir)
{
	if (lv == N+1){
		if (a1 == 0LL) a1 += b1;
		Sol = min(Sol, a1);
		return;
	}
	
	long long a2, b2;
	long long newa1, newb1;
	
	//urmatoarea este atinsa din dreapta
	a2 = D[lv][dir][DREAPTA];
	b2 = 2 * (N - lv + 1);
	a2 %= b2;
	Solve(a1, b1, a2, b2, newa1,  newb1);
	if (newa1 != (long long) -1)
		back(lv+1, newa1, newb1, DREAPTA);
	
	//urmatoarea este atinsa din stanga
	a2 = D[lv][dir][STANGA];
	b2 = 2 * (N - lv + 1);
	a2 %= b2;
	Solve(a1, b1, a2, b2, newa1,  newb1);
	if (newa1 != (long long) -1)
		back(lv+1, newa1, newb1, STANGA);

}

int main()
{
	freopen("sport2.in","r",stdin);
	freopen("sport2.out","w",stdout);
	
	for (scanf("%d", &T); T; --T){
		scanf("%d", &N);
		for (int i = 1; i <= N; ++i)
			scanf("%d",&A[i]);
		
		Precalcul();
		Sol = 1000000000000000000LL;
		
		back(2, A[1], 2*N, DREAPTA);
		back(2, (2*N - A[1] + 1), 2*N, STANGA);
		
		printf("%lld\n", Sol);
	}
	
	return 0;
}