akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n;
    cin >> n;
    int ma = 0;
    int ans = 0;
    rep(i,n){
        int in;
        cin >> in;
        if(ma <= in){
            ans++;
            ma = in;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 764
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
char s[100001];
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=1;i<=a+b+1;i++) cin>>s[i];
    for(int i=1;i<=a+b+1;i++)
    {
        if(s[i]<48&&i!=a+1||s[i]>58&&i!=a+1)
        {
            cout<<"No"<<endl;
            return 0;
        }
        if(i==a+1&&s[i]!='-')
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(a) a.begin(), a.end()
typedef long long ll;
#define MOD 1000000007
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N,M,X; cin>>N>>M>>X;
  vector<ll> C(N);
  vector<vector<ll>> A(N, vector<ll>(M));
  rep(i,N) {
    cin>>C[i];
    rep(j,M) {
      cin>>A[i][j];
    }
  }

  ll res = 1000000000;
  for(int bit = 0; bit < (1<<N); ++bit) {
    vector<ll> arr(M);
    ll sum = 0;
    for (int i = 0; i < N; ++i) {
      if (bit & (1 << i)) {
        rep(j, M)arr[j] += A[i][j];
        sum += C[i];
      }
    }
    bool can = true;
    rep(i,M) {
      if(arr[i]<X){can = false; break;}
    }
    if(can)res = min(res, sum);
  }
  if(res==1000000000)cout<<-1<<endl;
  else cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 3660
import sys
input = sys.stdin.readline

N=int(input())
h = list(map(int, input().split()))
INF = N*1e+4
dp = [INF]*N
dp[0]=0
for i in range(1,N):
    dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
    if i-2 >= 0:
        dp[i] = min(dp[i],dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])


Measured memory_bytes: 51772
#include <bits/stdc++.h>
	using namespace std;

	int main(){
		
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
	
		// #ifndef ONLINE_JUDGE
		// freopen("input.txt", "r", stdin);
		// freopen("output.txt", "w", stdout);
		// #endif

		// int n,W;
		// cin >> n >> W;
		// long long int w[n+1],v[n+1],dp[n+1][10000];
		// for(int i=0;i<n;i++){
		// 	cin >> w[i+1] >> v[i+1];
		// }
		// memset(dp,0,sizeof(dp));
		// for(int i=1;i<=n;i++){
		// 	for(int j=0;j<=W;j++){
		// 		dp[i][j]=dp[i-1][j];
		// 		if(j>=w[i]){
		// 			dp[i][j]=max(dp[i][j],v[i]+dp[i-1][j-w[i]]);
		// 		}
		// 	}
		// }
		// cout << dp[n][W];
		
		int n,k;
		cin >> n >> k;
		int a[n],dp[k+1];
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++) cin >> a[i];
		
		for(int i=1;i<=k;i++){
			int f=0;
			for(int j=0;j<n;j++){
				if(i>=a[j] && !dp[i-a[j]]){
					f=1;break;
				}
			}
			if(f) dp[i]=1;
		}
		if(dp[k]) cout << "First";
		else cout << "Second";


	
	
		
	
	}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  int n,k,i,j;
  int ban[10]={};
  int a;
  cin>>n>>k;

  rep(i,k){
    scanf(" %d",&a);
    ban[a]=1;
  }
  while(1){
    int price=n;
    while(2){
      if(ban[price%10])break;
      if(price/10==0){
	cout<<n<<endl;
	return 0;
      }
      price/=10;
    }
    n++;
  }

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try (Scanner sc = new Scanner(System.in)) {
			char[] n = sc.next().toCharArray();
			String ans = "a";

			if (Character.isUpperCase(n[0])) {

				ans = "A";
			}
			System.out.println(ans);


		} catch (Exception e) {
			// TODO: handle exception
		}
	}
}


Measured memory_bytes: 35756
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  if(N%2==0){
    cout << "0.5"<<endl;
  }
  else{
    double k;
    k=N/2 +1;
    cout << k/N<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    double A,B,X;cin>>A>>B>>X;
    double S=X/A;
  
  if(A*A*B==X){
    cout<<1.130863886742583809729988e-14<<endl;
    return 0;
  }
    
    double left=0.0,right=M_PI/2.0;
    
    for(int i=0;i<300;i++){
        double mid=(left+right)/2.0;
        double l=A*sin(mid),h=B*sin(M_PI/2.0-mid);
        double size;
        
        if(l<=h){
            size=A*B-A*A*tan(mid)/2.0;
        }else{
            size=B*B*tan(M_PI/2.0-mid)/2.0;
        }
        
        if(size>=S) left=mid;
        else right=mid;
    }
    
    printf("%.12lf\n",left*90.0/(M_PI/2.0));
    //cout<<setprecision(25)<<left*90.0/(M_PI/2.0)<<endl;
}




