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

using namespace std;

typedef long long ll;

ll dp[405][405];

ll sum[405];

ll a[405];

int main(){

	int n;

	scanf("%d",&n);

	memset(dp,0,sizeof(dp));

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

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

		sum[i] = sum[i - 1] + a[i];

	}

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

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

			int ends = i + j - 1;

			dp[j][ends] = 1e17;

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

				dp[j][ends]=min(dp[j][ends],dp[j][k] + dp[k + 1][ends] + sum[ends] - sum[j - 1]);//中间重复的部分用前缀和加上去，妙啊！

			}

		}

	}

	printf("%lld\n",dp[1][n]);

	return 0;

}

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

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 405

using namespace std;

using LL = long long;

int n,a[M];

bool vis[M][M];

LL dp[M][M],pre[M];



LL dfs(int x,int y) {

    if (x==y) return 0LL;

    if (vis[x][y]) return dp[x][y];

    vis[x][y] = true;

    LL &res = dp[x][y];



    LL sum = pre[y] - pre[x-1];

    res = (1LL << 61);

    REP(i,x,y-1) res = min(res, dfs(x,i) + dfs(i+1,y) + sum);

    return res;

}

int main()

{

    scanf("%d", &n);

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



    pre[0] = 0;

    REP(i,1,n) pre[i] = pre[i-1] + a[i];

    printf("%lld\n", dfs(1,n));

    return 0;

}


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

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<stack>

#include<set>

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 5e2 + 5;

const int inf = 0x3f3f3f3f;

const int inF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const db eps = 1e-8;

ll a[maxn] , dp[maxn][maxn][2];

int main(){

	int n;cin >> n;

	memset(dp, inf , sizeof dp);

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

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

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

			int k = j+i-1;

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

				dp[j][k][0] = min(dp[j][k][0] , dp[j][m][0]+dp[m+1][k][0]+dp[j][m][1] + dp[m+1][k][1]);

			}

			dp[j][k][1] = dp[j][k-1][1]+a[k];

		}

	}

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

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

		cout << endl;

	}*/

	cout << dp[1][n][0] << endl;

	return 0;

}

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

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 405

using namespace std;

using LL = long long;

int n,a[M];

bool vis[M][M];

LL dp[M][M],pre[M];



LL dfs(int x,int y) {

    if (x==y) return 0LL;

    if (vis[x][y]) return dp[x][y];

    vis[x][y] = true;

    LL &res = dp[x][y];



    LL sum = pre[y] - pre[x-1];

    res = (1LL << 61);

    REP(i,x,y-1) res = min(res, dfs(x,i) + dfs(i+1,y) + sum);

    return res;

}

int main()

{

    scanf("%d", &n);

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



    pre[0] = 0;

    REP(i,1,n) pre[i] = pre[i-1] + a[i];

    printf("%lld\n", dfs(1,n));

    return 0;

}


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



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

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

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

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

using namespace std;

typedef long long LL;

typedef pair<LL, LL> ii;

typedef vector<LL> vi;



template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }



void dbg_out() { cerr << "\n"; }

template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }



const int N = 405;

LL arr[N];

LL pre[N];

LL dp[N][N];





LL dfs(int l, int r){

    //dbg_out(l, r);

    if(l == r) return 0;

    if(dp[l][r] != -1) return dp[l][r];

    LL res = pre[r+1] - pre[l];

    LL mn = 1e14;

    for(int k = l; k < r; ++k){

        mn = min(mn, dfs(l, k) + dfs(k+1, r));

    }

    return dp[l][r] = res + mn;

}



void solve(){

    int n;

    cin >> n;

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

    pre[0] = 0;

    for(int i = 0; i < n; ++i) pre[i+1] += pre[i] + arr[i];



    memset(dp, -1, sizeof dp);

    cout << dfs(0, n-1) << "\n";

}



int main()

{

    Fast;

    //louisfghbvc{

        solve();

    //}

    return 0;

}


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

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 405

using namespace std;

