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

using namespace std;

#define MAX 100000



int n,k;

long long T[MAX];



int check(long long P){

    int i=0;

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

        long long s=0;

        while(s+T[i]<=P){

            s+=T[i];

            i++;

            if(i==n)return n;

        }

    }

    return i;

} 



int solve(){

    long long left = 0;

    long long right = 100000*10000;

    long long mid;

    while(right-left>1){

        mid=(left+right)/2;

        int v=check(mid);

        if(v>=n)right=mid;

        else left=mid;

    }

    return right;

}



int main() {

    cin>>n>>k;

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

    long long ans=solve();

    cout<<ans<<endl;

    return 0;

}

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

const int t=100005;

int a[t];

int n,m;

bool Find(int x)

{

    int sum=0;

    int fuck=0;

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

    {

        sum+=a[i];

        if(sum>x)

        {

            ++fuck;

            sum=a[i];

            if(sum>x)

            {

                return 0;

            }

        }

    }

    return fuck<m;

}

int main()

{

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

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

    {

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

    }

    int l=1,r=t*10000;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(Find(mid))

        {

            r=mid-1;

        }

        else

            l=mid+1;

    }

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

}

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

#include<vector>

#include<string>



#define MAX 100000

typedef long long llong;



using namespace std;



int n, k;

vector<llong> T(MAX);



int check(llong P) {

	int i = 0;

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

		llong s = 0;

		while (s + T[i] <= P) {

			s += T[i];

			++i;

			if (i == n)

				return n;

		}

	}

	return i;

}



llong solve() {

	llong left = 0, right = MAX*10000;

	llong mid;

	while (right-left>1) {

		mid = (left + right) / 2;

		int v = check(mid);

		if (v >= n) right = mid;

		else

			left = mid;

	}

	return right;

}



int main() {

	cin >> n >> k;

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

		cin >> T[i];

	}

	llong res = solve();

	cout << res << endl;

	return 0;

}




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



using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const int maxn = 100000;

int n, k;

ll a[maxn];



int check(ll mid) {

    int t = 0;

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

        int s = 0;

        while (s + a[t] <= mid) {

            s += a[t++];

            if (t == n)

                return n;

        }

    }

    return t;

}



int solve() {

    ll l = 0;

    ll r=10000000000;

//    ll r = 20;

    while (l < r - 1) {

        ll mid = (l + r) / 2;

        ll v = check(mid);

        if (v == n) {

            r = mid;

        } else {

            l = mid;

        }

    }

    return r;

}



int main() {

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

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

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

    }

    ll ans = solve();

    cout << ans << endl;

    return 0;

}


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

#include<algorithm>

#include<cstdio>



using namespace std;



#define N 100000



int A[N];

int n,k;



int K_search(int P){

    int TR[N]={0};

    int tr = 0;

    int count = 0;

    

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

        if (TR[tr]+A[i]<=P) {

            TR[tr] += A[i];

            count++;

        }else if(tr+1<k && A[i]<=P){

            tr++;

            TR[tr] += A[i];

            count++;

        }else{

            break;

        }

    }

    return count;

}



int solve(){

    int Right=0,Left=0;

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

        Right += A[i];

    }

    int mid;

    

    

    while ( Right-Left > 1 ) {

        mid = (Right+Left)/2;

        

        int v = K_search(mid);

        if (v >= n) {

            Right = mid;

        }else{

            Left = mid;

        }

    }

    return Right;

}





int main(){

    cin >> n >> k;

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

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

    }

    

    cout << solve() << endl;

    

    return 0;

}

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

#include<cstdio>

#include<string>

#include<algorithm>

#include<cstring>

using namespace std;



int W[100001];

int n,k;



int rec(int p){

    int maxw = 0;

    int numtr = 1;

    int tr = p;

    int i;

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

        if (tr - W[i] >= 0) {

            tr -= W[i];

        }else if(numtr < k){

            tr = p;

            i--;

            numtr++;

        }else{

            break;

        }

    }

    return i;

}



int binary(int left, int right){

    //cout << left << "???" << right << endl;

    

    if (right - left == 1) return right;

    int mid = (right + left)/2;

    int nn = rec(mid);

    if (nn >= n) {

        return binary(left,mid);

    }else{

        return binary(mid,right);

    }

}



int main(){

    int sum=0;

    cin >> n >> k;

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

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

        sum += W[i];

    }

    int min_p = sum/k;

    if (sum%k != 0) {

        min_p++;

    }

    cout << binary(min_p-1,sum) << endl;

    

    

    return 0;

}

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

using namespace std;

const int MAX_N = 100000;

const int MAX_W = 10000;

typedef long long llong;



int n, k;

llong w[MAX_N];



int check(llong P) {

  int i = 0;

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

    llong s = 0;

    while( s + w[i] <= P) {

      s += w[i];

      i++;

      if ( i == n ) return n;

    }

  }

  return i;

}



int solve() {

  llong left = 0;

  llong right = n * MAX_W;

  llong mid;

  while ( right - left > 1 ) {

    mid = (left + right) / 2;

    int v = check(mid);

    if ( v >= n ) right = mid;

    else left = mid;

  }



  return right;

}



int main() {

  cin >> n >> k;

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

  llong ans = solve();

  cout << ans << endl;



  return 0;

}


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

const int MAX_N = 100000;

const int MAX_W = 10000;

typedef long long llong;



int n, k;

llong w[MAX_N];



int check(llong P) {

  int i = 0;

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

    llong s = 0;

    while( s + w[i] <= P) {

      s += w[i];

      i++;

      if ( i == n ) return n;

    }

  }

  return i;

}



int solve() {

  llong left = 0;

  llong right = n * MAX_W;

  llong mid;

  while ( right - left > 1 ) {

    mid = (left + right) / 2;

    int v = check(mid);

    if ( v >= n ) right = mid;

    else left = mid;

  }

  return right;

}



int main() {

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

  for ( int i = 0; i < n; i++ ) scanf("%lld", &w[i]);

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

  return 0;

}


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

using namespace std;

#define MAX 100000

typedef long long llong;



int n, k;

llong T[MAX];



int check(llong p) {

  int i = 0;

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

    llong s = 0;

    while( s + T[i] <= p ) {

      s += T[i];

      i++;

      if ( i == n ) return n;

    }

  }

  return i;

}



llong solve() {

  llong left = 0;

  llong right = 100000 * 10000;

  llong mid;

  while ( right - left > 1 ) {

    mid = (left + right) / 2;

    int v = check(mid);

    if ( v >= n ) right = mid;

    else left = mid;

  }



  return right;

}



int main() {

  cin >> n >> k;

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

  llong ans = solve();

  cout << ans << endl;

}

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



#define MAX_NUM_OF_PACKS 100000

#define MAX_WEIGHT_OF_A_PACK 10000

#define MAX_TOTAL_WEIGHT MAX_NUM_OF_PACKS * MAX_WEIGHT_OF_A_PACK



int n, k, W[MAX_NUM_OF_PACKS];



bool valid(int p, int ck, int ci) {

  if (ci >= n) return true;

  if (ck >= k || p < W[ci]) return false;



  int tp = p;

  while(tp >= W[ci] && ci < n) {

    tp -= W[ci];

    ci++;

  }



  return valid(p, ck + 1, ci);

}



int minimum(int left, int right) {

  int mid = (left + right) / 2;

  bool result = valid(mid, 0, 0);

  if( mid == left && result) return mid;

  if (result) return minimum(left, mid);

  else return minimum(mid + 1, right);

}



int main() {



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

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



  printf("%d\n", minimum(0, MAX_TOTAL_WEIGHT));

  return 0;

}




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

using namespace std;

const int INF = 1e9;



int n, k, w[100000];

int w_mx = 0;



bool b_search(int p)

{

  int pointer = 0;

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

    int truck = 0;

    while(pointer < n && truck + w[pointer] <= p)

      truck += w[pointer++];

  }

  

  if(pointer < n)

    return false;

  return true;

}



int main()

{

  cin >> n >> k;

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

    cin >> w[i];



  int s = 0, e = INF;

  while(e - s > 1){

    int mid = (s + e) / 2;

    if(b_search(mid))

      e = mid;

    else

      s = mid;

  }



  cout << e << endl;

  return 0;

}

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

using namespace std;

const int INF = 1e9;



int n, k, w[100000];

int w_mx = 0;



bool b_search(int p)

{

  int pointer = 0;

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

    int truck = 0;

    while(pointer < n && truck + w[pointer] <= p)

      truck += w[pointer++];

  }

  

  if(pointer < n)

    return false;

  return true;

}



int main()

{

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

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

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



  int s = 0, e = INF;

  while(e - s > 1){

    int mid = (s + e) / 2;

    if(b_search(mid))

      e = mid;

    else

      s = mid;

  }



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

  return 0;

}

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

using namespace std;



#define MAX 100000

typedef long long llong;



int n,k;

llong T[MAX];



int check(int P){

    int j=0;

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

        llong sum=0;

        while(sum+T[j]<=P){

            sum += T[j];

            j++;

            if(j==n)return n;

        }

    }

    return j;

}



int main(){

    cin >> n >> k;

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



    llong left=0,right=100000*10000,mid;

    while(right-left>1){

        mid = (left+right)/2;

        if(check(mid)>=n)right=mid;

        else left=mid;

    }

    cout << right << endl;



    return 0;

}




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

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <functional>

#include <map>

#include <set>

#include <cmath>

#include <string>

#define SIZE 100005

#define INF 1000000005LL



using namespace std;

typedef long long int ll;

typedef pair <int,int> P;



int n;

int k;

int T[SIZE];



bool check(int m){

	int cw = 0;

	int car=1;

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

		if(T[i]>m)return false;

		else if(T[i]+cw>m){

			cw = T[i];

			car++;

			if(car>k)return false;

		}else{

			cw += T[i];

		}

	}

	return true;

}



int main()

{

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

	int r=0;

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

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

		r+=T[i];

	}

	r++;

	int l=0,m;

	while(l+1<r){

		m=(l+r)/2;

		if(check(m))r=m;

		else l=m;

	}

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

	return 0;

}




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

#include <vector>



using namespace std;



static int f(const vector<int>& ws, int P, int k) {

  int v = 0;

  int c = 0;

  int ntrack = 0;

  for (size_t i = 0; i < ws.size(); ++i) {

    if (c > 0 && P > 0 && c + ws[i] > P) {

      c = 0;

      ntrack++;

    }

    if (ntrack == k) {

      break;

    }



    if (c + ws[i] <= P) {

      c += ws[i];

      v++;

    }

  }

  return v;

}



int main() {

  int n, k;



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



  vector<int> ws(n);

  int max = 0;

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

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

    max += ws[i];

  }



  int min = 1;

  int P = (min + max) / 2;

  while (min <= max) {

    const int v = f(ws, P, k);

    if (v >= n) {

      max = P - 1;

    } else { // v < n

      min = P + 1;

    }

    P = (min + max) / 2;

  }



  printf("%d\n", P+1);

  return 0;

}

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

#include <vector>



using namespace std;



static int f(const int* ws, int n, int P, int k) {

  int v = 0;

  int c = 0;

  int ntrack = 0;

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

    if (c > 0 && P > 0 && c + ws[i] > P) {

      c = 0;

      ntrack++;

    }

    if (ntrack == k) {

      break;

    }



    if (c + ws[i] <= P) {

      c += ws[i];

      v++;

    }

  }

  return v;

}



int main() {

  int n, k;



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



  //vector<int> ws(n);

  int ws[100000];

  int max = 0;

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

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

    max += ws[i];

  }



  int min = 1;

  int P = (min + max) / 2;

  while (min <= max) {

    if (f(ws, n, P, k) >= n) {

      max = P - 1;

    } else { // v < n

      min = P + 1;

    }

    P = (min + max) / 2;

  }



  printf("%d\n", P + 1);

  return 0;

}

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

#include <vector>



using namespace std;



