stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

using ll = long long;



const int MAX_N = 2e5;



// 辺を保持

// いろんな保持の仕方がある

vector<int> ecasdqina[MAX_N];

/*

ほかにも

bool graph[MAX_N][MAX_N];

graph[a][b] := aとbの間に辺があるか?

といった定義にもできるけど,今回はMAX_Nが大きいのでMLE

(静的なのでコンパイル時に落ちる, これが割と気づきにくい)



vector< vector<int> > graph(MAX_N, vector<int>(MAX_N, 0));

と動的配列で書いても同様に実行時にMLE!!

動的配列を使うように心がけ解くと, MLEに気付きやすいかもという利点はある



さらに発展的な話題で,辺に重みがあったりする場合もこの二通りの

表現方法があるってことは頭の片隅にでも!(わからなかったらまた聞いてね!)

*/



// 僕はよく答えが二通りの問題とかは関数にしてるけど

// いいかどうかは人それぞれなので

int solve(int n) {

  vector<int> flag(n, 0);

  // 頂点1から行ける辺にマークを付ける(フラグを建てる)

  // ちなみにvector<bool>は特殊だからvector<int>を代わりに使う

  // 詳しくは調べてね

  // もちろんvector<bool>でもbool[MAX_N]でもいいよ

  

  // 拡張for (というのはJava的で, range-based for loopっていうのかな)

  // O(M) // なぜなら, 辺の数はたかだかM個だから, ecasdqina.size()はM程度

  for(int j : ecasdqina[0]) {

    // 頂点jに頂点1から行けるので印をつける

    flag[j] = 1; // trueでもよし

  }



  // 0-indexedなので頂点Nは[n-1]だよ

  // 上記と同様にO(M)

  for(int j : ecasdqina[n - 1]) {

    // 印がついてれば 1 - j - N というつながりがある！

    if(flag[j]) return 1; // true を返してもいい

  }

  // さてここまで来たらそんな辺はなかった

  return 0;

}



int main() {

  ios::sync_with_stdio(false), cin.tie(0);

  int n, m; cin >> n >> m;

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

    int a, b; cin >> a >> b;

    a--; b--;

    // push_back は emplace_back

    // 詳しくは調べてね

    ecasdqina[a].emplace_back(b);

    // 双方向につなぐことに注意してね

    ecasdqina[b].emplace_back(a);

  }

  // 例えばecasdqina[0]は配列になっているけど, 

  // それらは頂点1から行ける場所



  cout << (solve(n) ? "POSSIBLE" : "IMPOSSIBLE") << endl;

}




// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

using ll = long long;



int main() {

  ios::sync_with_stdio(false), cin.tie(0);

  int n, m; cin >> n >> m;

  vector<int> ecasdqina(n);

  while(m--) {

    int a, b; cin >> a >> b;

    if(a == 1 || a == n) ecasdqina[b-1]++;

    if(b == 1 || b == n) ecasdqina[a-1]++;

    if(ecasdqina[a-1] >=2 || ecasdqina[b-1] >= 2) {

      cout << "POSSIBLE" << endl;

      return 0;

    }

  }

  cout << "IMPOSSIBLE" << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main(void)

{

    int N,M;

    cin >> N >> M;

    int a;

    int b;

    bool s[200010] = {false};

    bool t[200010] = {false};



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

        cin >> a >> b;

        if( a == 1 ) s[b] = true;

        if( b == N ) t[a] = true;

    }



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

        if( s[i] == true && t[i] == true ){

            printf("POSSIBLE");

            return 0;

        }

    }

    printf("IMPOSSIBLE");

    

    return 0;

}

// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

using namespace std;

#define ll long long int

#define rep(i,n) for( int i = 0; i < n; i++ )

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



bool S[200010];