using LL = long long;

int n,a[M];

bool vis[M][M];

LL dp[M][M],pre[M];



LL dfs(int x,int y) {

    if (x==y) return 0LL;

    if (vis[x][y]) return dp[x][y];

    vis[x][y] = true;

    LL &res = dp[x][y];



    LL sum = pre[y] - pre[x-1];

    res = (1LL << 61);

    REP(i,x,y-1) res = min(res, dfs(x,i) + dfs(i+1,y) + sum);

    return res;

}

int main()

{

    scanf("%d", &n);

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



    pre[0] = 0;

    REP(i,1,n) pre[i] = pre[i-1] + a[i];

    printf("%lld\n", dfs(1,n));

    return 0;

}


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



using namespace std;



typedef long long ll;



const int N = 405;

ll arr[N];

ll cost[N][N];

ll dp[N][N];



ll solve(int i, int j)

{

  if(i == j)

    return 0;

  ll &ans = dp[i][j];

  if(~ans)

    return ans;

  ans = 1e18;

  for(int z = i; z <= j; z++)

  {

    ans = min(ans, cost[i][z] + solve(i, z) + solve(z + 1, j) + cost[z + 1][j]);

  }

  return ans;

}



int main()

{

  int n;

  cin >> n;

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

    cin >> arr[i];

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

  {

    cost[i][i] = arr[i];

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

      cost[i][j] = cost[i][j - 1] + arr[j];

  }

  memset(dp, -1, sizeof dp);

  cout << solve(0, n - 1);

  return 0;

}


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



using namespace std;



typedef long long ll;



const int N = 405;

ll arr[N];

ll dp[N][N];

ll cost[N][N];



int main()

{

  int n;

  cin >> n;

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

    cin >> arr[i];

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

  {

    cost[i][i] = arr[i];

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

      cost[i][j] = cost[i][j - 1] + arr[j];

  }

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

  {

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

    {

      dp[i][j] = 1e18;

      for(int z = i; z <= j; z++)

      {

        dp[i][j] = min(dp[i][j], cost[i][z] + cost[z + 1][j] + dp[i][z] + dp[z + 1][j]);

      }

    }

  }

  cout << dp[0][n - 1];

  return 0;

}


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

const int INF=1e9,MOD=1e9+7;

const long long LINF=1e18;

using namespace std;

#define int long long

//template

typedef pair<int,int> P;

P dp[402][402];

std::vector<int> v(500);

P f(int i,int j){

  if(dp[i][j]!=P(-1,-1))return dp[i][j];

  if(i==j)return P(v[i],v[i]);

  int res=LINF;

  for(int k=i;k<j;k++)res=min(res,f(i,k).first+f(k+1,j).first);

  return dp[i][j]=P(res+f(i,i).second+f(i+1,j).second,f(i,i).second+f(i+1,j).second);

}

//main

signed main(){

  int N;cin>>N;

  for(int i=0;i<N;i++)cin>>v[i];

  memset(dp,-1,sizeof(dp));

  /*

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

    for(int j=0;j<N;j++)cout<<i<<" "<<j<<" "<<f(i,j).first<<endl;

  }

  */

  cout<<f(0,N-1).first-f(0,N-1).second<<endl;

}


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

using namespace std;



template<typename T>

void chmin(T &a,T b){

  if(a>b||!a)a=b;

}

using ll=long long;

ll dp[500][500],wa[500],v[500];

ll f(int l,int r){

  if(~dp[l][r])return dp[l][r];

  ll res=0;

  for(int i=l+1;i<r;i++)chmin(res,f(l,i)+f(i,r));

  return dp[l][r]=res+wa[r]-wa[l];

}



signed main(){

  memset(dp,-1,sizeof(dp));

  int n;cin>>n;

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

  for(int i=0;i<n;i++)wa[i+1]=wa[i]+v[i];

  cout<<f(0,n)-wa[n]<<endl;

}


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

using namespace std;

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

typedef long long ll;

const int MAX = 401;

const ll INF = 1e17;



ll sum[MAX] = {};

vector<vector<ll>> dp(MAX, vector<ll>(MAX,-1));



ll dfs(int i, int j){

    if(dp[i][j] != -1) return dp[i][j];

    if(i == j) return dp[i][j] = 0;

    ll d = INF;

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

        d = min(d,dfs(i,k)+dfs(k+1,j)+sum[j]-sum[i-1]);

    }

    return dp[i][j] = d;

}





int main(){

    int n;

    cin >> n;

    rep(i,n){ 

        ll a;

        cin >> a;

        sum[i+1] += sum[i] + a;

    }

    cout << dfs(1,n) << endl;

    return 0;

}

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

using namespace std;

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

using ll = long long;

const ll INF = 1e17;



int main(){

  int n;

  cin >> n;

  ll a[n];

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

  vector<vector<ll>> dp(n,vector<ll>(n,INF));

  vector<ll> sum(n+1);

  rep(i,n) {

    dp[i][i] = 0;

    sum[i+1] = sum[i] + a[i];

  }

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

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

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

        dp[j][i+j] = min(dp[j][i+j],dp[j][k]+dp[k+1][i+j]+sum[i+j+1]-sum[j]);

      }

    }

  }

  cout << dp[0][n-1] << endl;

  return 0;

}

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

*  Author: xuziyuan  * 

*********************/



#include <bits/stdc++.h>



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

#define repn(i,n) for(int i=1;i<=n;i++)

#define LL long long

#define pii pair <int,int>

#define fi first

#define se second

#define pb push_back

#define mpr make_pair



using namespace std;



const LL MOD=1e9+7;



LL n,x,sum[410],dp[410][410];



LL dfs(int lb,int ub)

{

  if(dp[lb][ub]!=-1) return dp[lb][ub];

  if(lb==ub) return dp[lb][ub]=0;

  dp[lb][ub]=1e18;

  for(int i=lb;i<ub;i++) dp[lb][ub]=min(dp[lb][ub],dfs(lb,i)+dfs(i+1,ub)+sum[ub+1]-sum[lb]);

  return dp[lb][ub];

}



int main()

{

  cin>>n;

  repn(i,n)

  {

    cin>>x;

    sum[i]=sum[i-1]+x;

  }

  rep(i,405) rep(j,405) dp[i][j]=-1;

  cout<<dfs(0,n-1)<<endl;

  return 0;

}

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



#define LL long long



using namespace std;



LL n,a[410],dp[410][410],sum[410];



int main()

{

  cin>>n;

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

  {

	cin>>a[i];

    sum[i+1]=sum[i]+a[i];

  }

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

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

    {

      if(i+len-1>=n) break;

      int j=i+len-1;

      dp[i][j]=1e18;

      for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]);

    }

  cout<<dp[0][n-1]<<endl;

  return 0;

}

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

#define ll long long

const int N=5e5+10,mod=998244353;

int n,m,ans,fc[N],fi[N];

int main(){

	std::cin>>n>>m,fc[0]=fc[1]=fi[0]=fi[1]=1;

	for(int i=2;i<=m;i++)fc[i]=(ll)fc[i-1]*i%mod;

	for(int i=2;i<=m;i++)fi[i]=(ll)(mod-mod/i)*fi[mod%i]%mod;

	for(int i=2;i<=m;i++)fi[i]=(ll)fi[i-1]*fi[i]%mod;

	for(int i=n;i<=m;i++)ans=(ans+(ll)fc[m-1]*fi[i-1]%mod*fi[m-i])%mod;

	std::cout<<ans;

}

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



typedef long long LL;

const int Mod = 998244353;



inline int qPow(int b, int e) {

	int a = 1;

	for (; e; e >>= 1, b = (LL)b * b % Mod)

		if (e & 1) a = (LL)a * b % Mod;

	return a;

}



const int MN = 500005;



int Fac[MN], iFac[MN];



inline void Init(int N) {

	Fac[0] = 1;

	for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;

	iFac[N] = qPow(Fac[N], Mod - 2);

	for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;

}

inline int Binom(int N, int M) {

	if (M < 0 || M > N) return 0;

	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;

}



int N, K, Ans;



int main() {

	scanf("%d%d", &N, &K);

	if (K < N) return puts("0"), 0;

	Init(K);

	for (int R = 0; R <= K; ++R) {

		int B = K - R;

		if (R < B) continue;

		if (R == B) --B;

		Ans = ((LL)Ans + Binom(R + B, R) - Binom(R + B, 2 * R - N + 1) + Mod) % Mod;

	}

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

	return 0;

}



// Luogu : PinkRabbit

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

#define N 500005

#define ll long long

#define For(i,x,y) for(int i=(x);i<=(y);++i)

#define Rof(i,x,y) for(int i=(x);i>=(y);--i)

#define Edge(x) for(int i=head[x];i;i=e[i].nxt)

#define mset(x,y) memset(x,y,sizeof(x))

#define mod 998244353

using namespace std;

int fac[N],invf[N];

int C(int x,int y){ return x>=y?1ll*fac[x]*invf[y]%mod*invf[x-y]%mod:0; }

int main(){

	int n,k,ans=0;

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

	fac[0]=fac[1]=1,invf[0]=invf[1]=1;

	For(i,2,k){

		fac[i]=1ll*fac[i-1]*i%mod;

		invf[i]=1ll*(1ll*mod-mod/i)*invf[mod%i]%mod;

	}

	For(i,2,k) invf[i]=1ll*invf[i-1]*invf[i]%mod;

	For(i,n,k) (ans+=C(k-1,i-1))%=mod;

	cout<<ans;

}


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



typedef long long LL;

const int Mod = 998244353;



inline int qPow(int b, int e) {

	int a = 1;

	for (; e; e >>= 1, b = (LL)b * b % Mod)

		if (e & 1) a = (LL)a * b % Mod;

	return a;

}



const int MN = 500005;



int Fac[MN], iFac[MN];



inline void Init(int N) {

	Fac[0] = 1;

	for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;

	iFac[N] = qPow(Fac[N], Mod - 2);

	for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;

}

inline int Binom(int N, int M) {

	if (M < 0 || M > N) return 0;

	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;

}



int N, K, Ans;



int main() {

	scanf("%d%d", &N, &K);

	Init(K);

	for (int i = N; i <= K; ++i) Ans = (Ans + Binom(K - 1, i - 1)) % Mod;

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

	return 0;

}

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

#define LL long long

#define mod 998244353

#define M 1000005

using namespace std;

int read()

{

	char ch=getchar(); int w=1,c=0;

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;

	for (;isdigit(ch);ch=getchar()) c=(c<<3)+(c<<1)+(ch^48);

	return w*c;

}

LL f[M],inv_f[M],ans;

int n,m;

LL fast(LL x,LL p)

{

	LL res=1;

	for (;p;p>>=1,x=x*x%mod) if (p&1) res=res*x%mod;

	return res;

}

LL C(int n,int m){if (m>n) return 0;return f[n]*inv_f[m]%mod*inv_f[n-m]%mod;}

LL calc(int x,int y,int t){return C(x+y,y)-C(x+y,x+t);}

int main()

{

	n=read(); m=read();

	if(m<n) return puts("0")&0;

	f[0]=1;

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

	f[i]=f[i-1]*i%mod;

	inv_f[m+n]=fast(f[m+n],mod-2);

	for(register int i=m+n;i;--i) inv_f[i-1]=inv_f[i]*i%mod;

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

	{

		int R=i,B=m-i;

		if(R==B) ans=(ans+calc(R,B-1,R-n+1)+mod)%mod;

		if(R>B) ans=(ans+calc(R,B,R-n+1)+mod)%mod;

	}

	return printf("%lld",ans)&0;

}


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



typedef long long LL;

const int Mod = 998244353;



inline int qPow(int b, int e) {

	int a = 1;

	for (; e; e >>= 1, b = (LL)b * b % Mod)

		if (e & 1) a = (LL)a * b % Mod;

	return a;

}



const int MN = 500005;



int Fac[MN], iFac[MN];



inline void Init(int N) {

	Fac[0] = 1;

	for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;

	iFac[N] = qPow(Fac[N], Mod - 2);

	for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;

}

inline int Binom(int N, int M) {

	if (M < 0 || M > N) return 0;

	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;

}



int N, K, Ans;



int main() {

	scanf("%d%d", &N, &K);

	Init(K);

	for (int i = N; i <= K; ++i) Ans = (Ans + Binom(K - 1, i - 1)) % Mod;

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

	return 0;

}

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

using namespace std ;

int n , a , b ;

int main()

{

	cin >> n >> a >> b ;

	cout << min( n*a , b ) << "\n" ;



}

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

int main()

{

	int a, b, c;

	scanf("%d%d%d", &a, &b, &c);

	printf("%d", a*b<c?a*b:c);

}

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

using namespace std;



typedef long long ll;



const int N = 2500;

ll arr[N + 5];

ll sq[N + 5];



ll tipe[3];



int main() {

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

	int n;

	cin>>n;

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

	sort(arr, arr + n);

	for(int i = 0;i < n;i++) sq[i] = arr[i] * arr[i];

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

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

			int lo = j + 1;

			int hi = n - 1;

			int ub = -1;

			while(lo <= hi) {

				int mid = (lo + hi) / 2;

				if(arr[i] + arr[j] > arr[mid]) {

					ub = mid;

					lo = mid + 1;

				} else hi = mid - 1;

			}

			

			if(ub != -1) {

				int lo = j + 1;

				int hi = ub;

				int resL = j;

				while(lo <= hi) {

					int mid = (lo + hi) / 2;

					if(sq[i] + sq[j] > sq[mid]) {

						resL = mid;

						lo = mid + 1;

					} else hi = mid - 1;

				}

				

				lo = j + 1;

				hi = ub;

				int resH = ub + 1;

				while(lo <= hi) {

					int mid = (lo + hi) / 2;

					if(sq[i] + sq[j] < sq[mid]) {

						resH = mid;

						hi = mid - 1;

					} else lo = mid + 1;

				}

				int total = ub - j;

				int t1 = resL - j;

				int t3 = ub + 1 - resH;

				int t2 = total - t1 - t3;

//				cout<<"RESL "<<resL<<" "<<resH<<endl;

//				cout<<"AT "<<i<<" "<<j<<" "<<t1<<" "<<t2<<" "<<t3<<endl;

				tipe[0] += t1, tipe[1] += t2, tipe[2] += t3;

			}			

		}

	}

	cout<<tipe[0] + tipe[1] + tipe[2]<<endl;

}

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



void ShellSort(int arr[],int n)

{

	int incre = 1;

	while(incre < n/3)

		incre = incre*3 + 1;

	for(;incre >= 1;incre/=3)

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

		{

			int pos = i;

			int val = arr[i];

			for(;pos >= incre && val < arr[pos - incre];pos-=incre)

				arr[pos] = arr[pos - incre];

			arr[pos] = val;

		}

}



int Find(int arr[],int n)

{

    int ans = 0;

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

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

            for(int k = j + 1;k < n;k++)

            {

                if(arr[i] + arr[j] > arr[k]) ans++;

                else break;

            }

    return ans;

}  

int main()

{

    int n;

    scanf("%d",&n);

    int arr[10002];

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

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

    ShellSort(arr,n);

    printf("%d\n",Find(arr,n));

    return 0;

}


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


#include<bits/stdc++.h>

using namespace std;



int a[100001] ;



int panduan(int a,int b,int c)

{

	if(a+b>c&&b+c>a&&c+a>b) return 1;

	else return 0;

}



