#include<iostream>
#include<fstream>
#include<algorithm>
#include<windows.h>
using namespace std;
ifstream f("data.in");
ofstream g("data.out");

int maximul(int a, int b, bool &c)
{
    if(a>=b)
    {
        c=0;
        return a;
    }
    else
    {
        c=1;
        return b;
    }
}

int main()
{
    int n;
    long int suma_totala=0;
    f>>n;
    int v[n];
    for(int i=0;i<n;++i)
    {f>>v[i];suma_totala+=v[i];}

    int tabla[n][n];
    int mutare[n][n];

    for(int diag=0;diag<n;++diag)
    {
        for(int i=0,j=diag; j<n; ++j,++i)
        {
            int a,b,c;
            if(i+2<=j)
            {
                a=tabla[i+2][j];
            }
            else
            a=0;

            if(i+1<=j-1)
            {
                b=tabla[i+1][j-1];
            }
            else
            b=0;

            if(i<=j-2)
            {
                c=tabla[i][j-2];
            }
            else
            c=0;

            bool alegere=0;
            tabla[i][j]=maximul(v[i]+min(a,b),v[j]+min(b,c),alegere);
            if(alegere==0)
            mutare[i][j]=i;
            else
            mutare[i][j]=j;

        }
    }

    cout<<"Bine ai venit in joc!!!!\n\nRegulile jocului sunt:\n1.Fiecare jucator trebuie sa aleaga un numar la tura sa\n";
    cout<<"2.Jucatorul poate alege la tura sa fie cel mai din stanga numar al tablei, fie cel mai din dreapta numar al tablei\n";
    cout<<"3.Jucatorul cu cel mai mare punctaj adunat la finalul jocului castiga, in caz de egalitate castiga primul jucator\n";
    cout<<"\nTastele de joc: S pentru numarul stang, D pentru numarul drept";
    cout<<"\n\nAdversarul tau incepe primul si e nerabdator sa iti masoare puterile matematice si strategice :)\n\n";
int st=0;int dr=n-1;
long int suma_posibila_jucator_2=suma_totala-tabla[0][n-1];


long int suma_jucator_1=0;
long int suma_jucator_2=0;
long int premonitie=0;
while(st<=dr)
{

    cout<<"Tabla de joc: ";

    for(int i=st;i<=dr;++i) cout<<v[i]<<" ";cout<<"\n";
    cout<<"Este randul jucatorului 1.\n";
    cout<<"Calculatorul se gandeste...\n\n";
    Sleep(5000);
        cout<<"Jucatorul 1 a ales numarul: "<<v[mutare[st][dr]]<<"\n";
        suma_jucator_1+=v[mutare[st][dr]];
        suma_totala-=v[mutare[st][dr]];
        if(mutare[st][dr]==st)
        {
            st++;
        }
        else
        --dr;

    if(st<=dr)
    {
        premonitie=((suma_jucator_1+suma_totala-tabla[st][dr])-tabla[st][dr]-suma_jucator_2);
    if(premonitie>=0)
    cout<<"\n\nJucatorul 1 e sigur ca te va invinge cu un avans de cel putin "<<premonitie<<" puncte\n";
    else
    cout<<"\n\nJucatorul 1 nu e sigur daca te poate invinge, ai mare grija cum joci\n";

        cout<<"Tabla de joc: ";
        for(int i=st;i<=dr;++i) cout<<v[i]<<" ";cout<<"\n\n";
        cout<<"Suma jucator 1: "<<suma_jucator_1<<"\n";
        cout<<"Suma jucator 2: "<<suma_jucator_2<<"\n";
        Alegerea:
        cout<<"Este randul Jucatorului 2, Algeti un numar de pe tabla: ";
        char aleg;
        cin>>aleg; cout<<"\n\n";
        if(aleg!='S'&&aleg!='D')
        {
            cout<<"Caracterul introdus este nevalid, mai incercati o data cu S sau D\n";
            goto Alegerea;
        }
        else
        if(aleg=='S')
        {
            suma_jucator_2+=v[st];
            suma_totala-=v[st];
            ++st;
        }
        else
        if(aleg=='D')
        {
            suma_jucator_2+=v[dr];
            suma_totala-=v[dr];
            --dr;
        }

    }

}
    cout<<"Jocul a luat sfarsit.\n";
    cout<<"Suma jucator 1: "<<suma_jucator_1<<"\n";
    cout<<"Suma jucator 2: "<<suma_jucator_2<<"\n";
    if(suma_jucator_1>=suma_jucator_2)
    cout<<"Jucatorul 1 a castigat";
    else
    cout<<"Jucatorul 2 a castigat";
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        if(j<i)
        g<<"0 ";
        else
        g<<tabla[i][j]<<" ";
        g<<"\n";
    }
    g<<"\n\n";
        for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        if(j<i)
        g<<"0 ";
        else
        g<<mutare[i][j]<<" ";
        g<<"\n";
    }

        return 0;

}