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

#include <stdio.h>

#include <cstring>

#include <algorithm>

#define ll long long

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

using namespace std;

const int N = 1e5 + 9, M = 2e5 + 9;

const int inf = 0x3f3f3f3f;

int a[N], s[N], tr[M], n;

int lowbit(int x) { return x & (-x); }

void add(int x){ while(x < M) tr[x]++, x += lowbit(x); }

ll query(int x){

    ll res = 0;

    while(x > 0) res += tr[x], x -= lowbit(x);

    return res;

}

bool check(int x){

    ll res = 0;

    rep(i, 1, n) s[i] = s[i-1] + (a[i] >= x ? 1 : -1);

    memset(tr, 0, sizeof tr);

    rep(i, 0, n) res += query(s[i] + N), add(s[i] + N);

    return res * 2 >= 1ll * n * (n+1) / 2; 

}

int erfen(int l, int r){

    int res = 0;

    while(l <= r){

        int mid = (l + r) / 2;

        if(check(mid)) res = mid, l = mid+1;

        else r = mid-1;

    }

    return res;

}

int main(){

    int minn = inf, maxx = 0;

    scanf("%d", &n);

    rep(i, 1, n) {

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

        maxx = max(maxx, a[i]), minn = min(minn, a[i]);

    }

    printf("%d", erfen(minn, maxx));

    return 0;

}

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

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head







const int N = 1e6+50;

int n, a[N], b[N];

int f[2*N], *cnt = f+N;



//求出中位数>=x的子区间个数

ll calc(int x) {

	REP(i,-n,n) cnt[i] = 0;

	ll ans = 0;

	int ret = 0, sum = 0, pos = 0;

	//ret维护0<=j<=i-1, s[j]<=s[i]的j的个数

	REP(i,1,n) {

		++cnt[sum], ++ret;

		if (a[i]>=x) ret += cnt[++sum];

		else ret -= cnt[sum--];

		ans += ret;

	}

	return ans;

}



int main() {

	scanf("%d", &n);

	REP(i,1,n) scanf("%d",a+i),b[i]=a[i];

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

	int l=1,r=n,ans;

	ll m = (n+1ll)*n/2, pos = (m+1)/2;

	while (l<=r) {

		if (calc(b[mid])>=pos) ans=mid,l=mid+1;

		else r=mid-1;

	}

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

}


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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define int long long

#define N 100002

using namespace std;

int n,i,a[N],b[N],c[N*2],sum[N],l=0,r,mid,ans;

int read()

{

	char c=getchar();

	int w=0;

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

int lowbit(int x)

{

	return x&(-x);

}

void add(int x,int y)

{

	for(int i=x;i<=200000;i+=lowbit(i)) c[i]+=y;

}

long long ask(int x)

{

	long long ans=0;

	for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];

	return ans;

}

bool check(int x)

{

	sum[0]=100000;

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

		if(a[i]>=x) sum[i]=sum[i-1]+1;

		else sum[i]=sum[i-1]-1;

	}

	memset(c,0,sizeof(c));

	long long ans=0;

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

		ans+=ask(sum[i]);

		add(sum[i],1);

	}

	return (ans>=1LL*n*(n+1)/4);

}

signed main()

{

	n=read();

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

		a[i]=read();

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

	}

	while(l<=r){

		mid=(l+r)/2;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	cout<<ans<<endl;

	return 0;

}

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

using namespace std;

//#include<ext/rope>

//using namespace __gnu_cxx

//#include<ext/pb_ds/priority_queue.hpp>

//using namespace __gnu_pbds;

#define lowbit(x) (x&-x)

#define pb push_back

#define empb emplace_back

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

#define clr(a,b) memset(a,b,sizeof(a))

#define caze(T) for(cin>>T;T;T--)

#define inf (1<<29)

#define Endl ('\n')

#define fi first

#define se second

#define db double

#define ldb long double

#define ll long long

#define pii pair<int,int>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pll pair<ll,ll>

#define ull unsigned long long

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

inline char nc() {

	#define SZ 1000000

	static char buf[SZ], *p1, *p2;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;

}

template<typename T>

inline int scan(T &x) {

	char c, sign=1; 

	while(!isdigit(c=nc())&&c!=EOF)if(c=='-')sign*=-1;

	if(c==EOF) return EOF;

	for(x = 0; isdigit(c); c = nc())

		x = (x<<1) + (x<<3) + (c&15);

	return x *= sign, 1;

}

