stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

const ll inf=1e18;

ll a[maxn];

ll dp[3][maxn];

char op[10];

int main(){

    int n;

    scanf("%d",&n);

    scanf("%lld",&a[1]);

    for(int i=2;i<=n;i++) {

        scanf("%s %lld",op,&a[i]);

        if(op[0]=='-')a[i]=-a[i];

    }

    for(int i=0;i<maxn;i++) dp[1][i]=dp[2][i]=-inf;

    ll ans=0;

    dp[0][0]=0;

    for(int i=1;i<=n;i++){

        if(a[i]>=0){

            dp[0][i]=max(max(dp[0][i-1]+a[i],dp[1][i-1]-a[i]),dp[2][i-1]+a[i]);

            dp[1][i]=dp[1][i-1]==-inf?-inf:max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]);

            dp[2][i]=dp[2][i-1]==-inf?-inf:dp[2][i-1]+a[i];

        }else {

            dp[0][i]=max(dp[0][i-1]+a[i],max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]));

            dp[1][i]=max(dp[1][i-1]-a[i],max(dp[0][i-1]+a[i],dp[2][i-1]+a[i]));

            dp[2][i]=max(dp[2][i-1]+a[i],dp[1][i-1]-a[i]);

        }

    }

//    for(int i=1;i<=n;i++) cout<<dp[0][i]<<" ";

//    cout<<endl;

//    for(int i=1;i<=n;i++) cout<<dp[1][i]<<" ";

//    cout<<endl;

    cout<<max(dp[0][n],max(dp[1][n],dp[2][n]))<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.5779455537845237x):
#include<bits/stdc++.h>

using namespace std;



typedef long long lint;

typedef long double louble;



#define so(a) ((int)((a).size()))



template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}

template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

template<typename T1,typename T2> inline T1 gmax(T1 &a,T2 b){return a=a<b?b:a;}

template<typename T1,typename T2> inline T1 gmin(T1 &a,T2 b){return a=a<b?a:b;}



const char lf = '\n';



namespace ae86

{

	const int bufl = 1 << 15;



	char buf[bufl],*s=buf,*t=buf;



	inline int fetch()

	{

		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}

		return *s++;

	}



	inline int ty()

	{

		int a=0;int b=1,c=fetch();

		while(!isdigit(c))b^=c=='-',c=fetch();

		while(isdigit(c))a=a*10+c-48,c=fetch();

		return b?a:-a;

	}



	inline int tc()

	{

		int c=fetch();

		while(c<=32 && c!=EOF)c=fetch();

		return c;

	}

}

using ae86::ty;

using ae86::tc;



const int _ = 100007;

const lint linf = 0x3f3f3f3f3f3f3f3f;



int n,dir[_]={0};lint val[_]={0};

lint f[3];



int main()

{

	ios::sync_with_stdio(0),cout.tie(nullptr);



	n=ty(),dir[1]=1,val[1]=ty();

	for(int i=2;i<=n;i++)dir[i]=tc()=='+',val[i]=ty();

	n+=2;

	

	memset(f,-64,sizeof(f));

	f[0]=0;

	for(int i=1;i<=n;i++)

	{

		lint xval=val[i]*(dir[i]?1:-1);

		f[0]+=xval,f[1]-=xval,f[2]+=xval;

		if(!dir[i])gmax(f[2],f[1]),gmax(f[1],f[0]);

		gmax(f[1],f[2]),gmax(f[0],f[1]);

	}



	cout<<max({f[0],f[1],f[2]})<<lf;

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

const ll inf=1e18;

ll a[maxn];

ll dp[3][maxn];

char op[10];

int main(){

    int n;

    scanf("%d",&n);

    scanf("%lld",&a[1]);

    for(int i=2;i<=n;i++) {

        scanf("%s %lld",op,&a[i]);

        if(op[0]=='-')a[i]=-a[i];

    }

    for(int i=0;i<maxn;i++) dp[1][i]=dp[2][i]=-inf;

    ll ans=0;

    dp[0][0]=0;

    for(int i=1;i<=n;i++){

        if(a[i]>=0){

            dp[0][i]=max(max(dp[0][i-1]+a[i],dp[1][i-1]-a[i]),dp[2][i-1]+a[i]);

            dp[1][i]=dp[1][i-1]==-inf?-inf:max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]);

            dp[2][i]=dp[2][i-1]==-inf?-inf:dp[2][i-1]+a[i];

        }else {

            dp[0][i]=max(dp[0][i-1]+a[i],max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]));

            dp[1][i]=max(dp[1][i-1]-a[i],max(dp[0][i-1]+a[i],dp[2][i-1]+a[i]));

            dp[2][i]=max(dp[2][i-1]+a[i],dp[1][i-1]-a[i]);

        }

    }

//    for(int i=1;i<=n;i++) cout<<dp[0][i]<<" ";

//    cout<<endl;

//    for(int i=1;i<=n;i++) cout<<dp[1][i]<<" ";

//    cout<<endl;

    cout<<max(dp[0][n],max(dp[1][n],dp[2][n]))<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 13.866002776955462x):
#include<cctype>

#include<cstdio>

#include<algorithm>

using i64=long long;

int fetc(){int c=getchar();while(c^'-'&&c^'+')c=getchar();return c;}

int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}

int main()

{

    int n=read();i64 ans=read(),b=-1e18,c=-1e18;

    for(int x;n^1;--n) fetc()=='-'?(x=read(),c=b+x,ans=b=std::max(ans-x,c)):(x=read(),ans+=x,c+=x,b=std::max(b-x,c));

    printf("%lld",ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

#define ll long long int

#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >

//added two more functions to set

//(1)*(set.find_by_order(k))[kth element in the sorted set] 

//(2)set.order_of_key(k)[count of elements strictly less than k]

typedef vector< int > vi;

typedef vector< ll > lvi;

typedef vector< vi > vvi;

typedef vector< lvi > lvvi;

typedef pair< int,int > ii;

typedef pair< ll,ll > lii;

#define sz(a) int((a).size())

#define pb push_back

#define all(c) (c).begin(),(c).end()

#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator

#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps

#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors

#define tc(t) int (t); cin>>(t);while((t)--)

#define ff first

#define ss second

#define mp make_pair

#define ld long double

#define ull unsigned long long int

#define mod 1000000007

string s;

lvi v;

// lvvi dp;

ll n,y,dp[200000][5];

ll recurs(int idx,int state)

{

	if(idx>=n-1) return 0LL;

	if(dp[idx][state]!=((ll)-1e15)) return dp[idx][state];

	if(s[idx]=='-')

	{

		if(state==0)

		{

			dp[idx][state]=max(recurs(idx+1,state)-v[idx],recurs(idx+1,state+1)-v[idx]);

		}

		if(state==1)

		{



			dp[idx][state]=max(recurs(idx+1,state-1)+v[idx],max(recurs(idx+1,state)+v[idx],recurs(idx+1,state+1)+v[idx]));

		}

		if(state==2)

		{



			dp[idx][state]=max(recurs(idx+1,state)-v[idx],recurs(idx+1,state-1)-v[idx]);

		}

	}

	else

	{

		if(state==0)

		{

			dp[idx][state]=recurs(idx+1,state)+v[idx];

		}

		if(state==1)

		{



			dp[idx][state]=max(recurs(idx+1,state-1)-v[idx],recurs(idx+1,state)-v[idx]);

		}

		if(state==2)

		{

			

			dp[idx][state]=max(recurs(idx+1,state)+v[idx],recurs(idx+1,state-1)+v[idx]);

		}

	}

	// cout<<idx<<" "<<state<<" "<<dp[idx][state]<<endl;

	return dp[idx][state];

}

int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);	

	cin>>n>>y;

	// dp.assign(n+2,lvi(4,-1e15));

	for(int i=0;i<(n+2);i++)

	{

		for(int j=0;j<5;j++)

		{

			dp[i][j]=-1e15;

		}

	}

	for(int i=1;i<n;i++)

	{

		char ch;

		cin>>ch;

		ll x;

		cin>>x;

		s.pb(ch);

		v.pb(x);

	}

	ll ans=recurs(0,0)+y;

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.402397696041599x):
#include<cctype>

#include<cstdio>

#include<algorithm>

using i64=long long;

int fetc(){int c=getchar();while(c^'-'&&c^'+')c=getchar();return c;}

int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}

int main()

{

    int n=read();i64 ans=read(),b=-1e18,c=-1e18;

    for(int x;n^1;--n) fetc()=='-'?(x=read(),c=b+x,ans=b=std::max(ans-x,c)):(x=read(),ans+=x,c+=x,b=std::max(b-x,c));

    printf("%lld",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long lint;

typedef long double louble;



#define so(a) ((int)((a).size()))



template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}

template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

template<typename T1,typename T2> inline T1 gmax(T1 &a,T2 b){return a=a<b?b:a;}

template<typename T1,typename T2> inline T1 gmin(T1 &a,T2 b){return a=a<b?a:b;}



const char lf = '\n';



namespace ae86

{

	const int bufl = 1 << 15;



	char buf[bufl],*s=buf,*t=buf;



	inline int fetch()

	{

		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}

		return *s++;

	}



	inline int ty()

	{

		int a=0;int b=1,c=fetch();

		while(!isdigit(c))b^=c=='-',c=fetch();

		while(isdigit(c))a=a*10+c-48,c=fetch();

		return b?a:-a;

	}



	inline int tc()

	{

		int c=fetch();

		while(c<=32 && c!=EOF)c=fetch();

		return c;

	}

}

using ae86::ty;

using ae86::tc;



const int _ = 100007;

const lint linf = 0x3f3f3f3f3f3f3f3f;



int n,dir[_]={0};lint val[_]={0};

lint f[3];



int main()

{

	ios::sync_with_stdio(0),cout.tie(nullptr);



	n=ty(),dir[1]=1,val[1]=ty();

	for(int i=2;i<=n;i++)dir[i]=tc()=='+',val[i]=ty();

	n+=2;

	

	memset(f,-64,sizeof(f));

	f[0]=0;

	for(int i=1;i<=n;i++)

	{

		lint xval=val[i]*(dir[i]?1:-1);

		f[0]+=xval,f[1]-=xval,f[2]+=xval;

		if(!dir[i])gmax(f[2],f[1]),gmax(f[1],f[0]);

		gmax(f[1],f[2]),gmax(f[0],f[1]);

	}



	cout<<max({f[0],f[1],f[2]})<<lf;

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.378702725742067x):
#include<cctype>

#include<cstdio>

#include<algorithm>

using i64=long long;

int fetc(){int c=getchar();while(c^'-'&&c^'+')c=getchar();return c;}

int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}

int main()

{

    int n=read();i64 ans=read(),b=-1e18,c=-1e18;

    for(int x;n^1;--n) fetc()=='-'?(x=read(),c=b+x,ans=b=std::max(ans-x,c)):(x=read(),ans+=x,c+=x,b=std::max(b-x,c));

    printf("%lld",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;



const int N=1e5+100;

int n,a[N];

char op[N];

LL f[N][3];



void cmax(LL &x,LL y) {x=x>y?x:y;}



int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	{

		scanf("%d",&a[i]); op[i]='!';

		if(i == n) break;

		while(op[i] != '+' && op[i] != '-') op[i]=getchar();

	}

	memset(f,0xcf,sizeof(f)); f[1][0]=a[1];

	for(int i=1;i<n;++i)

	{

		if(op[i] == '-') cmax(f[i+1][1],f[i][0]-a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][0]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][0]-a[i+1]);

		

		if(op[i] == '+') cmax(f[i+1][1],f[i][1]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][1],f[i][1]+a[i+1]);

		//if(op[i] == '-') cmax(f[i+1][1],f[i][1]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][2],f[i][1]+a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][1]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][1]-a[i+1]);

		

		if(op[i] == '+') cmax(f[i+1][2],f[i][2]+a[i+1]);

		//if(op[i] == '-') cmax(f[i+1][2],f[i][2]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][2],f[i][2]+a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][2]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][2]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][1],f[i][2]-a[i+1]);

	}

	printf("%lld",max(f[n][0],max(f[n][1],f[n][2])));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 18.039056731202514x):
#include<cctype>

#include<cstdio>

#include<algorithm>

using i64=long long;

int fetc(){int c=getchar();while(c^'-'&&c^'+')c=getchar();return c;}

int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}

int main()

{

    int n=read();i64 ans=read(),b=-1e18,c=-1e18;

    for(int x;n^1;--n) fetc()=='-'?(x=read(),c=b+x,ans=b=std::max(ans-x,c)):(x=read(),ans+=x,c+=x,b=std::max(b-x,c));

    printf("%lld",ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

const ll inf=1e18;

ll a[maxn];

ll dp[3][maxn];

char op[10];

int main(){

    int n;

    scanf("%d",&n);

    scanf("%lld",&a[1]);

    for(int i=2;i<=n;i++) {

        scanf("%s %lld",op,&a[i]);

        if(op[0]=='-')a[i]=-a[i];

    }

    for(int i=0;i<maxn;i++) dp[1][i]=dp[2][i]=-inf;

    ll ans=0;

    dp[0][0]=0;

    for(int i=1;i<=n;i++){

        if(a[i]>=0){

            dp[0][i]=max(max(dp[0][i-1]+a[i],dp[1][i-1]-a[i]),dp[2][i-1]+a[i]);

            dp[1][i]=dp[1][i-1]==-inf?-inf:max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]);

            dp[2][i]=dp[2][i-1]==-inf?-inf:dp[2][i-1]+a[i];

        }else {

            dp[0][i]=max(dp[0][i-1]+a[i],max(dp[1][i-1]-a[i],dp[2][i-1]+a[i]));

            dp[1][i]=max(dp[1][i-1]-a[i],max(dp[0][i-1]+a[i],dp[2][i-1]+a[i]));

            dp[2][i]=max(dp[2][i-1]+a[i],dp[1][i-1]-a[i]);

        }

    }

//    for(int i=1;i<=n;i++) cout<<dp[0][i]<<" ";

//    cout<<endl;

//    for(int i=1;i<=n;i++) cout<<dp[1][i]<<" ";

//    cout<<endl;

    cout<<max(dp[0][n],max(dp[1][n],dp[2][n]))<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.6457709066956943x):
#include<bits/stdc++.h>

#define maxn 100005

#define LL long long

using namespace std;

char cb[1<<20],*cs,*ct;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &a){

	char c;bool f=0;while(!isdigit(c=getc())) c=='-'&&(f=1);

	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); f&&(a=-a);

}

int n;

LL F[maxn],G[maxn],a[maxn];

int main()

{

	read(n);

	for(int i=1;i<=n;i++){

		read(a[i]);

		if(i>1&&a[i-1]>0&&a[i]>0) a[i-1]+=a[i],i--,n--;

	}

	for(int i=1;i<=n;i++) F[i]=F[i-1]+a[i],G[i]=G[i-1]+abs(a[i]);

	LL ans=F[n];

	for(int i=2;i<n;i++) if(a[i]<0) ans=max(ans,F[i]-a[i+1]+G[n]-G[i+1]);

	printf("%lld\n",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;



const int N=1e5+100;

int n,a[N];

char op[N];

LL f[N][3];



void cmax(LL &x,LL y) {x=x>y?x:y;}



int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	{

		scanf("%d",&a[i]); op[i]='!';

		if(i == n) break;

		while(op[i] != '+' && op[i] != '-') op[i]=getchar();

	}

	memset(f,0xcf,sizeof(f)); f[1][0]=a[1];

	for(int i=1;i<n;++i)

	{

		if(op[i] == '-') cmax(f[i+1][1],f[i][0]-a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][0]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][0]-a[i+1]);

		

		if(op[i] == '+') cmax(f[i+1][1],f[i][1]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][1],f[i][1]+a[i+1]);

		//if(op[i] == '-') cmax(f[i+1][1],f[i][1]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][2],f[i][1]+a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][1]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][1]-a[i+1]);

		

		if(op[i] == '+') cmax(f[i+1][2],f[i][2]+a[i+1]);

		//if(op[i] == '-') cmax(f[i+1][2],f[i][2]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][2],f[i][2]+a[i+1]);

		if(op[i] == '+') cmax(f[i+1][0],f[i][2]+a[i+1]);

		if(op[i] == '-') cmax(f[i+1][0],f[i][2]-a[i+1]);

		if(op[i] == '-') cmax(f[i+1][1],f[i][2]-a[i+1]);

	}

	printf("%lld",max(f[n][0],max(f[n][1],f[n][2])));

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.442031005717723x):
#include<bits/stdc++.h>

#define maxn 100005

#define LL long long

using namespace std;

char cb[1<<20],*cs,*ct;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &a){

	char c;bool f=0;while(!isdigit(c=getc())) c=='-'&&(f=1);

	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); f&&(a=-a);

}

int n;

LL F[maxn],G[maxn],a[maxn];

int main()

{

	read(n);

	for(int i=1;i<=n;i++){

		read(a[i]);

		if(i>1&&a[i-1]>0&&a[i]>0) a[i-1]+=a[i],i--,n--;

	}

	for(int i=1;i<=n;i++) F[i]=F[i-1]+a[i],G[i]=G[i-1]+abs(a[i]);

	LL ans=F[n];

	for(int i=2;i<n;i++) if(a[i]<0) ans=max(ans,F[i]-a[i+1]+G[n]-G[i+1]);

	printf("%lld\n",ans);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef long long STATES;



int main( void )

{

	int n;

	while ( cin >> n && n )

	{

		STATES goal_state = 0;

		for ( int i = 0; i < n; i++ ) goal_state |= 1LL << i;



		vector <STATES> free_days( 30+1, 0 );

		for ( int i = 0; i < n; i++ )

		{

			int k; cin >> k;

			for ( int j = 0; j < k; j++ )

			{

				int free_day; cin >> free_day;

				free_days[free_day] |= 1LL << i;

			}

		}



		int answer = -1;

		vector <STATES> dp( n, 0 );

		for ( int i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( int i = 1; answer == -1 && i <= 30; i++ )

		{

			STATES next = 0;

			for ( int j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( int j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		cout << answer << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.242918747336921x):
#include <cstdio>

#include <cstring>

using namespace std;



typedef long long STATES;



int main( void )

{

	STATES free_days[31], dp[51];

	STATES goal_state, next;

	register int i, j;

	int n, answer, free_day, k;



	while ( scanf( "%d", &n ) == 1 && n )

	{

		memset( free_days, 0, sizeof(STATES)*31 );

		memset( dp, 0, sizeof(STATES)*n );



		goal_state = 0;

		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;



		for ( i = 0; i < n; i++ )

		{

			scanf( "%d", &k );

			for ( j = 0; j < k; j++ )

			{

				scanf( "%d", &free_day );

				free_days[free_day] |= 1LL << i;

			}

		}



		answer = -1;

		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( i = 1; answer == -1 && i <= 30; i++ )

		{

			next = 0;

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		printf( "%d\n", answer );

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef long long STATES;



int main( void )

{

	register int i, j;

	int n;

	while ( cin >> n && n )

	{

		STATES goal_state = 0;

		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;



		vector <STATES> free_days( 30+1, 0 );

		for ( i = 0; i < n; i++ )

		{

			int k; cin >> k;

			for ( j = 0; j < k; j++ )

			{

				int free_day; cin >> free_day;

				free_days[free_day] |= 1LL << i;

			}

		}



		int answer = -1;

		vector <STATES> dp( n, 0 );

		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( i = 1; answer == -1 && i <= 30; i++ )

		{

			STATES next = 0;

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		cout << answer << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.242918747336921x):
#include <cstdio>

#include <cstring>

using namespace std;



typedef long long STATES;



int main( void )

{

	STATES free_days[31], dp[51];

	STATES goal_state, next;

	register int i, j;

	int n, answer, free_day, k;



	while ( scanf( "%d", &n ) == 1 && n )

	{

		memset( free_days, 0, sizeof(STATES)*31 );

		memset( dp, 0, sizeof(STATES)*n );



		goal_state = 0;

		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;



		for ( i = 0; i < n; i++ )

		{

			scanf( "%d", &k );

			for ( j = 0; j < k; j++ )

			{

				scanf( "%d", &free_day );

				free_days[free_day] |= 1LL << i;

			}

		}



		answer = -1;

		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( i = 1; answer == -1 && i <= 30; i++ )

		{

			next = 0;

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		printf( "%d\n", answer );

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef long long STATES;



int main( void )

{

	register int i, j;

	int n;

	while ( cin >> n && n )

	{

		STATES goal_state = 0;

		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;



		vector <STATES> free_days( 30+1, 0 );

		for ( i = 0; i < n; i++ )

		{

			int k; cin >> k;

			for ( j = 0; j < k; j++ )

			{

				int free_day; cin >> free_day;

				free_days[free_day] |= 1LL << i;

			}

		}



		int answer = -1;

		vector <STATES> dp( n, 0 );

		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( i = 1; answer == -1 && i <= 30; i++ )

		{

			register STATES next = 0;

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		cout << answer << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.242891876087693x):
#include <cstdio>

#include <cstring>

using namespace std;



typedef long long STATES;



int main( void )

{

	STATES free_days[31], dp[51];

	STATES goal_state, next;

	register int i, j;

	int n, answer, free_day, k;



	while ( scanf( "%d", &n ) == 1 && n )

	{

		memset( free_days, 0, sizeof(STATES)*31 );

		memset( dp, 0, sizeof(STATES)*n );



		goal_state = 0;

		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;



		for ( i = 0; i < n; i++ )

		{

			scanf( "%d", &k );

			for ( j = 0; j < k; j++ )

			{

				scanf( "%d", &free_day );

				free_days[free_day] |= 1LL << i;

			}

		}



		answer = -1;

		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;

		for ( i = 1; answer == -1 && i <= 30; i++ )

		{

			next = 0;

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) next |= dp[j];

			for ( j = 0; j < n; j++ ) if ( free_days[i] & ( 1LL << j ) ) dp[j] |= next;

			if ( next == goal_state ) answer = i;

		}



		printf( "%d\n", answer );

	}



	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



const int MAX = 500010;

int n;

int a[MAX];

int tmp[MAX];

int com;



void merge(int A[], int lo, int mi, int hi) {

    int p1 = lo;

    int p2 = mi;

    int p3 = lo;

    while (p1 < mi && p2 < hi) {

        com++;

        if (A[p1] <= A[p2]) {

            tmp[p3++] = A[p1++];

        } else {

            tmp[p3++] = A[p2++];

        }

    }

    while (p1 < mi) {tmp[p3++] = A[p1++]; com++;}

    while (p2 < hi) {tmp[p3++] = A[p2++]; com++;}

    for (int i = lo; i < hi; i++) {

        A[i] = tmp[i];

    }

}



void mergeSort(int A[], int lo, int hi) {

    if (lo + 1 < hi) {

        int mi = (lo + hi) >> 1;

        mergeSort(A, lo, mi);

        mergeSort(A, mi, hi);

        merge(A, lo, mi, hi);

    }

}





int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);

    com = 0;

    for (int i = 0; i < n; i++) {

        scanf("%d", &a[i]);

    }

    mergeSort(a, 0, n);

    for (int i = 0; i < n; i++) {

        if (i > 0) printf(" ");

        printf("%d", a[i]);

    }

    printf("\n");

    printf("%d\n", com);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.08722563448933x):
#include<stdio.h>

int a[6000000];

int n;

int sum=0;

void hebing(int a[],int q,int p,int l,int d){

  int i,j,k,b[n];

  i=q;

  j=l;

  k=q;

  while(i<=p&&j<=d){

    if(a[i]<a[j]){b[k++]=a[i++];sum++;}

    else {b[k++]=a[j++];sum++;}

  }

  while (i<=p){b[k++]=a[i++];sum++;}

  while (j<=d){b[k++]=a[j++];sum++;}

  for(int i=q;i<=d;i++){

    a[i]=b[i];

  }

}

void paixu(int a[],int m,int n){

    if(n>m){

int x=(n+m)/2;

paixu(a,m,x);

paixu(a,x+1,n);

hebing(a,m,x,x+1,n);

}

}

int main(){

scanf("%d",&n);

for(int i=0;i<n;i++){

    scanf("%d",&a[i]);

}

paixu(a,0,n-1);

printf("%d",a[0]);

for(int i=1;i<n;i++){

    printf(" %d",a[i]);

}

printf("\n%d\n",sum);

return 0;

}