int main(){

	

	int n;

	scanf("%d",&n);

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

	{

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

	}

	int ans=0;

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

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

	{

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

		{

			int it=lower_bound(a+1,a+n+1,a[i]+a[j])-a-2;

			if(it-j+1>0)

			{

				ans+=it-j+1;

			}

		}

	}

	printf("%d",ans);

	return 0;

}


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



void ShellSort(int arr[],int n)

{

	int incre = 1;

	while(incre < n/3)

		incre = incre*3 + 1;

	for(;incre >= 1;incre/=3)

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

		{

			int pos = i;

			int val = arr[i];

			for(;pos >= incre && val < arr[pos - incre];pos-=incre)

				arr[pos] = arr[pos - incre];

			arr[pos] = val;

		}

}



int Find(int arr[],int n)

{

    int ans = 0;

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

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

            for(int k = j + 1;k < n;k++)

            {

                if(arr[i] + arr[j] > arr[k]) ans++;

                else break;

            }

    return ans;

}  

int main()

{

    int n;

    scanf("%d",&n);

    int arr[10002];

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

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

    ShellSort(arr,n);

    printf("%d\n",Find(arr,n));

    return 0;

}


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

#include<stdio.h>

#include<algorithm>

using namespace std;



int main()

{

	int n,j,k,a[10009],m=0;

	scanf("%d",&n);

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

	{

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

	}

	sort(a,a+n);

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

	{

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

		{

			for(k=j+1;k<n;k++)

			{

				if(a[i]<a[j]+a[k]&&a[j]<a[k]+a[i]&&a[k]<a[i]+a[j])

				{

					m++;

				}

				else

				{

					break;

				}

			}

		}

	}

	cout<<m;

	return 0;

 } 

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



void ShellSort(int arr[],int n)

{

	int incre = 1;

	while(incre < n/3)

		incre = incre*3 + 1;

	for(;incre >= 1;incre/=3)

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

		{

			int pos = i;

			int val = arr[i];

			for(;pos >= incre && val < arr[pos - incre];pos-=incre)

				arr[pos] = arr[pos - incre];

			arr[pos] = val;

		}

}



int Find(int arr[],int n)

{

    int ans = 0;

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

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

            for(int k = j + 1;k < n;k++)

            {

                if(arr[i] + arr[j] > arr[k]) ans++;

                else break;

            }

    return ans;

}  

int main()

{

    int n;

    scanf("%d",&n);

    int arr[10002];

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

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

    ShellSort(arr,n);

    printf("%d\n",Find(arr,n));

    return 0;

}


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

using namespace std;

typedef long long ll;

ll n,arr[3000],tot,ans = 0;





int main (){

	cin >> n;

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

		cin >> arr[i];

	}

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

	

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

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

			ll l = j + 1, r = n, nemu = 0;

			while(l <= r){

				ll mid = (l + r) / 2;

				if((arr[i] + arr[j]) > arr[mid]){

					nemu = mid;

					l = mid + 1;

				}else r = mid - 1;

			}

			

			if(nemu > 0) ans += nemu - j;

			//cout << nemu << " " << j << endl;

		}

	}

	

	cout << ans << endl;

}

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



void ShellSort(int arr[],int n)

{

	int incre = 1;

	while(incre < n/3)

		incre = incre*3 + 1;

	for(;incre >= 1;incre/=3)

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

		{

			int pos = i;

			int val = arr[i];

			for(;pos >= incre && val < arr[pos - incre];pos-=incre)

				arr[pos] = arr[pos - incre];

			arr[pos] = val;

		}

}



int Find(int arr[],int n)

{

    int ans = 0;

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

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

            for(int k = j + 1;k < n;k++)

            {

                if(arr[i] + arr[j] > arr[k]) ans++;

                else break;

            }

    return ans;

}  

int main()

{

    int n;

    scanf("%d",&n);

    int arr[10002];

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

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

    ShellSort(arr,n);

    printf("%d\n",Find(arr,n));

    return 0;

}


// Fastest known solution for this problem: