stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <cmath>

#include <cstdio>

#include <algorithm>



using namespace std;



int main()

{

    int n; double x[100000], y[100000];

    

    scanf("%d", &n);

    

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

    {

        scanf("%lf", &x[i]);

        scanf("%lf", &y[i]);

    }

    

    pair<double, double> p1[100000], p2[100000];

    

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

    {

        p1[i] = make_pair(x[i], y[i]);

    }

    

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

    {

        p2[i] = make_pair(y[i], x[i]);

    }

    

    sort(p1, p1 + n);

    sort(p2, p2 + n);

    

    double sqr_ans = 100000000.0;

    

    const int loops = 150;

    

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

    {

        int r = min(loops, n - i - 1);

        

        for(int j = 1; j <= r; j++)

        {

            double distance_ = (p1[i + j].first - p1[i].first) * (p1[i + j].first - p1[i].first) + (p1[i + j].second - p1[i].second) * (p1[i + j].second - p1[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

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

    {

        int r = min(loops, n - i - 1);

        

        for(int j = 1; j <= r; j++)

        {

            double distance_ = (p2[i + j].first - p2[i].first) * (p2[i + j].first - p2[i].first) + (p2[i + j].second - p2[i].second) * (p2[i + j].second - p2[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

    printf("%.15f\n", sqrt(sqr_ans));

    

    return 0;

}

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

using namespace std;

int n; double bx, by; pair<double, double> p[100009];

int main() {

	scanf("%d", &n);

	double sq = sin(1.234), cq = cos(1.234);

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

		scanf("%lf%lf", &bx, &by);

		double ex = bx * cq - by * sq;

		double ey = bx * sq + by * cq;

		p[i] = make_pair(ex, ey);

	}

	sort(p, p + n);

	double ret = 1.0e+10;

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

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

			double dx = p[i].first - p[j].first;

			if(dx * dx > ret) break;

			double dy = p[i].second - p[j].second;

			double dist = dx * dx + dy * dy;

			if(ret > dist) ret = dist;

		}

	}

	printf("%.15lf\n", sqrt(ret));

	return 0;

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

#include <cstdio>

#include <algorithm>



using namespace std;



int main()

{

    int n; double x[100000], y[100000];

    

    scanf("%d", &n);

    

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

    {

        scanf("%lf", &x[i]);

        scanf("%lf", &y[i]);

    }

    

    pair<double, double> p1[100000], p2[100000];

    

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

    {

        p1[i] = make_pair(x[i], y[i]);

    }

    

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

    {

        p2[i] = make_pair(y[i], x[i]);

    }

    

    sort(p1, p1 + n);

    sort(p2, p2 + n);

    

    double sqr_ans = 100000000.0;

    

    const int loops = 125;

    

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

    {

        int r = min(loops, n - i - 1);

        

        for(int j = 1; j <= r; j++)

        {

            double distance_ = (p1[i + j].first - p1[i].first) * (p1[i + j].first - p1[i].first) + (p1[i + j].second - p1[i].second) * (p1[i + j].second - p1[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

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

    {

        int r = min(loops, n - i - 1);

        

        for(int j = 1; j <= r; j++)

        {

            double distance_ = (p2[i + j].first - p2[i].first) * (p2[i + j].first - p2[i].first) + (p2[i + j].second - p2[i].second) * (p2[i + j].second - p2[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

    printf("%.15f\n", sqrt(sqr_ans));

    

    return 0;

}

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

using namespace std;

int n; double bx, by; pair<double, double> p[100009];

int main() {

	scanf("%d", &n);

	double sq = sin(1.234), cq = cos(1.234);

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

		scanf("%lf%lf", &bx, &by);

		double ex = bx * cq - by * sq;

		double ey = bx * sq + by * cq;

		p[i] = make_pair(ex, ey);

	}

	sort(p, p + n);

	double ret = 1.0e+10;

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

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

			double dx = p[i].first - p[j].first;

			if(dx * dx > ret) break;

			double dy = p[i].second - p[j].second;

			double dist = dx * dx + dy * dy;

			if(ret > dist) ret = dist;

		}

	}

	printf("%.15lf\n", sqrt(ret));

	return 0;

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

#include <cstdio>

#include <algorithm>



using namespace std;



int main()

{

    int n; double x[100000], y[100000];

    

    scanf("%d", &n);

    

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

    {

        scanf("%lf", &x[i]);

        scanf("%lf", &y[i]);

    }

    

    pair<double, double> p1[100000], p2[100000];

    

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

    {

        p1[i] = make_pair(x[i], y[i]);

    }

    

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

    {

        p2[i] = make_pair(y[i], x[i]);

    }

    

    sort(p1, p1 + n);

    sort(p2, p2 + n);

    

    double sqr_ans = 100000000.0;

    

    const int loops = 111;

    

    int n_1 = n - 1;

    

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

    {

        int r = min(loops, n_1 - i);

        

        for(char j = 1; j <= r; j++)

        {

            double distance_ = (p1[i + j].first - p1[i].first) * (p1[i + j].first - p1[i].first) + (p1[i + j].second - p1[i].second) * (p1[i + j].second - p1[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

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

    {

        int r = min(loops, n_1 - i);

        

        for(char j = 1; j <= r; j++)

        {

            double distance_ = (p2[i + j].first - p2[i].first) * (p2[i + j].first - p2[i].first) + (p2[i + j].second - p2[i].second) * (p2[i + j].second - p2[i].second);

        

            sqr_ans = min(distance_, sqr_ans);

        }

    }

    

    printf("%.9f\n", sqrt(sqr_ans));

    

    return 0;

}

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

using namespace std;

int n; double bx, by; pair<double, double> p[100009];

int main() {

	scanf("%d", &n);

	double sq = sin(1.234), cq = cos(1.234);

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

		scanf("%lf%lf", &bx, &by);

		double ex = bx * cq - by * sq;

		double ey = bx * sq + by * cq;

		p[i] = make_pair(ex, ey);

	}

	sort(p, p + n);

	double ret = 1.0e+10;

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

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

			double dx = p[i].first - p[j].first;

			if(dx * dx > ret) break;

			double dy = p[i].second - p[j].second;

			double dist = dx * dx + dy * dy;

			if(ret > dist) ret = dist;

		}

	}

	printf("%.15lf\n", sqrt(ret));

	return 0;

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

#include<iostream>

using namespace std;

int n;

int B,W;

int a[300050];

int s[300050];

bool judge(int x)

{

	int mn=0;

	if(s[n]>=x) return 1;

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

	{

		if(s[i-1]-mn>=x)

		{

			if(s[n]-s[i]>=x) return 1;

			mn=min(mn,s[i]);

		}

	}

	return 0;

}

int main()

{

	scanf("%d",&n);

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

	{

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

		if(i&1)

		{

			B+=a[i];

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

		}

		else

		{

			W+=a[i];

			s[i]=s[i-1]-a[i];

		}

	}

	if(~n&1)

	{

		printf("%d %d\n",max(B,W),min(B,W));

		return 0;

	}

	int l=0,r=B,re=-1;

	while(l<=r)

	{

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

		if(judge(mid)) l=mid+1,re=mid;

		else r=mid-1;

	}

	int an=max(B,W+re);

	printf("%d %d\n",an,B+W-an);

	return 0;

}

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

#include<algorithm>

using namespace std;

#define N 300060

int n,v[N];

long long su[N],su1,su2;

bool check(long long l)

{

	long long mn=0;

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

	if(su[i]-mn>=l)

	{

		if(mn>su[i+1])mn=su[i+1];

		if(i==n)return 1;

	}

	return 0;

}

int main()

{

	scanf("%d",&n);

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

	if(~n&1)

	{

		long long s1=0,s2=0;

		for(int i=1;i<=n;i+=2)s1+=v[i],s2+=v[i+1];

		printf("%lld %lld\n",max(s1,s2),min(s1,s2));

	}

	else

	{

		for(int i=1;i<=n;i++)su1+=v[i]*(i&1),su[i]=su[i-1]+v[i]*(i&1?1:-1),su2+=v[i]*(~i&1);

		long long lb=0,rb=2e10,as=0;

		while(lb<=rb)

		{

			long long mid=(lb+rb)>>1;

			if(check(mid))as=mid,lb=mid+1;

			else rb=mid-1;

		}

		printf("%lld %lld\n",su2+as,su1-as);

	}

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

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>



using namespace std;



int n;

int seq[300050];



bool chk(int mid)

{

	int val = seq[1];

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

	{

		if(val >= mid) val = max(val + seq[i + 1] - seq[i],seq[i + 1]);

		else val += seq[i + 1] - seq[i];

	}

	return val >= mid;

}



int main()

{

	scanf("%d",&n);

	int ji = 0,ou = 0;

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

	{

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

		if(i % 2) ji += seq[i];

		else ou += seq[i];

	}

	if(n % 2 == 0)

	{

		printf("%d %d\n",max(ji,ou),min(ji,ou));

	}

	else

	{

		int l = 0,r = 300000000,ans;

		while(l <= r)

		{

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

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

			else r = mid - 1;

		}

		printf("%d %d\n",ou + ans,ji - ans);

	}

}

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

#include <algorithm>

using namespace std;



const int MAXN = 300000;

const int INF = (1 << 30);



int s[2], sum[MAXN + 5], a[MAXN + 5], N;

bool check(int x) {

	int k = 0;

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

		if( sum[i-1] - k >= x )

			k = min(k, sum[i]);

	}

	return sum[N] - k >= x;

}



int main() {

	scanf("%d", &N);

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

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

	if( N % 2 == 0 )

		printf("%d %d\n", max(s[0], s[1]), min(s[0], s[1]));

	else {

		for(int i=1;i<=N;i++) sum[i] = sum[i-1] + (i & 1 ? a[i] : -a[i]);

		int le = 0, ri = s[0] + s[1];

		while( le < ri ) {

			int mid = (le + ri + 1) >> 1;

			if( check(mid) ) le = mid;

			else ri = mid - 1;

		}

		printf("%d %d\n", s[0] + le, s[1] - le);

	}

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

using namespace std;



int main(){

  int n,w[300],maxx[301][301],dp[301][301];

  cin>>n;

  while(n!=0){

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

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

        dp[i][j]=0;

        maxx[i][j]=0;

      }

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

      cin>>w[i];

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

      if(w[i]-w[i+1]>=-1&&w[i]-w[i+1]<=1)

        dp[i][i+1]=1;

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

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

        if(dp[i+1][i+k-1]==1&&w[i]-w[i+k]>=-1&&w[i]-w[i+k]<=1)

          dp[i][i+k]=1;

        else

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

            if(dp[i][j]==1&&dp[j+1][i+k]==1){

              dp[i][i+k]=1;

              break;

            }

        

      }

    

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

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

        if(dp[i][i+k]==1)

          maxx[i][i+k]=k+1;

        else

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

            if(maxx[i][i+k]<maxx[i][j]+maxx[j+1][i+k])

              maxx[i][i+k]=maxx[i][j]+maxx[j+1][i+k];

      }

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

    cin>>n;

  }

}


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

#include<algorithm>

using namespace std;

int main(){

    int n,w[300],dp[300][300];

    scanf("%d",&n);

    while(n){

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

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

        }

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

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

                dp[i][j]=0;

            }

        }

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

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

                if(dp[i+1][i+k-1]==k-1&&max(w[i],w[i+k])-min(w[i],w[i+k])<=1){

                    dp[i][i+k]=k+1;

                }

                else{

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

                        dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]);

                    }

                }

            }

        }

        printf("%d\n",dp[0][n-1]);

        scanf("%d",&n);

    }

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

#define loop for(;;)

typedef std::vector<long> LI;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }

template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }

template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }

void scan() {}

template<typename Head, typename... Tail>

void scan(Head& x, Tail&... xs) {

  scan1(x); scan(xs...);

}



struct Solver {

   long memo[314][314];

   LI xs;

   long dfs(long left, long right) {

      if( memo[left][right] != -1 ) return memo[left][right];

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

      long res = 0;

      if( std::abs(xs[right-1] - xs[left]) <= 1 ) {

         long x = dfs(left + 1, right - 1);

         if( x == (right - 1) - (left + 1) ) {

            res = std::max(res, x + 2);

         }

      }

      for(long i = left + 1; i <= right - 1; ++i) {

         res = std::max(res, dfs(left, i) + dfs(i, right));

      }

      return memo[left][right] = res;

   }

   void solve() {

      long n; scan(n);

      if( n == 0 ) exit(0);

      xs.resize(n); for(long &x : xs) scan(x);

      init();

      printf("%ld\n", dfs(0, n));

   }

   void init() {

      for(long i = 0; i < 314; ++i) {

         for(long k = 0; k < 314; ++k) {

            memo[i][k] = -1;

         }

      }

   }

};



int main() {

   loop std::shared_ptr<Solver>(new Solver())->solve();

}

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



int main() {

    for(;;) {

        int n;

        std::cin >> n;

        if (n == 0) {

            break;

        }

        std::vector<int> xs(n);

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

            std::cin >> xs[i];

        }

        int dp[310][310] = {{}};

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

            for(int l = 0; l <= n-w; ++l) {

                int r = l + w;

                // sep

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

                    dp[l][r] = std::max(dp[l][r], dp[l][k] + dp[k][r]);

                }

                // 2

                if (std::abs(xs[l] - xs[r-1]) <= 1 && dp[l+1][r-1] == r-l-2) {

                    dp[l][r] = std::max(dp[l][r], dp[l+1][r-1] + 2);

                }

            }

        }

        printf("%d\n", dp[0][n]);

    }

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



using namespace std;



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



    int n;

    while(cin>>n,n){

        vector<int> w(n);

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

        vector<vector<int> > dp(400,vector<int>(400,0));//dp[i][j]:=i~j??????????????????

        vector<vector<int> > res(400,vector<int>(400,0));

        for(int i=0;i<n-1;i++) if(abs(w[i]-w[i+1])<=1){

            dp[i][i+1]=1;

        }

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

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

                if(dp[j+1][j+i-2] && abs(w[j]-w[j+i-1])<=1){

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

                    continue;

                }

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

                    if(dp[j][j+k-1] && dp[j+k][j+i-1]){

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

                        break;

                    }

                }

            }        

        }

        for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(dp[i][j]){

            res[i][j]=j-i+1;

        }

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

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

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

                    res[i][j]=max(res[i][j],res[i][k]+res[k+1][j]);

                }

            }

        }

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

    }

}

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



using namespace std;



int main()

{

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n;

    while (cin >> n, n)

    {

        vector<int> w(n);

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

            cin >> w[i];

        vector<vector<int>> dp(n, vector<int>(n, 0));

        int ret = 0;

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

        {

            if (abs(w[i] - w[i + 1]) <= 1)

            {

                dp[i][i + 1] = 2;

                ret = 2;

            }

        }

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

        {

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

            {

                if (dp[j + 1][j + i - 2] == i - 2 && abs(w[j] - w[j + i - 1]) <= 1)

                {

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

                    ret = i;

                }

                else

                {

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

                    {

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

                    }

                    ret = max(ret, dp[j][j + i - 1]);

                }

            }

        }

        cout << ret << endl;

    }

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

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

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

#define INF (1ll<<58)



	

int main(){

	long long n,m;

	while(cin >> n >> m && n){

		long long land[200][200] , ship[200][200] ;

		rep(i,200)rep(j,200)land[i][j] = ship[i][j] = INF;

		rep(i,200)land[i][i] = ship[i][i] = 0;

		

		rep(i,m){

			string l;

			long long a,b,c; cin >> a >> b >> c >> l;

			a--,b--;

			if(l=="L")land[a][b] = land[b][a] = min(c,land[a][b]);

			else      ship[a][b] = ship[b][a] = min(c,ship[a][b]);

		}

		rep(k,n)rep(i,n)rep(j,n)land[i][j] = min(land[i][j],land[i][k]+land[k][j]);

		rep(k,n)rep(i,n)rep(j,n)ship[i][j] = min(ship[i][j],ship[i][k]+ship[k][j]);

		

		long long r; cin >> r;

		long long R[1000];	

		rep(i,r)cin >> R[i] , R[i]--;

		

		long long dp[2][200];

		rep(j,2)rep(k,200)dp[j][k] = INF;

		dp[0][R[0]] = 0;

		

		rep(bit,r-1){

			rep(cur,n){

				rep(next,n){

					long long newCost = dp[bit%2][cur] + land[R[bit]][cur] + ship[cur][next] + land[next][R[bit+1]];

					dp[(bit+1)%2][next] = min( dp[(bit+1)%2][next],newCost);

				}

				dp[(bit+1)%2][cur] = min(dp[(bit+1)%2][cur],dp[bit%2][cur]+land[R[bit]][R[bit+1]]);

			}

			rep(j,200)dp[bit%2][j] = INF;

		}

		long long ret = INF;

		rep(i,n){

			ret = min(dp[(r-1)%2][i],ret);

		}

		cout << ret << endl;

		

	}

}

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

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

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

#define INF 100000000



	

int main(){

	int n,m;

	while(cin >> n >> m && n){

		int land[200][200] , ship[200][200] ;

		rep(i,200)rep(j,200)land[i][j] = ship[i][j] = INF;

		rep(i,200)land[i][i] = ship[i][i] = 0;

		

		rep(i,m){

			string l;

			int a,b,c; cin >> a >> b >> c >> l;

			a--,b--;

			if(l=="L")land[a][b] = land[b][a] = min(c,land[a][b]);

			else      ship[a][b] = ship[b][a] = min(c,ship[a][b]);

		}

		rep(k,n)rep(i,n)rep(j,n)land[i][j] = min(land[i][j],land[i][k]+land[k][j]);

		rep(k,n)rep(i,n)rep(j,n)ship[i][j] = min(ship[i][j],ship[i][k]+ship[k][j]);

		

		int r; cin >> r;

		int R[1000];	

		rep(i,r)cin >> R[i] , R[i]--;

		

		int dp[2][200];

		rep(j,2)rep(k,200)dp[j][k] = INF;

		dp[0][R[0]] = 0;

		

		rep(bit,r-1){

			rep(cur,n){

				rep(next,n){

					int newCost = dp[bit%2][cur] + land[R[bit]][cur] + ship[cur][next] + land[next][R[bit+1]];

					dp[(bit+1)%2][next] = min( dp[(bit+1)%2][next],newCost);

				}

				dp[(bit+1)%2][cur] = min(dp[(bit+1)%2][cur],dp[bit%2][cur]+land[R[bit]][R[bit+1]]);

			}

			rep(j,200)dp[bit%2][j] = INF;

		}

		int ret = INF;

		rep(i,n){

			ret = min(dp[(r-1)%2][i],ret);

		}

		cout << ret << endl;

		

	}

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

#include<string.h>

#include<math.h>

#include<iostream>

#include<string>

#include<sstream>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<vector>

#define ll  long long 

using namespace std;

ll a[100005], f[100005] = {1}, mod = 1000000007, n, k;

ll quick_pow(ll a, ll b, ll mod)

{

	ll ans = 1;

	while (b)

	{

		if (b & 1)	ans = ans * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return ans;

}

ll vim(ll a, ll b)

{

	return quick_pow(a, b - 2, b);

}

inline ll C(ll a, ll b)

{

	return f[b] * vim(f[a], mod) % mod * vim(f[b - a], mod) % mod;

}

ll solve()

{

	ll mx = 0, mn = 0;

	sort(a, a + n);

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

		mx = (mx + C(k - 1, i) * a[i]) % mod;

	for (int i = n - 1, j = 0; i >= k - 1; i--, j++)

		mn = (mn + C(k - 1, i) * a[j]) % mod;

	return ((mx - mn) % mod + mod) % mod;

}

signed main()

{

	for (int i = 1; i <= 100000; i++)	f[i] = f[i - 1] * i % mod;

	//cout << vim(1, mod) << endl;

	while (~scanf("%lld%lld", &n, &k))

	{

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

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

	}

}


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

#include<algorithm>

#include<vector>

using namespace std ;

typedef long long ll ;

const ll maxx = 1e5+5,mod=1e9+7 ;

ll fact[maxx];

ll power(ll b,ll p,ll m)

{

    if(p==0){return 1;}

    //if(p==1){return b;}

    ll half = power(b,p/2,m);

    ll ans,full=(half*half)%m;

    if(p%2==0)

    {

        return full;

    }

    else { return  (full*b)%m ;}

}

ll mulv(ll b,ll p)

{

    // since p is prime ;

    // b*x=1 mod p , p is prime so gcd(p,b)=1

    ll x  = power(b,p-2,p);

    return x ;

}

ll ncr(ll n,ll r)

{

    //cout << n << "  " << r << endl;

    if(n<r){return 0;}

    if(r==0 || n==r){return 1;}

    if(r==1 ){return n%mod;}

    ll a,b,c;

    a = fact[n];

    b = mulv(fact[n-r],mod);

    c = mulv(fact[r],mod);

    ll ans = (a*b)%mod;

    ans = (ans*c)%mod;

    return ans ;

}

int main()

{

    fact[0]=1;

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

    {

       fact[i]=(fact[i-1]*i)%mod;

    }

    ll n , k ;

    cin >> n >> k ;

    ll arr[n+5];

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

    {

       ll  x ;

       cin >> x ;

       arr[i-1]=x;

    }

    sort(arr,arr+n,greater<ll>());

    ll sum=0,sum1=0,sum2=0;

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

    {

        sum1+= (arr[i]*ncr(n-i-1,k-1))%mod ;



        sum2+= (arr[i]*ncr(i,k-1))%mod ;

    }

    sum=sum1-sum2;

    cout << sum%mod << endl;

    return 0 ;

}