Measured memory_bytes: 512
/************************************
/ AUTHOR : YATHARTH GOSWAMI         /  
/ ALIAS : hacker_yg                 /
/ INSTITUTE : IIT Kanpur            /
************************************/
//          TEMPLATE                //

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;

int main(){
    int n;
    scanf ("%d\n", &n);
    map <string, int> m;
    int ans = 0;
    for (int i = 0; i < n; i++){
        string s;
        getline(cin, s);
        if (!m[s]) ans++;
        m[s]++;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 19304
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll n,m;
        cin>>n>>m;
        ll h[n+1];
        rep(i,1,n+1)cin>>h[i];
        vi adj[N];
        rep(i,0,m)
        {
            ll x,y;
            cin>>x>>y;
            adj[x].pb(y);
            adj[y].pb(x);
        }        
        ll ans=0;
        rep(i,1,n+1)
        {
            bool f=1;
            for(auto u:adj[i])
            {
                if(h[u]>=h[i])
                    {f=0;break;}
            }
            if(f)
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 10244
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
#include<iomanip>
#include<queue>

using namespace std;
using ll = long long;
using ull = unsigned long long;
ll amari = 1000000007;
#define rep(n,x) for(ll i=0;i<n;i++) cin>>x[i];
#define forr(a,b) for(ll i=a;i<b;i++);
ll modpow(ll a, ll n, ll mod)
{
	ll res = 1;
	while (0 < n)
	{
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
ll gcd(ll x, ll y)
{
	if (x % y == 0) return y;
	else return gcd(y, x % y);
}
// 1or素数だと１を返す
ll prime(ll x)
{
	for (ll i = 2; i * i <= x; i++)
	{
		if (x % i == 0) return 0;
	}
	return 1;
}



int main()
{
	ll n;
	cin >> n;
	ll k = n;
	ll x = sqrt(n);
	vector<ll> a(x+10, 0);

	for (ll i = 2; i < x + 5; i++)
	{
		while (k % i == 0)
		{
			a[i]++;
			k /= i;
		}
	}


	ll ans = 0;
	ll y = 0;
	for (ll i = 0; i < x+5; i++)
	{
		if (a[i] != 0)
		{
			y = 0;
			while (y * (y + 1) <= 2 * a[i])
			{
				y++;
			}
			y--;
			ans += y;
		}
	}
	if(k!=1) ans++;
	cout << ans << "\n";
  
	return 0;
}

Measured memory_bytes: 11080
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int p[1005][1005],n,m,a,b;

int main()
{
	n=read(); m=read(); a=read(); b=read();
	rep(i,1,b) rep(j,1,a) p[i][j]=1;
	rep(i,b+1,n) rep(j,a+1,m) p[i][j]=1;
	rep(i,1,n)
	{
		rep(j,1,m) printf("%d",p[i][j]);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 7696
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
int n,L;
int ar[100005];
int nxt[20][100005];
int main(){
  cin>>n;
  REP(i,n) cin>>ar[i];
  cin>>L;

  REP(i,n){
    nxt[0][i]=upper_bound(ar,ar+n,ar[i]+L)-ar;
    --nxt[0][i];
  }
  nxt[0][n]=n;
  REP(j,19) REP(i,n){
    nxt[j+1][i]=nxt[j][nxt[j][i]];
  }
  int q;cin>>q;
  REP(_,q){
    int a,b;cin>>a>>b;--a;--b;
    int res=0;
    if(a>b) swap(a,b);
    for(int i=19;i>=0;--i) if(nxt[i][a]<b){
      a=nxt[i][a];
      res+=(1<<i);
    }
    if(a<b) ++res;
    cout<<res<<endl;
  }

  return 0;
}





Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;  
  vector<int> seq(N);
    for(int i = 0;i<N;i++){
        cin >> seq.at(i);
    }
  int count = 1;
  int min = seq.at(0);
  for(int i=1;i<N;i++){
    if(seq.at(i) < min){
      count++;
      min = seq.at(i);
    }
  }
     cout << count << endl;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;

int main() { 
    unsigned long long N, A, B;
    cin >> N >> A >> B;
    unsigned long long ans = A * (N / (A + B));
    if (N % (A + B) > A) {
      ans = ans + A;
    } else {
      ans = ans + N % (A + B);
    }
    cout << ans << endl;
    return 0; 
}

Measured memory_bytes: 256
#include<stdio.h>
char c;int f;int nextInt();int H, W, N, X, Y, low[200001], p, i;int MAX = 524288;int main(void){H=nextInt();W=nextInt();N=nextInt();for(i=2; i<=H; i++){low[i]=MAX;}for(i=0; i<N; i++){X=nextInt();Y=nextInt();if(Y<low[X]){low[X]=Y;}}for(i=2; i<=H; i++){if(low[i]+p==i){p++;}else if(low[i]+p<i){printf("%d\n", i-1);return 0;}}printf("%d\n", H);return 0;}int nextInt(){f=0;c = getchar();while((c<'0')||('9'<c)){c=getchar();}while((c>='0')&&(c<='9')){f=f*10+(c-'0');c=getchar();}return f;}


Measured memory_bytes: 896
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int [][] numbers = new int[r+1][c+1];
        
        for(int i = 0 ; i < r ; i++ ){
            for(int j = 0 ; j < c ; j++ ){
                numbers[i][j] = sc.nextInt();
                numbers[i][c] += numbers[i][j];
                numbers[r][j] += numbers[i][j];
                numbers[r][c] += numbers[i][j];
            }
        }
        
        for(int i = 0 ; i < r + 1 ; i++){
            for(int j = 0 ; j < c + 1 ; j++){
                if(j == 0){
                    System.out.print(numbers[i][j]);
                } else {
                    System.out.print(" " + numbers[i][j] );
                }
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 41232
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

signed main(){
	ll a,b;cin>>a>>b;
	ll c=b-a;
	cout<<(1+c)*c/2-b<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
LL k,a,b; 
int main()
{
	k=io;a=io;b=io;
	if(b-a>2){
		if(k>=a-1+2){
			LL t=(k-(a-1));
			printf("%lld",t/2*(b-a)+(t&1)+a);	
		}
		else{
			printf("%lld",k+1);
		}
	}
	else{
		printf("%lld",k+1);	
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> v;

int main(){
    double A, B;
    static const double pi = 3.141592653589793;
    ll  H, M;
    cin >> A >> B >> H >> M;

    double arc , ans;
    if(30 * H >= 5.5 * M){
        arc = min(30 * H - 5.5 * M, 360 - 30 * H + 5.5 * M ) / 180;
    }else{
        arc = min(5.5 * M - 30 * H ,360 - 5.5 * M + 30 * H) /180;
    }
    
    ans = sqrt(A * A + B * B - 2 * A * B * cos(arc * pi));

    cout << setprecision(20) << ans << endl;
}


Measured memory_bytes: 4192
def resolve():
    n, a, b, c, d = list(map(int, input().split()))
    s = input()
    if "##" in s[a - 1:c] or "##" in s[b - 1:d]:
        print("No")
        return 0

    if c < d:
        print("Yes")
    else:
        if "..." in s[b - 2:d + 1]:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3572
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

#define X first
#define Y second

int a, b;

pair<int, int> calc(int d) {
	int x = 0, y = 0, diff = 0;

	while(diff != d) {
		const int ad = abs(diff + a - d), bd = abs(diff - b - d);
		if(ad > bd) {
			diff -= b;
			++y;
		}
		else {
			diff += a;
			++x;
		}
	}

	return make_pair(x, y);
}

void chans(pair<int, int>& p, const pair<int, int>& q) {
	const int p_sum = p.X + p.Y, q_sum = q.X + q.Y;
	if(p_sum > q_sum || (p_sum == q_sum && p.X * a + p.Y * b > q.X * a + q.Y * b))
		p = q;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	for(int d; cin >> a >> b >> d, a | b | d;) {
		int g = __gcd(a, b);
		a /= g;
		b /= g;
		d /= g;

		pair<int, int> ans = calc(d);
		chans(ans, calc(-d));

		if(d % a == 0)
			chans(ans, make_pair(d / a, 0));

		if(d % b == 0)
			chans(ans, make_pair(0, d / b));

		for(int x = 1; a * x < d; ++x) {
			const int rest = d - a * x;
			if(rest % b == 0)
				chans(ans, make_pair(x, rest / b));
		}

		cout << ans.X << " " << ans.Y << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1192
fun main(args: Array<String>) {
    val (H, W) = readLine()!!.split(" ").map { it.toInt() }
    val c = mutableListOf<IntArray>()
    (0..9).forEach {
        val ci = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
        c.add(ci)
    }

    for (i in 0..9) {
        for (j in 0..9) {
            for (k in 0..9) {
                c[j][k] = Math.min(c[j][k], c[j][i] + c[i][k])
            }
        }
    }

    var ans = 0
    for (i in 0 until H) {
        readLine()!!.split(" ").map { it.toInt() }.forEach {num ->
            if (num >= 0) ans += c[num][1]
        }
    }
    println(ans)
}


Measured memory_bytes: 40864
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    int n, h, w;
    cin >> n >> h >> w;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i + h <= n && j + w <= n) {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

 

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);
const long double EPS = 1e-14L;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	long double a,b,c;
	cin >> a >> b >> c;
	cout << ((sqrt(a)+sqrt(b)+EPS<sqrt(c))?"Yes":"No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

#define PI acos(-1)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define io  ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define file freopen ("team.in", "r", stdin),freopen ("team.out", "w", stdout);
#define fileIn freopen ("in.txt", "r", stdin);
#define all(v) ((v).begin()), ((v).end())


using namespace std;

typedef pair<int, int> pii;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;

const int N = 1e5 + 10;

int a[N];
ll sum[N], d[N];
int n, m;

void add(int L, int R, int c, int k) {

  if(L > R) {
    return;
  }
  //add

  sum[L] += c;
  sum[R + 1] -= c + (R - L) * 1LL * k;

  d[L] += k;
  d[R] -= k;
}

void calc() {
  for(int i = 1; i <= m; i++) {
    sum[i] += sum[i - 1];
    d[i] += d[i - 1];
  }
  ll cur = 0;
  for(int i = 1; i <= m; i++) {
    sum[i] += cur;
    cur += d[i];
  }
}

void print(ll *a) {

  for(int i = 1; i <= m; i++) {
    cout << a[i] << " ";
  }
  cout << endl << endl;
}

int main () {
#ifndef ONLINE_JUDGE
  //fileIn;
#endif
  io;
  cin >> n >> m;

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

  //L, R, c, k

  for(int i = 0; i < n - 1; i++) {
    int from = a[i];
    int to = a[i + 1];
    int dist = (to - from + m) % m;
    if(from < to) {
      add(from, from, dist, 0);
      add(from + 1, to, dist, -1);
      add(1, from - 1, dist, 0);
      add(to + 1, m, dist, 0);
    }
    if(to < from) {
      add(from, from, dist, 0);
      add(from + 1, m, dist, -1);
      add(1, to, to, -1);
      add(to + 1, from - 1, dist, 0);
    }
  }
  calc();

  ll best = sum[1];
  for(int i = 1; i <= m; i++) {
    if(sum[i] < best) {
      best = sum[i];
    }
  }
  cout << best << endl;
  return 0;
}







Measured memory_bytes: 2176
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, M = map(int, input().split())

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

ans = N
uni = UnionFind(N + 1)
for _ in range(M):
    x, y, z = map(int, input().split())
    if uni.same(x, y):
        continue
    uni.connect(x, y)
    ans -= 1

print (ans)

Measured memory_bytes: 5424
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
	sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
ll n,a,b;
void MAIN() {
	cin>>n>>a>>b;
	ll ans=9e18;
	if((b-a)%2) {
		chmin(ans,a+(b-a-1)/2);
		chmin(ans,n-b+1+(n-(a+n-b+1))/2);
	} else {
		chmin(ans,(b-a)/2);
	}
	cout<<ans;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	//cin>>T;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def solve(SOLVE_PARAMS):
    pass


def main():
    global parent, rank
    # parse input
    N, M = map(int, input().split())
    parent = [-1] * N
    rank = [0] * N
    for q in range(M):
        a, b = map(int, input().split())
        unite(a - 1, b - 1)

    xs = list(find_root(x) for x in range(N))
    # debug(": xs", xs)
    # print(len(set(xs)))
    from collections import Counter
    print(max(Counter(xs).values()))


# tests
T1 = """
5 3
1 2
3 4
5 1
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
4
"""

T3 = """
10 4
3 1
4 1
5 9
2 6
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
3
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()


Measured memory_bytes: 113780
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

int b = 1007, mo = 1e9+7;
VI g[100010];
map<int,int> v;
// 部分木xのハッシュを返す
int func(int x, int p) {
  int ret = b;
  for(int e: g[x]) {
    if(e == p) continue;
    (ret += func(e, x) * b % mo) %= mo;
  }
  v[ret]++;
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b; a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }

  mo = 1e9+7;
  b = rand() % mo;
  v.clear();
  func(0, -1);

  int ret = 0;
  for(auto i: v) ret += i.second*(i.second-1)/2;
  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 21132
#include<iostream>
using namespace std;

int main(void)
{
  int wa;
  cin>>wa;

  int a=0;
  if(wa==10||wa==100||wa==1000||wa==10000||wa==100000)
  {
    cout<<10;
  }
  else
  {
  while(wa>0)
  {
    a+=wa%10;
    wa/=10;
  }
  cout<<a;
  }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define RREP(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll K, N;
  cin >> K >> N;
  vector<ll> A(N);
  REP(i,N) cin >> A[i];
  ll dist = (K - A[N-1]) + A[0];
  REP(i,N-1){
    ll tmp = dist;
    dist = max(tmp,A[i+1] - A[i]);
  }
  cout << K- dist;
  
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int x; cin >> x;
    if(x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
	int N, K, Q;

	cin >> N >> K >> Q;

	int A[Q + 1];

	for (int i = 1; i <= Q; i++)
	{
		cin >> A[i];
	}

	int player[N + 1] = {0};

	for (int i = 1; i <= Q; i++)
	{
		int buf = A[i];
		player[buf]++;
	}

	for (int i = 1; i <= N; i++)
	{
		if (K - Q + player[i] > 0)
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 1408
#include<iostream>
#include<string>
using namespace std;
int main(){
  string a,b;
  cin>>a>>b;
  string ans="EQUAL";
  if(a.size()>b.size())ans="GREATER";
  else if(a.size()<b.size())ans="LESS";
  else{
    for(int i=a.size()-1;i>=0;i--){
      if(a[i]>b[i])ans="GREATER";
      else if(a[i]<b[i])ans="LESS";
      else continue;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x,y;
    cin >> x >> y;
    cout << x+ y/2;

    return 0;
}

Measured memory_bytes: 256
a = input().split()
N = int(a[0])
K = int(a[1])
list = []
price = 0
b = input().split()
for i in range(len(b)):
    list.append(int(b[i]))
list = sorted(list)
for i in range(K):
    price+= list[i]
print(price)

Measured memory_bytes: 9284
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	int n,m,k,l=-100004;
	n=a+b;
	m=a-b;
	k=a*b;
	l=max(n,l);
	l=max(m,l);
	l=max(k,l);
	printf("%d\n",l);
	return 0;
 } 

Measured memory_bytes: 256
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R ll y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
    return res;
}
int kkk(R int x,R ll y){
	R int res=1,d=1;
	for(;y;y>>=1,d=mul(x+1,d),x=mul(x,x))(y&1)?res=add(mul(res,x),d):0;
	return res;
}
const int N=1005;
char mp[N][N],t[N][N];int n,m,sz,p,ss,res;ll k;
inline int ck1(){R int res=0;fp(i,1,n)res+=(mp[i][1]=='#'&&mp[i][m]=='#');return res;}
inline int ck2(){R int res=0;fp(j,1,m)res+=(mp[1][j]=='#'&&mp[n][j]=='#');return res;}
int main(){
	scanf("%d%d%lld",&n,&m,&k);
	if(k<=1)return puts("1"),0;
	--k;
	fp(i,1,n)scanf("%s",mp[i]+1);
	fp(i,1,n)fp(j,1,m)sz+=mp[i][j]=='#';
	int sz1=ck1(),sz2=ck2();
	if(sz1&&sz2)return puts("1"),0;
	if(!sz1&&!sz2)return printf("%d\n",ksm(sz,k)),0;
	if(sz2){
		fp(i,1,n)fp(j,1,m)t[j][i]=mp[i][j];
		swap(n,m);
		fp(i,1,n)fp(j,1,m)mp[i][j]=t[i][j];
		swap(sz1,sz2);
	}
	fp(i,1,n)fp(j,1,m-1)ss+=(mp[i][j]=='#'&&mp[i][j+1]=='#');
//	printf("%d %d %d\n",sz,ss,sz1);
	res=mul(ksm(sz,k-1),kkk(mul(sz1,ksm(sz,P-2)),k-1));
	res=dec(ksm(sz,k),mul(ss,res));
	printf("%d\n",res); 
	return 0;
}

Measured memory_bytes: 2304
#include <iostream>
using namespace std;

int main(){
	int x,y;
	cin >> x >> y;
	while(!(x==0&&y==0)){
		if(x<y) cout << x << " " << y << endl;
		else cout << y << " " << x << endl;
		cin >> x >> y;
	}
	return 0;
}


Measured memory_bytes: 3004
#include <bits/stdc++.h>

const int MAXN = 20;
int dp[MAXN + 1][1 << MAXN + 1];
int n, K;
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> K;
	for (int i = 0; i <= n; ++i) {
		static char buf[1 << MAXN | 10];
		std::cin >> buf;
		const int U = 1 << i;
		for (int j = 0; j != U; ++j) dp[i][U + j] = buf[j] & 1;
	}
	static auto len = [] (int x) { return std::__lg(x); };
	static auto output = [] (int x) {
		int l = len(x);
		for (int i = l - 1; i >= 0; --i)
			std::cout << (x >> i & 1);
		return ;
	} ;
	static auto fn0 = [] (int x, int l) {
		const int mask = (1 << l) - 1;
		x = ~x;
		if (!(x & mask)) return 0;
		int b = __builtin_ctz(x); x >>= b;
		return (~x & mask) | 1 << l - b;
	} ;
	static auto fn1 = [] (int x, int l) {
		if (!x) return 0;
		int b = __builtin_ctz(x); x >>= b;
		return x | 1 << l - b;
	} ;
	for (int i = n; i; --i) {
		for (int j = i; j <= n; ++j) {
			const int U = 1 << j;
			const int l = j - i;
			for (int k = 0; k != U; ++k) if (int t = dp[i][k + U]) {
				int d = k & (1 << l) - 1, u = k >> l;
				dp[0][d | (1 << l)] += t;
				if (int x = fn0(u, i) >> 1)
					dp[len(x)][d | x << l + 1] += t;
				if (int x = fn1(u, i) >> 1)
					dp[len(x)][d | 1 << l | x << l + 1] += t;
			}
		}
	}
	for (int i = n; i; --i)
		for (int j = 0, U = 1 << i; j != U; ++j)
			if (dp[0][j + U] >= K)
				return output(j + U), 0;
	return 0;
}


Measured memory_bytes: 171264
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
#define MOD 1000000007 // prime
const int SIZE = 100100;
ll inv[SIZE+10],fac[SIZE+10],facinv[SIZE+10];
ll Pow[1010],kai[210];
ll val[210];
ll nCr(int n,int r)
{
	if(n<r)return -1;
	if(n<0||r<0)return -1;
	return ((fac[n]*facinv[r]%MOD)*facinv[n-r])%MOD;
}
ll func(int n)
{
	ll ret = 0ll;
	for(int i=0;i<=n;i++)ret = (ret+(nCr(n,i)*kai[i])%MOD)%MOD;
	return ret;
}
void init()
{
	fac[0]=1ll;
	for(int i=1;i<=SIZE;i++)fac[i]=(fac[i-1]*i)%MOD;
	inv[1]=1ll;
	for(int i=2;i<=SIZE;i++)inv[i]=((-(MOD/i)*inv[MOD%i])%MOD+MOD)%MOD;
	facinv[0]=1ll;
	for(int i=1;i<=SIZE;i++)facinv[i]=(facinv[i-1]*inv[i])%MOD;
	Pow[0]=1ll;
	for(int i=0;i<1000;i++)Pow[i+1]=(Pow[i]*10ll)%MOD;
	kai[0]=1ll;
	for(int i=1;i<=200;i++)kai[i]=(kai[i-1]*i)%MOD;
	for(int i=0;i<=200;i++)val[i]=func(i);
}
int cnt_digit(ll x)
{
	if(x==0ll)return 1;
	int ret = 0;
	while(x){ret++;x/=10ll;}
	return ret;
}
ll dp[210][1010];
int n;
ll a[210];
int dig[210];
ll digit_sum[5];
int del[5];
int zero=-1;
int N;
void culc_dp(int unuse)
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1ll;
	for(int i=0;i<N;i++)
	{
		if(i==unuse)continue;
		for(int j=i;j>=0;j--)
		{
			for(int k=0;k<=j*4;k++)
			{
				if(dp[j][k]==0)continue;
				dp[j+1][k+dig[i]]+=dp[j][k];
				dp[j+1][k+dig[i]]%=MOD;
			}
		}
	}
}
ll solve()
{
	ll ans = 0ll;
	for(int d=1;d<=4;d++)
	{
		if(del[d]==-1)continue;
		culc_dp(del[d]);
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<=4*N;j++)
			{
				if(dp[i][j]==0)continue;
				ans += (((((((val[N-i-1]*kai[i])%MOD)*digit_sum[d])%MOD)*dp[i][j])%MOD)*Pow[j])%MOD;
				ans %= MOD;
			}
		}
	}
	return ans;
}

int main()
{
	init();
	memset(del,-1,sizeof(del));
	scanf("%d",&n);
	N=n;
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	for(int i=0;i<n;i++)
	{
		dig[i]=cnt_digit(a[i]);
		digit_sum[dig[i]]+=a[i];
		del[dig[i]]=i;
		if(a[i]==0)zero=i;
	}
	ll ans = solve();
	//cout << solve() << ' ';
	if(zero!=-1)
	{
		swap(a[zero],a[n-1]);
		N--;
		memset(del,-1,sizeof(del));
		memset(digit_sum,0,sizeof(digit_sum));
		for(int i=0;i<N;i++)
		{
			dig[i]=cnt_digit(a[i]);
			digit_sum[dig[i]]+=a[i];
			del[dig[i]]=i;
		}
		ans -= solve();
		//cout << solve() << endl;
		ans = ((ans%MOD)+MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 5216
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(),x.end()
#define ln '\n'
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<MOD>;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<int> x(N),y(M);
    rep(i,N) cin >> x[i];
    rep(i,M) cin >> y[i];

    mint H = 0, W = 0;
    rep(i,N-1) {
        mint h = x[i+1] - x[i];
        H += h*(i+1)*(N-1-i);
    }
    rep(i,M-1) {
        mint w = y[i+1] - y[i];
        W += w*(i+1)*(M-1-i);
    }

    cout << (H*W).a << ln;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#include <numeric>
#define INF INT_MAX
using namespace std;
int dx[5]={1,0,-1,0,0},dy[5]={0,1,0,-1,0};
long long gcd(long long a,long long b){if(a%b==0){return b;}else return gcd(b,a%b);}
long long lcm(long long a,long long b){if(a==0){return b;} return a/gcd(a,b)*b;}
#define MOD 1000000007
#define sym cout<<"---------"<<endl;
#define ll long long
#define PL pair<long long, long long>
#define mk make_pair
#define en endl
#define WHITE 1
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll
#define P pair<int,int>

int ans_a=0,ans_b=0;

signed main(){
  int n; cin>>n;
  for(int i=0; i<n; i++){
    int a,b; cin>>a>>b;
    if(i==0){
      ans_a=a; ans_b=b;
      continue;
    }
    if(a==b){
      if(ans_a>ans_b) ans_b=ans_a;
      else if(ans_b>ans_a) ans_a=ans_b;
    }else if(a<b){
      if(floor(ans_a/a*b)<ans_b){
        for(int i=ans_b; i<=ans_b+1001; i++){
          if(i%b) continue;
          ans_b=i;
          ans_a=ans_b/b*a;
          break;
        }
        continue;
      }
      for(int i=ans_a; i<=ans_a+1001; i++){
        if(i%a) continue;
        ans_a=i;
        ans_b=ans_a/a*b;
        break;
      }
    }else{
      if(floor(ans_b/b*a)<ans_a){
        for(int i=ans_a; i<=ans_a+1001; i++){
          if(i%a) continue;
          ans_a=i;
          ans_b=ans_a/a*b;
          break;
        }
        continue;
      }
      for(int i=ans_b; i<=ans_b+1001; i++){
        if(i%b) continue;
        ans_b=i;
        ans_a=ans_b/b*a;
        break;
      }
    }
  }
  cout<<ans_b+ans_a<<en;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

char op(int x) {
  return x > 0 ? '+' : '-';
}

int main() {
  char s[4];
  int a[4];
  scanf("%s", s);
  for (int i = 0; i < 4; ++i) {
    a[i] = s[i] - '0';
  }
  for (int i = -1; i <= 1; i += 2) {
    for (int j = -1; j <= 1; j += 2) {
      for (int k = -1 ; k <= 1; k += 2) {
        int res = a[0] + i * a[1] + j * a[2] + k * a[3];
        if (res == 7) {
          printf("%d%c%d%c%d%c%d", a[0], op(i), a[1], op(j), a[2], op(k), a[3]);
          puts("=7");
          return 0;
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stdio.h>


using namespace std;

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

int main() {
    double x1,x2,y1,y2,x,y;
    cin >> x1 >> y1 >> x2 >> y2;
    //cout << sqrt(pow(x2-x1,2)+pow(y2-y1,2)) << endl;
    printf("%.6lf\n", sqrt(pow(x2-x1,2)+pow(y2-y1,2)));
    return 0;
}



Measured memory_bytes: 3200
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  cout << 0 << endl;
  int initial = 0;
  {
    string s;
    cin >> s;
    if (s != "Male") ++initial;
  }
  const array<string, 2> gender = {{"Male", "Female"}};
  int l = 0, r = N;
  while (r - l > 1) {
    int mid = l + (r - l) / 2;
    cout << mid << endl;
    string s;
    cin >> s;
    if (s == "Vacant") break;
    if (s == gender[(initial + mid) % 2])
      l = mid;
    else
      r = mid;
  }
}


Measured memory_bytes: 852
N = int(input())
s = sorted(list(int(input()) for _ in range(N)))
tmp = sum(s)
if tmp % 10 != 0:
    print(tmp)
else:
    for i in s:
        if i % 10 != 0:
            print(tmp-i)
            break
    else:
        print(0)

Measured memory_bytes: 3060
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    int n; scan(n);
    writeln(n * n * n);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#include <queue>
#include <string.h>
#include <bitset>

#define ll long long int
#define ld long double
#define rep(i,n) for(int i = 0;i < n;i++)
#define rep1(i,n) for(int i = 1;i < n;i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define allr(x) x.begin(),x.end(),greater<int>()
#define P pair<ll,ll>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1ll << 60
#define PI 3.14159265359

using namespace std;

int main(){
	ll a;
	cin >> a;
	int tmp = a;
	int f = 0;
	while(f == 0){
		f = 1;
		for(int i = 2;i < sqrt(tmp);i++){
			if(tmp%i == 0){
				f = 0;
			}
		}
		if(f == 1){
			cout << tmp << endl;
			return 0;
		}
		else{
			tmp++;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (n : k : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    n' = n `mod` k :: Int
  print $ min n' (k - n')

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
	ll x,y,z;
	cin >> x >> y >> z;
	vector<pair<ll,pair<ll,ll> > > v;
	ll sm = 0;
	rep(i,x+y+z){
		ll a,b,c;
		cin >> a >> b >> c;
		sm += c;
		a -= c;
		b -= c;
		v.push_back(MP(b-a,MP(a,b)));
	}
	sort(v.begin(),v.end());
	vector<ll>a(x+y+z),b(x+y+z);
	// cerr << sm << endl;
	// cerr << endl;
	rep(i,x+y+z){
		a[i] = v[i].second.first;
		b[i] = v[i].second.second;
		//cerr << a[i] << " " << b[i] << endl;
	}
	ll n = x+y+z;
	vector<ll>sa(n),sb(n+1);
	priority_queue<ll,vector<ll>,greater<ll> >pq,pq2;
	rep(i,n){
		if(i<x){
			if(i!=0)sa[i] = sa[i-1]+a[i];
			else sa[i] = a[i];
			pq.push(a[i]);
		}else{
			sa[i] = sa[i-1]+a[i];
			pq.push(a[i]);
			ll x = pq.top();
			pq.pop();
			sa[i]-=x;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(i>=n-y){
			sb[i] = sb[i+1]+b[i];
			pq2.push(b[i]);
		}else{
			sb[i] = sb[i+1]+b[i];
			pq2.push(b[i]);
			ll x = pq2.top();
			pq2.pop();
			sb[i]-=x;
		}
	}
	// cerr << endl;
	// rep(i,n)cerr << sa[i] << " ";
	// cerr << endl;
	// rep(i,n)cerr << sb[i] << " ";
	// cerr << endl;

	ll ans = 0;
	for(int i=x-1;i<n-y;i++){
		ans = max(ans,sm+sa[i]+sb[i+1]);
		//cerr << ans <<endl;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7792
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(begin(a), end(a));
  auto f = [&](int m) {
    vector<vector<int>> dp(n + 1, vector<int>(k, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < k; j++) {
        dp[i + 1][j] |= dp[i][j];
        if (i != m && j - a[i] >= 0) dp[i + 1][j] |= dp[i][j - a[i]];
      }
    }
    bool need = false;
    for (int i = max(0, k - a[m]); i < k; i++) {
      if (dp[n][i]) need = true;
    }
    return need;
  };
  int ng = -1;
  int ok = n;
  while (ok - ng > 1) {
    int m = (ok + ng) / 2;
    (f(m) ? ok : ng) = m;
  }
  cout << ng + 1 << endl;
}


Measured memory_bytes: 98204