bool G[200010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N, M;

    cin >> N >> M;

    rep(i, M) {

        int a, b;

        cin >> a >> b;

        a--; b--;

        if(a == 0) S[b] = true;

        if(b == N - 1) G[a] = true;

    }

    rep(i, N) {

        if(S[i] && G[i]) {

            cout << "POSSIBLE" << endl;

            return 0;

        }

    }

    cout << "IMPOSSIBLE" << endl;



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define MAX_N 200000

#define MAX_M 200000



int N, M;

vector<int> ab[MAX_N + 1];



int main()

{

	cin >> N >> M;

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

		int a, b;

		cin >> a >> b;

		ab[a].push_back( b );

	}



	int ans = 0;

	for( int i = 0; i < ab[1].size(); i++ ) {

		int idx = ab[1][i];

		for( int j = 0; j < ab[idx].size(); j++ ) {

			if( ab[idx][j] == N ) {

				ans = 1;

				break;

			}

		}

	}



	if( ans == 1 ) {

		cout << "POSSIBLE" << endl;

	}

	else {

		cout << "IMPOSSIBLE" << endl;

	}



	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main()

{

	int N, M;

	cin >> N >> M;

	vector<vector<int>> g( N );

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

		int a, b;

		cin >> a >> b;

		a--;

		b--;

		g[a].push_back( b );

		g[b].push_back( a );

	}



	vector<int> v( N );

	typedef pair<int, int> P;

	queue<P> que;

	que.push( P( 0, 0 ) );

	v[0] = 1;

	string ans = "IMPOSSIBLE";

	while( !que.empty() ) {

		int d, x;

		tie( d, x ) = que.front();

		que.pop();

		if( x == N - 1 ) {

			ans = "POSSIBLE";

			break;

		}

		if( d >= 2 ) continue;

		for( int e : g[x] ) {

			if( v[e] ) continue;

			que.push( P( d + 1, e ) );

			v[e] = 1;

		}

	}



	cout << ans << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int a[100010];

int main ()

{

	int n,i;

	scanf("%d",&n);

	for(i=1;i<=n;++i) scanf("%d",&a[i]);

	sort(a+1,a+1+n);

	int stand1=a[n]/2,stand2;

	if(a[n]%2==0) stand2=stand1;

	else stand2=stand1+1;

	int p=1,minn=min(abs(stand1-a[1]),abs(stand2-a[1]));

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

	{

		int t=min(abs(stand1-a[i]),abs(stand2-a[i]));

		if(t<minn)

		{

			p=i;

			minn=t;

		}

	}

	printf("%d %d\n",a[n],a[p]);

} 

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define WR "txt"



void Open() { freopen(WR".in", "r", stdin); freopen(WR".out", "w", stdout); }

void Close() { fclose(stdin); fclose(stdout); }

using namespace std;

int Read()  {

	int val = 0, opt = 1; char ch;

	while (!isdigit(ch = getchar() )) if (ch == '-') opt = -1;

	while (isdigit( ch )) (val *= 10) += ch - '0', ch= getchar();

	return val * opt;

}



int a[100100], n, p;



void work()  {

	n = Read();

	for (int i = 1;i <= n; i++)	a[i] = Read();

	sort(a + 1, a + 1 + n);

	p = a[1];

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

		if (abs(a[i] - a[n] / 2.) < abs(p - a[n] / 2.)) p = a[i];

	printf("%d %d", a[n], p);

}



int main(void)  {

	//Open();

	work();

	//Close();

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<cmath>

bool cmp(int a, int b){

	return a > b;

}

using namespace std;

int main(){

	int n;

	long long mid = 0;

	long long a[100010];

	cin >> n;

	for(int i = 0; i < n; i ++)cin >> a[i];

	sort(a, a + n, cmp);

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

		if(abs(a[0] - 2 * a[i]) <= abs(a[0] - 2 * mid))mid = a[i];

		else break;

	}

	cout << a[0] << ' ' << mid; 

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstring>

#define ll long long

#define maxn 0x3f3f3f3f

using namespace std;

int a[100010];

int b[100010];

int main()

{

	int n;

	cin>>n;

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

	{

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

	}

	sort(a+1,a+n+1);

	double k=a[n]*1.0;

	k = k/2.0;

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

	{

		b[i]=(a[i]-k<0?-(a[i]-k):a[i]-k);

	}

	int minn=0x3f3f3f3f,sum=0;

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

	{

		if(minn>b[i]){

			minn = b[i];

			sum = i;

		}

		

	}

	cout<<a[n]<<" "<<a[sum]<<endl;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//D

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int a[100010];

bool cmp (int p,int b)

{

	return p>b;

}

int main()

{

	int n;

	int x,y1,y2,y,mid;

	scanf("%d",&n);

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

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

	sort(a+1,a+1+n);//升序

	x=a[n];

	mid=x/2;

	y1=lower_bound(a+1,a+1+n,mid)-a;

	if(y1==n)

		y1=a[y1-1];

	else y1=a[y1];

	if(y1!=mid)

	{

		sort(a+1,a+1+n,cmp);//降序 

		y2=lower_bound(a+1,a+1+n,mid,greater<int>())-a;

		y2=a[y2];

	if((y1-1-mid)<(mid-y2))

		y=y1;

	else 

		y=y2;

	}

	if(y1==mid)

		y=y1;

	cout<<x<<" "<<y<<endl;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

int f[100005];

int  maxx=-1,n,temp;

int main()

{

    cin>>n;

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

    {

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

    	if(f[i]>maxx)

		{

			maxx=f[i];

		

		}

	}

	if(n==2)

	{

		cout<<max(f[1],f[2])<<" "<<min(f[1],f[2])<<endl;

		return 0;

	}

		double mm=maxx/2.0;

		double minn=maxx;

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

	    {

	    	if(abs(f[i]-mm)<minn)

	    	{

	    	//	cout<<f[i]<<" "<<minn<<endl;

				minn=abs(f[i]-mm);

	    		temp=f[i];

			}

		}

		cout<<maxx<<" "<<temp;

		    return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

double b[N];

int main()

{

	int n, maxa = -1;

	int ans;

	scanf("%d",&n);

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

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

	sort(a + 1, a + 1 + n);

	double mid = 1.0 * a[n] / 2, minb = 1000000009.0;

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

	{

		if (fabs(mid - (1.0 * a[n] - 1.0 * a[i])) < minb)

		{

			ans = a[i];

			minb = fabs(mid - (1.0 * a[n] - 1.0 * a[i]));

		}

	}

	printf("%d %d\n", a[n], ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<utility>

#include<math.h>

#include<set>

#include<map>

#include<string.h>

#include<stack>

#define n 200000

#define loop(i, a, b) for(int i = a; i<=b; i++)

using namespace std;

typedef pair<int, int> P;

typedef long long lli;

typedef double llf;

struct edge{

	int from, to, weight;

	bool operator < (const edge& thing) const

	{

		return thing.weight < weight;

	}

};

vector<edge> V[n + 50];

bool visit[n + 50];

int arr[n + 50], a, b, c, d, e;

string str1, str2;

void addedge(int a, int b, int c)

{

	edge temp;

	temp.from = a;

	temp.to = b;

	temp.weight = c;

	V[a].push_back(temp);

}





//////////////////////////////////////////





void solve()

{

	cin >> a;

	loop(i, 0, a - 1)

		cin >> arr[i];

	int max = 0;

	loop(i, 1, a - 1)

		if(arr[i] > arr[max]) max = i;

	int ans2 = -1;

	int temp = arr[max] / 2;

	loop(i, 0, a - 1)

	{

		if(i == max) continue;

		else if(ans2 == -1) ans2 = i;

		else

		{

			int t1 = abs(temp - arr[ans2]), t2 = abs(temp - arr[i]);

			if(t2 < t1) ans2 = i;

		}

	}

	cout << arr[max] << ' ' << arr[ans2] << '\n';

}

int main()

{

	int times = 1;

//	cin << times;

	loop(i, 1, times)

	{

		solve();

		printf("\n");

	}

	return 0;

}






// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int a; cin >> a;

	int arr[a + 50], n = 0, m = 0, now = 999999999;

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

	{

		cin >> arr[i];

		n = max(n, arr[i]);

	}

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

	{

		if(arr[i] == n) continue;

		int tmp = abs(arr[i] - n / 2);

		if(m % 2) tmp = min(abs(arr[i] - n / 2), abs(arr[i] - (n + 1) / 2));

		if(tmp < now)

		{

			now = tmp;

			m = arr[i];

		}

	}

	cout << n << ' ' << m << '\n';

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int n, a[100005];

double m;

int main() {

	int i, k;

	scanf("%d", &n);

	for(i=0; i<n; i++) scanf("%d", &a[i]);

	sort(a, a+n);

	m = a[n-1] / 2.0;

	k = lower_bound(a, a+n, m) - a;

	if(m-a[k-1]<=a[k]-m) printf("%d %d", a[n-1], a[k-1]);

	else printf("%d %d", a[n-1], a[k]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;

int n, a[100005];

int main() {

	int i;

	scanf("%d", &n);

	for(i=0; i<n; i++) scanf("%d", &a[i]);

	sort(a, a+n);

	for(i=0; 2*a[i]<a[n-1]; i++);

	printf("%d %d", a[n-1], a[n-1]-2*a[i-1] <= 2*a[i]-a[n-1] ? a[i-1] : a[i]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <map>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)



int main() {

	ll n; cin >> n;

	ll a[100000] = {};

	ll maxV = 0;

	rep(i, 0, n) {

		cin >> a[i];

		maxV = max(maxV, a[i]);

	}



	ll index = 0;

	ll minV = 1e20;

	rep(i, 0, n) {

		if (a[i] != maxV) {

			if (minV > abs(maxV - 2 * a[i])) {

				minV = abs(maxV - 2 * a[i]);

				index = i;

			}

		}

	}

	cout << maxV << " " << a[index] << endl;



	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#include <map>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)



ll a[100001];

int main()

{

	ll n; cin >> n;

	ll maxA = 0;

	rep(i, 0, n) {

		cin >> a[i];

		if (maxA <= a[i]) {

			maxA = a[i];

		}

	}



	ll minV = 1e20;

	ll minIndex = 0;

	rep(i, 0, n) {

		if (a[i] != maxA) {

			if (minV >= abs(2 * a[i] - maxA)) {

				minV = abs(2 * a[i] - maxA);

				minIndex = i;

			}

		}

	}

	cout << maxA << " " << a[minIndex] << endl;



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <algorithm>

#include <vector>



using namespace std;



typedef long long lint;



int main()

{

	int n;

	static int a[100000];

	static int s[200000], t[200000], next[2][200000];

	static pair<int, int> p[400000];

	static vector<int> bucket[300000];

	

	lint sum = 0;

	

	scanf("%d", &n);

	

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

		scanf("%d", a + i);

		sum += a[i];

	}

	

	lint left = 0, right = sum / 3;

	

	while (left != right){

		lint mid = (left + right + 1) >> 1;

		lint sum2 = 0;

		int head = 0, tail = 0;

		bool ng = false;

		

		for (; head < n; head++){

			while (sum2 < mid){

				sum2 += a[tail++];

				if (tail >= n) tail -= n;

			}

			int i = head;

			s[i] = head, t[i] = tail;

			if (s[i] == t[i]) ng = true;

			if (t[i] < s[i]) t[i] += n;

			s[n + i] = s[i] + n, t[n + i] = t[i] + n;

			sum2 -= a[head];

		}

		if (ng){

			right = mid - 1;

			continue;

		}

		for (int i = 0; i < n * 3; i++) bucket[i].clear();

		

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

			bucket[t[i]].push_back(i);

			bucket[s[i]].push_back(n * 2 + i);

		}

		int ctr = 0;

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

			for (int j = 0; j < bucket[i].size(); j++){

				p[ctr++] = make_pair(i, bucket[i][j]);

			}

		}

		

		int last = -1;

		for (int i = n * 4 - 1; i >= 0; i--){

			int id = p[i].second;

			if (id < n * 2) next[0][id] = last;

			else {

				id -= n * 2;

				if (last < 0 || t[last] > t[id]) last = id;

			}

		}

		

		for (int k = 0; k + 1 < 2; k++){

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

				if (next[k][i] < 0) next[k + 1][i] = -1;

				else next[k + 1][i] = next[k][next[k][i]];

			}

		}

		

		int res = 0;

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

			int tmp = 0, j = i;

			for (int k = 1; k >= 0; k--){

				int j2 = next[k][j];

				if (j2 >= 0 && t[j2] <= s[i] + n){

					j = j2;

					tmp |= 1 << k;

				}

			}

			if (res >= 3) break;

			res = max(res, tmp + 1);

		}

		if (res >= 3) left = mid;

		else right = mid - 1;

	}

	

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

	

	return (0);

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>



using namespace std;



typedef long long lint;



int main()

{

	int n;

	int a[100000];

	int t[300000];

	

	lint sum = 0;

	

	scanf("%d", &n);

	

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

		scanf("%d", a + i);

		sum += a[i];

	}

	

	lint left = 0, right = sum / 3;

	

	while (left != right){

		lint mid = (left + right + 1) >> 1;

		lint sum2 = 0;

		

		int head = 0, tail = 0;

		for (; head < n; head++){

			while (sum2 < mid){

				sum2 += a[tail % n];

				tail++;

			}

			t[head] = tail - 1;

			t[head + n] = tail - 1 + n;

			t[head + n + n] = tail - 1 + n + n;

			sum2 -= a[head];

		}

		

		bool ok = false;

		for (head = 0; head < n; head++){

			if (t[t[t[head] + 1] + 1] - head + 1 <= n){

				ok = true;

				break;

			}

		}

		

		if (ok) left = mid;

		else right = mid - 1;

	}

	

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

	

	return (0);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<string>

#include<cmath>



using namespace std;



int main(){

    int n, t, maxn = 0;

    cin >> n >> t;

    int a[n], b[n];

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

        cin >> a[i];

    }

    b[n-1] = a[n-1];

    for(int i = n-2; i >= 0; i--){

        b[i] = max(b[i+1], a[i]);

    }

    int cnt = 0;

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

        if(maxn < b[i]-a[i]){

            maxn = b[i] - a[i];

            cnt = 1;

        }else if(maxn == b[i] - a[i]){

            cnt ++;

        }

    }

    cout << cnt << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

int n,t,a;

int main(){

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

	scanf("%d%d",&n,&t);

	scanf("%d",&a);

	int min1=a,ans=0,maxc=0;

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

		scanf("%d",&a);

		if(a-min1==maxc) ans++;

		if(a-min1>maxc) maxc=a-min1,ans=1;

		if(min1>a) min1=a;

	}

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



vector < int > v;



int main(){

    int a_i, b_i, n, temp, t, mini, maxiD, cont = 0;



    cin>>n>>t;



    v.resize( n );



    for( a_i=0; a_i<n; a_i++ ) cin>>v[a_i];



    mini = v[0]; maxiD = 0;



    for( a_i=0; a_i<n; a_i++ ){

        mini = min( v[a_i], mini );

        maxiD = max( maxiD, v[a_i]-mini );

    }



    mini = v[0];

    for( a_i=0; a_i<n; a_i++ ){

        mini = min( v[a_i], mini );

        if( v[a_i]-mini == maxiD ) cont++;

    }



        cout<<cont<<endl;



}


// Optimized solution to the same problem (faster):
#include <cstdio>

int n,t,a;

int main(){

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

	scanf("%d%d",&n,&t);

	scanf("%d",&a);

	int min1=a,ans=0,maxc=0;

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

		scanf("%d",&a);

		if(a-min1==maxc) ans++;

		if(a-min1>maxc) maxc=a-min1,ans=1;

		if(min1>a) min1=a;

	}

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int a, b; cin >> a >> b;

	int arr[a + 50], mi[a + 50];

	fill(mi, mi + a, 2147483647);

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

	{

		cin >> arr[i];

		if(i) mi[i] = mi[i - 1];

		mi[i] = min(mi[i], arr[i]);

	}

	int cnt = 1, now = 0;

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

	{

//		cout << arr[i] << ' ' << mi[i] << '\n';

		if(arr[i] - mi[i - 1] > now)

		{

			cnt = 1;

			now = arr[i] - mi[i - 1];

		}

		else if(arr[i] - mi[i - 1] == now) cnt ++;

	}

	cout << cnt << '\n';

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int min(int a,int b)

{

	if(a<b)

		return a;

	else

		return b;

}

int main()

{

	int n,t,i,pos,old,ans=0;

	scanf("%d%d",&n,&t);

	int min_pic=0x3f3f3f3f,max_value=0;

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

	{

		scanf("%d",&pos);

		if(i==0)

		{

			min_pic=pos;

			old=pos;

		}

		else

		{

			if(pos>old)

			{

				if(pos-min_pic>max_value)

				{

					max_value=pos-min_pic;

					ans=1;

				}

				else if(pos-min_pic==max_value)

					ans++;

			}

			else

				old=pos;

			if(min_pic>pos)

				min_pic=pos;

		}

	}

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define mp make_pair

#define ll long long

#define x first

#define y second

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



const int MAX = 500005;

const int mod = 998244353;

int a[100005];

int main()

{

	ios_base::sync_with_stdio(0);

	int n , t;

	cin >> n >> t;

	map<int, int> res;

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

		cin >> a[i];

	int ans = 0;

	for(int i = n - 1; i >= 0; i--)

	{

		ans = max(ans , a[i]);

		res[ans - a[i]]++;

	}

	cout << (--res.end())->y;

			

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int min(int a,int b)

{

	if(a<b)

		return a;

	else

		return b;

}

int main()

{

	int n,t,i,pos,old,ans=0;

	scanf("%d%d",&n,&t);

	int min_pic=0x3f3f3f3f,max_value=0;

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

	{

		scanf("%d",&pos);

		if(i==0)

		{

			min_pic=pos;

			old=pos;

		}

		else

		{

			if(pos>old)

			{

				if(pos-min_pic>max_value)

				{

					max_value=pos-min_pic;

					ans=1;

				}

				else if(pos-min_pic==max_value)

					ans++;

			}

			else

				old=pos;

			if(min_pic>pos)

				min_pic=pos;

		}

	}

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

}

// Fastest known solution for this problem: