Cod sursă (job #143637)

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

using namespace std;

#define STANGA 0
#define DREAPTA 1

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

int gcd( long long A, long long B)
{
	long long r;
	while (B){
		r = A % B;
		A = B;
		B = r;
	}
	return A;
}

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 D, rez;
	D = gcd(b1, b2);
	if ((a1 - a2) % D != 0) {
		sol1 = (long long) -1;
		return;
	}
	rez = a1;
	while ((rez - a2) % b2)
		rez += b1;
	sol2 = b1 / D * b2;
	sol1 = rez % 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;
}