inline int f(const vector<int>& ws, int P, int k) {

  int v = 0;

  int c = 0;

  int ntrack = 0;

  for (size_t i = 0; i < ws.size(); ++i) {

    if (c > 0 && P > 0 && c + ws[i] > P) {

      c = 0;

      ntrack++;

    }

    if (ntrack == k) {

      break;

    }



    if (c + ws[i] <= P) {

      c += ws[i];

      v++;

    }

  }

  return v;

}



int main() {

  int n, k;



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



  vector<int> ws(n);

  int max = 0;

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

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

    max += ws[i];

  }



  int min = 1;

  int P = (min + max) / 2;

  while (min <= max) {

    const int v = f(ws, P, k);

    if (v >= n) {

      max = P - 1;

    } else { // v < n

      min = P + 1;

    }

    P = (min + max) / 2;

  }



  printf("%d\n", P+1);

  return 0;

}

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

#include <vector>



using namespace std;



static int f(const int* ws, int n, int P, int k) {

  int v = 0;

  int c = 0;

  int ntrack = 0;

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

    if (c > 0 && P > 0 && c + ws[i] > P) {

      c = 0;

      ntrack++;

    }

    if (ntrack == k) {

      break;

    }



    if (c + ws[i] <= P) {

      c += ws[i];

      v++;

    }

  }

  return v;

}



int main() {

  int n, k;



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



  //vector<int> ws(n);

  int ws[100000];

  int max = 0;

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

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

    max += ws[i];

  }



  int min = 1;

  int P = (min + max) / 2;

  while (min <= max) {

    if (f(ws, n, P, k) >= n) {

      max = P - 1;

    } else { // v < n

      min = P + 1;

    }

    P = (min + max) / 2;

  }



  printf("%d\n", P + 1);

  return 0;

}

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

#include <vector>

#include <algorithm>

 

using namespace std;

typedef long long ll;

 

int main() {

  int N;

  cin >> N;

  vector<ll> A(N);

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

    cin >> A[i];

  }

  vector<ll> acc(N + 1);

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

    acc[i + 1] = acc[i] + A[i];

  }



  ll ans = 1LL << 62;

  for(int j = 2; j < N; j++) {

    int i1 = lower_bound(acc.begin(), acc.begin() + j, acc[j] / 2) - acc.begin();

    int i2 = i1 - 1;

    int k1 = lower_bound(acc.begin() + j, acc.end(), (acc[N] - acc[j]) / 2 + acc[j]) - acc.begin();

    int k2 = k1 - 1;

    vector<int> I = {i1}, K = {k1};

    if (i2 > 0) I.push_back(i2);

    if (k2 > j) K.push_back(k2);

    for(int ii = 0; ii < I.size(); ii++) {

      for(int kk = 0; kk < K.size(); kk++) {

        int i = I[ii], k = K[kk];

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

      }

    }

  }

  cout << ans << endl;

  return 0;

}

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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

        scanf("%lld", &A[i]);

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

}


// 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

constexpr int INF = 1 << 29;

constexpr int MOD = 1000000007;

typedef long long ll;

typedef unsigned long long ull;



constexpr int dx[4] = {1, 0, -1, 0};

constexpr int dy[4] = {0, 1, 0, -1};



int main() {

    int N;

    cin >> N;

    vector<ll> A(N);

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

        cin >> A[i];

    }

    vector<ll> acc(N + 1);

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

    }

    cout << ans << endl;

    return 0;

}


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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

        scanf("%lld", &A[i]);

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

}


// 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

constexpr int INF = 1 << 29;

constexpr int MOD = 1000000007;

typedef long long ll;

typedef unsigned long long ull;



constexpr int dx[4] = {1, 0, -1, 0};

constexpr int dy[4] = {0, 1, 0, -1};



int main() {

    int N;

    scanf("%d", &N);

    vector<ll> A(N);

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

        scanf("%lld", &A[i]);

    }

    vector<ll> acc(N + 1);

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

    }

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

    return 0;

}


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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

        scanf("%lld", &A[i]);

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

}


// Fastest known solution for this problem: