Cod sursă (job #294404)

#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;
}