template<typename T, typename...Args>

inline int scan(T &x, Args&...args) {

	return scan(x), scan(args...);

}

const int N=1<<18;

const int zero=1<<17;

int t[N],a[N],n;

int b[N],cc;

void add(int x,int v){for(;x<N;t[x]+=v,x+=lowbit(x));}

int sum(int x){int ret=0;while(x)ret+=t[x],x-=lowbit(x);return ret;}

int sum(int l,int r){return sum(r)-sum(l-1);}

ll calc(int x)

{

	int y=zero;

	ll ret=0;

	clr(t,0);

	add(zero,1);

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

	{

		y+=(a[i]<=x?1:-1);

		ret+=sum(y-1);

		add(y,1);

	}

	return ret;

} 

int main()

{IOS;

	cin>>n;cc=0;

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

		cin>>a[i],b[++cc]=a[i];

	sort(b+1,b+1+cc);

	cc=unique(b+1,b+1+cc)-b-1;

	int L=1,R=cc,mid;

	ll ans,tp;

	ll ok=1LL*(n+1)*n/4+1;

	while(R>=L)

	{

		mid=(L+R)>>1;

		if((tp=calc(b[mid]))>=ok)

			ans=b[mid],R=mid-1;

		else L=mid+1;

	}

	cout<<ans<<Endl;

}

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

  ll m = n * (n+1) / 2;

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th, vecint& v) {

  ll n = a.size();

  v.assign(n*4, 0);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

  ll m = n * (n+1) / 2;

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  scanf("%d", &n);

  vecint a(n);

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

  int hi = 1000000001;

  int lo = 0;

  vecint v(n*4);

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, mid, v)) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

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

  return 0;

}


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

#define ll long long

using namespace std;

const int N=100011;

int n,a[N],r=0,l=0;

int c[N*10],s[N<<1  ];

void add(int x)

{

	while(x<=N*2)

	  c[x]++,x+=x&(-x);

}

ll ask(int x)

{

	ll ans=0;

	while(x)

	{

		ans+=c[x];

		x-=x&(-x);

	}

	return ans;

}

bool check(int x)

{

	for(int i=1;i<=2*N;i++) c[i]=0;

	s[0]=0;

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

	  s[i]=s[i-1]+(a[i]>=x?1:-1);

	ll sum=0;

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

    {

       sum+=ask(s[i]+N);

       add(s[i]+N);

	} 

	return sum>=(ll)n*(n+1)/4;

}

int main()

{

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

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

  scanf("%d",&n);

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

  while(l<=r)

  {

  	int mid=(l+r)>>1;

  	if(check(mid)) 

	  l=mid+1;

	else r=mid-1;

  }

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

  return 0;

}


// Optimized solution to the same problem (faster):
#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 loop(i, n) for(int i = 0;i < int(n);i++)

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

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

#define SZ(c) int(c.size())

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

#define RALL(c) c.rbegin(), c.rend()

#define PI acos(-1)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define sfi1(v) scanf("%d",&v)

#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)

#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)

#define sfll1(v) scanf("%I64d",&v);

#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)

#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)

#define endl '\n'



typedef vector<int> vi;

typedef vector<pair<int, int> > vii;

typedef long long ll;

typedef pair<int, int> pii;



template<typename T>

using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;





const int N = 1e5 + 5;

int arr[N];

int acc[N];

int n;



bool valid(int val) {

    range(i, 1, n) {

        if (arr[i] < val)acc[i] = -1;

        else acc[i] = 1;

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

    }



    Tree<pii> X;

    X.insert({0, 0});

    ll res = 0;

    range(i, 1, n) {

        int cnt = X.order_of_key(mp(acc[i], n + n));

        res += cnt;

        X.insert(mp(acc[i], i));

    }



    //cout << val << " " << res  << " " << (res*2 >= 1LL * n * (n + 1) / 2) << endl;

    return (res * 2 >= 1LL * n * (n + 1) / 2);

}



int main() {



#ifndef ONLINE_JUDGE

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

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

#endif

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);



    cin >> n;

    vi v(n);

    range(i, 1, n)cin >> arr[i], v[i - 1] = arr[i];

    sort(ALL(v));

    v.resize(unique(ALL(v)) - v.begin());



    //loop(i,SZ(v))valid(v[i]);



    int s = 0, e = SZ(v) - 1;

    while (s < e) {

        int mid = s + (e - s + 1) / 2;

        if (valid(v[mid]))

            s = mid;

        else

            e = mid - 1;

    }



    cout << v[e] << endl;





    return 0;

}


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

using namespace std;

#define maxn 100005

inline void read(int& x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,a[maxn],sum[maxn],c[maxn+maxn];



inline int lowbit(int x)

{

	return x&(-x);

}

inline void modify(int pos)

{

	for(int i=pos;i<=n+100000;i+=lowbit(i)) ++c[i];

}

inline int query(int pos)

{

	int ans=0;

	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];

	return ans;

}



bool check(int x)

{

	sum[0]=0;

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

		sum[i]=sum[i-1]+(a[i]>=x?1:-1);

	memset(c,0,sizeof(c));

	long long ans=0;

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

	{

		ans+=query(sum[i]+100000);

		modify(sum[i]+100000);

	}

	return (ans<<2)>=1ll*n*(n+1);

}

int main()

{

	int l=0x3f3f3f3f,r=-0x3f3f3f3f,mid;

	read(n);

	for(int i=1;i<=n;++i) read(a[i]),l=min(l,a[i]),r=max(r,a[i]);

	while(l<=r)

	{

		mid=(l+r)>>1;

		if(check(mid)) l=mid+1;

		else r=mid-1;

	}

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

	return 0;

}

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

#include <ext/pb_ds/detail/standard_policies.hpp>

#include <ext/pb_ds/assoc_container.hpp>



using namespace std;

using namespace __gnu_pbds;



template<typename T>

using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



template<typename T>

using normal_queue = priority_queue<T, vector<T>, greater<T>>;



#define int long long



bool check(int x, int n, vector<int>& a) {

    int cnt = 0, nw = 0;

    ordered_set<pair<int, int>> c;

    c.insert({0, 0});

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

        if (a[i] >= x) {

            nw++;

        } else {

            nw--;

        }

        cnt += c.order_of_key({nw, n + 10});

        c.insert({nw, i + 1});

    }

    return cnt >= (n * (n + 1) / 2 + 1) / 2;

}



void solve() {

    int n;

    cin >> n;

    vector<int> a(n);

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

        cin >> a[i];

    }

    int l = -1, r = 1e9 + 10;

    while (r - l > 1) {

        //cout << l << " " << r << " >\n";

        int m = (l + r) / 2;

        if (check(m, n, a)) {

            l = m;

        } else {

            r = m;

        }

    }

    cout << l << "\n";

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;

}




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

using namespace std;

const int N = 1e5 + 87;

const int M = N * 2;

int n,a[N],f[M];

void add(int i)

{

    for (; i < M; i += i & -i)

        ++f[i];

}

int qry(int i)

{

    int r=0;

    for (; i ; i ^= i & -i)

        r += f[i];

    return r;

}

bool ok(int k)

{

    memset(f,0,sizeof(f));

    int s = N;

    add(s);

    long long t = (n * (n + 1LL) / 2 + 1) / 2;

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

        s += a[i] >= k ? 1 : -1;

        t -= qry(s);

        add(s);

    }

    return t <= 0;

}

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

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

        cin >> a[i];

    int lo = 1, hi = 1e9;

    while (lo <= hi) {

        int mi = (lo + hi) / 2;

        if (ok(mi))

            lo = mi + 1;

        else

            hi = mi - 1;

    }

    cout << hi << '\n';

}


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

using namespace std;

const int N = 1e5 + 87;

const int M = N * 2;

int n,a[N],b[N],f[M];

void add(int i)

{

    for (; i < M; i += i & -i)

        ++f[i];

}

int qry(int i)

{

    int r=0;

    for (; i ; i ^= i & -i)

        r += f[i];

    return r;

}

bool ok(int k)

{

    memset(f,0,sizeof(f));

    int s = N;

    add(s);

    long long t = (n * (n + 1LL) / 2 + 1) / 2;

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

        s += a[i] >= k ? 1 : -1;

        t -= qry(s);

        add(s);

    }

    return t <= 0;

}

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

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

        cin >> a[i];

    copy_n(a+1,n,b);

    sort(b,b+n);

    int bn = unique(b,b+n) - b, ans = 0;

    for (int k = 1<<__lg(bn); k; k >>= 1)

        if ((ans | k) < bn && ok(b[ans | k]))

            ans |= k;

    cout << b[ans] << '\n';

}


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

#include <cstring>

#include <cstdio>

#define ll long long

#define int ll

#define lowbit(a) a&(-a)

using namespace std;



inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}

	return f*sum;

}



const int N=200000;

const int M=100000;

int n,m,a[N+5];

ll t[N+5],c[N+5],tem;



inline void add(int x){for(;x<=N;x+=lowbit(x)) t[x]++;}



inline ll ask(int x){ll ret=0;for(;x;x-=lowbit(x)) ret+=t[x];return ret;}



inline int check(int x){

	ll cnt=0;

	memset(t,0,sizeof(t));

	for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]<=x? 1:-1);

	add(1+M);

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

		cnt+=ask(c[i]+M);

		add(c[i]+1+M);

	}

	return cnt>tem;

}



signed main(){

	n=read();

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

	ll l=0,r=0;

	for(int i=1;i<=n;i++) r=max(r,(ll)a[i]);

	ll ans=r;

	tem=n*(n+1)/2;tem/=2;

	while(l<=r){

	ll mid=(l+r)>>1;

	if(check(mid)) ans=min(ans,mid),r=mid-1;

	else l=mid+1;

}

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

	return 0;

}


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

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<queue>

#include<ctime>

#include<cassert>

#include<complex>

#include<string>

#include<cstring>

#include<chrono>

#include<random>

#include<bitset>

#include<iomanip>



#define fi first

#define se second

#define mp make_pair

#define eb emplace_back

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

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



using namespace std;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<int, int> pii;



const int MAX_N = 1e5 + 5;



int n, a[MAX_N];

int pref[MAX_N], fenw[MAX_N * 2];



void update(int pos, int delta) {

	for (int i = pos; i <= 2 * n; i |= (i + 1)) {

		fenw[i] += delta;

	}

}



int get(int r) {

	int res = 0;

	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {

		res += fenw[i];

	}

	return res;

}



bool check(int m) {

	fill(fenw, fenw + 2 * n + 1, 0);

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

		pref[i] = pref[i - 1] + (a[i] >= m) - (a[i] < m);

	}

	update(n, 1);

	ll cnt = 0;

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

		cnt += get(pref[i] + n);

		update(pref[i] + n, 1);

	}

	return cnt >= (1ll * n * (n + 1) / 2 + 1) / 2;

}



signed main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin >> n;

	vector<int> diff;

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

		cin >> a[i];

		diff.eb(a[i]);

	}

	sort(all(diff));

	diff.resize(unique(all(diff)) - diff.begin());

	int lef = 0, rig = sz(diff);

	while (lef + 1 < rig) {

		int mid = (lef + rig) / 2;

		if (check(diff[mid])) {

			lef = mid;

		} else {

			rig = mid;

		}

	}

	cout << diff[lef] << "\n";

	return 0;

}

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

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

 



 

int main(){

 

	int n; 

	while(scanf("%d",&n),n){



		vector<pair<int,int> > rw(n);

		int sum_r=0,sum_w=0;

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

			cin>>rw[i].first>>rw[i].second;

			sum_r+=rw[i].first;

			sum_w+=rw[i].second;

		}

		sort(rw.begin(),rw.end(),greater< pair<int,int> >());



		int r0=rw[0].first;

		int r=sum_r-r0;



		if(r0 <= r){

			cout<<sum_r+sum_w<<endl;

		}else{



			int res=2*rw[0].first;

			vector<vector<bool> > dp(1001,vector<bool>(1000,false));



			//r0-r???w?????°??????

			//dp[pos][sum]



			dp[1][0]=true;

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

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

					if(dp[i][j]){

						dp[i+1][j]=true; //??°?????????

						if(j+rw[i].second<=10000)

							dp[i+1][j+rw[i].second]=true; //??°??????

					}

				}

			}



			int opt=0;

			for(int i=1;i<=r0-r;i++){

				if(dp[n][i]) opt=i;

			}



			res+=sum_w-opt;

			cout<<res<<endl;







		}

		

		

	}

}

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

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

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

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

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

//			bool cur[1001]={};

			bool *cur = (bool*)malloc( sizeof(bool)*(1000+2) );

            cur[0]=true;

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

				bool *next = (bool*)malloc( sizeof(bool)*(1000+2) );

                for(int j=0;j<=r0-r;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<=r0-r)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

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

  

  

  

        }

          

          

    }

}

// Fastest known solution for this problem: