akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int UF_MAX = 1e5 + 3;

class UF{
	int x[UF_MAX];
	LL p[UF_MAX];
	priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> Q[UF_MAX];
	
public:

	void clear(){
		fill(x,x+UF_MAX,-1);
		fill(p,p+UF_MAX,0);
		repp(i,0,UF_MAX) while(!Q[i].empty()) Q[i].pop();
	}
	
	int boss(int a){
		int s = a;
		while(x[s] > -1) s = x[s];
		if(s != a) x[a] = s;
		return s;
	}
	
	void uni(int a , int b){
		int s = boss(a);
		int t = boss(b);
		if(s != t){
			if(Q[s].size() < Q[t].size()) swap(s,t);
			while(!Q[t].empty()){
				Q[s].push(Q[t].top());
				Q[t].pop();
			}
			if(x[s] < x[t]){
				x[s] += x[t];
				x[t] = s;
				p[s] += p[t];
			} else {
				x[t] += x[s];
				x[s] = t;
				p[t] += p[s];
				swap(Q[s],Q[t]);
			}
		}
	}

	LL get_p(int a){
		return p[boss(a)];
	}

	int get_q(int a){
		a = boss(a);
		return Q[a].empty()?-1:Q[a].top().second;
	}

	void set(int a , LL b){
		p[a] = b;
	}

	void push(int a , int b , LL c){
		Q[a].push({c,b});
	}

	void pop(int a){
		Q[boss(a)].pop();
	}
};

const int MC = 1e5 + 3;
int N,M;
LL A[MC],B[MC],S;
vector<int> V[MC];
UF uf;

bool eval(LL z){
	vector<int> used(N,0);
	queue<int> Q;
	uf.clear();
	repp(i,0,N){
		for(auto u : V[i]) uf.push(i,u,A[u]);
		if(z >= A[i]){
			Q.push(i);
			uf.set(i,B[i]);
			used[i] = 1;
		}
	}
	while(!Q.empty()){
		int k = Q.front(); Q.pop();
		for(int u = uf.get_q(k) ; u >= 0 && z + uf.get_p(k) >= A[u] ; u = uf.get_q(k)){
			if(!used[u]){
				Q.push(u);
				uf.set(u,B[u]);
				used[u] = 1;
			}
			uf.pop(k);
			uf.uni(k,u);
		}
	}
	int c = 0;
	repp(i,0,N) c += used[i];
	return c == N;
}

LL BS(LL x , LL y){
	if(x-y<2) return x;
	LL z = (x+y)/2;
	return eval(z)?BS(z,y):BS(x,z);
}

int main(){
	cin >> N >> M;
	repp(i,0,N){
		cin >> A[i] >> B[i];
		S += B[i];
		A[i] -= B[i];
	}
	repp(i,0,M){
		int x,y; cin >> x >> y;
		V[--x].push_back(--y);
		V[y].push_back(x);
	}
	cout << S + BS(1e9,-1) << endl;
	return 0;
}


Measured memory_bytes: 22140
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>

using namespace std;

const int MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;
#define rep(i, m, n) for(int i=m;i<n;i++)
#define rrep(i, n, m) for(int i=n;i>=m;i--)

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, 0, N){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    cout << a[N - 1] - a[0] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int n,m,k,l,s;
	cin >> n>>m>>k>>l;
	s = 0;
	if (l == 1) {
		s = 1;
	}
	cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
typedef long long ll;

int main(){
   int n,m,c,ans=0,sum=0;
   cin >> n >> m >> c;
   vector<int> b(m);
   rep(i,m) cin >> b[i];
   rep(i,n){
       vector<int> a(m);
       rep(j,m) cin >> a[j];
       sum=c;
       rep(j,m){
           sum+=a[j]*b[j];
       }
       if(sum>0) ans++;
   }
   cout << ans;
}

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    int minv = 114514;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        minv = min(minv, m);
        x -= m;
    }
    int ans = n + x / minv;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 896
N = int(input())
A, B, C = [], [], []
for i in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
dp = [[0]*3 for _ in range(N)]
dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]
for i in range(1,N):
    dp[i][0] = A[i] + max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = B[i] + max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = C[i] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

Measured memory_bytes: 78168
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if (a+b+c >= 22) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args){
		try(Scanner scan = new Scanner(System.in)){
			String S = scan.nextLine();
			
			int max = (int) Math.pow(2,S.length()-1);
			long ans = 0;
			
			for(int bit = 0; bit<max; bit++){
				int left = 0;
				for(int i = 0; i < S.length()-1; i++){
					if( ((bit >> i) & 1) > 0){
						ans += Long.valueOf(S.substring(left, i+1));
						left = i+1;
					}
				}
				ans+=Long.valueOf(S.substring(left, S.length()));
			}
			
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 21204
n = int(input())
time = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    time[i] = [time[i][1],time[i][0]]

time.sort()

ans = 'Yes'
t = 0
for i in range(n):
    t += time[i][1]
    if t > time[i][0]:
        ans = 'No'

print(ans)


Measured memory_bytes: 50792
import sys
# int(input()) # 入力が1つ
h, w = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

square = [[''] * (w + 2)]
for _ in range(h):
    row = list(input())
    row = ['.'] + row + ['.']
    square.append(row)
square.append([''] * (w + 2))

for i in range(1, h):
    for j in range(1, w):
        if square[i][j] == '#':
            if square[i + 1][j] == '#' or square[i][j + 1] == '#' or square[i - 1][j] == '#' or square[i][j - 1] == '#':
                # right, down, left, up
                continue
            else:
                print('No')
                sys.exit()
print('Yes')

Measured memory_bytes: 39024
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>


#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...)
#define showlr(n,l,r)
#endif

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;
/*------------end of definitions------------*/

char c;

signed main(){

    in(c);
    puts(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'?"vowel":"consonant");

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;
//import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int w = parseInt(sc.next());
		String[] s = new String[n];
		for (i = 0; i < n; i++) {
			s[i] = sc.next();
		}
		sc.close();
		for (i = 0; i < n; i++) {
			out.println(s[i]);
			out.println(s[i]);
		}
	}
}


Measured memory_bytes: 23684
#include<iostream>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
ll dp[201][201];
int N;
int junni[200];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		char c;
		cin >> c;
		if (c == '-')junni[i] = 0;
		else if (c == 'U')junni[i] = 1;
		else junni[i] = 2;
	}
	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N; j++) {
			dp[i][j] %= MOD;

			if (junni[i] == 0) {
				dp[i + 1][j] += dp[i][j];
			}
			else if (junni[i] == 1) {
				//U
				if(j < N)
					dp[i + 1][j + 1] += dp[i][j];
				if(j > 0)
					dp[i + 1][j] += dp[i][j] * j;
			}
			else {
				//D
				if(j > 0)
					dp[i + 1][j] += dp[i][j] * j;
				if (j >= 1)
					dp[i + 1][j - 1] += dp[i][j] * j * j;
			}
		}
	}
	cout << dp[N][0] % MOD << endl;
	return 0;
}


Measured memory_bytes: 3432
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll maxn=200005;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll quickp(ll a,ll n){
	ll ans=1;
	while(n){
		if(n&1) ans=a*ans%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}

int main(){
	int n;
	scanf("%d",&n);
	map<pair<ll,ll>,pair<int,int>>mp;
	int zero=0;
	ll sum=1;
	for(int i=1;i<=n;i++){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if(a==0&&b==0){zero++;continue;}
		ll g=gcd(a,b);
		a/=g,b/=g;
		if(b<0) b=-b,a=-a;
		if(a<=0) mp[make_pair(b,-a)].second++;
		else mp[make_pair(a,b)].first++;
	}
	for(auto it=mp.begin();it!=mp.end();it++){
		sum=(quickp(2,it->second.first)+quickp(2,it->second.second)-1)%mod*sum%mod;
	}
	sum=(sum+zero-1)%mod;
	sum=(sum%mod+mod)%mod;
	printf("%lld\n",sum);
}

Measured memory_bytes: 16164
<?php

fscanf(STDIN, "%d", $n);
$p=trim(fgets(STDIN));
$list = explode(" ",$p);
$ans=0;
for($i=1;$i<($n-1);$i++){
    $new_array = [$list[$i-1], $list[$i],$list[$i+1]];
    sort($new_array);
    if($new_array[1] == $list[$i]){
        $ans++;
    }
}
echo $ans;

Measured memory_bytes: 4728
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n, m = sc.nextInt()
  val a = Array.fill(n)(sc.next().map(_ == '#'))
  val b = Array.fill(m)(sc.next().map(_ == '#'))

  var found = false
  for {
    i <- 0 to n-m
    j <- 0 to n-m
    if !found
  } {
    var ok = true
    for {
      di <- 0 until m
      dj <- 0 until m
      if a(i + di)(j + dj) != b(di)(dj)
    } {
      ok = false
    }

    if (ok) {
      found = true
    }
  }
  println(if (found) "Yes" else "No")
}


Measured memory_bytes: 57416
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    double rev1, rev2;
    vector<int> A(110);
    int N;
    cin >> N;
    for (int i=0;i<N;i++) cin >> A[i];

    rev1 = 0.0;
    for (int i=0;i<N;i++) {
        rev1 += 1.0/A[i];
    }
    rev2 = 1.0/rev1;
    cout << fixed << setprecision(10) << rev2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 200005 ;
using namespace std ;

int n, a[N] ;
map <int, int> H[2] ;

int main(){
	scanf("%d", &n) ;
	rep(i, 1, n) {
		scanf("%d", &a[i]) ;
	}	
	sort(a + 1, a + n + 1) ;
	reverse(a + 1, a + n + 1) ;
	a[n + 1] = 0 ;
	rep(i, 1, n) {
		H[0][i] = a[i] ;
		if (i > a[i + 1] && i <= a[i]) {
			if ((a[i] - i + 1) & 1) printf("Second") ; else printf("First") ;
			return 0 ; 
		}
	}
	for (int i = 1, j ; i <= n; i = j) {
		for (j = i + 1 ; j <= n && a[i] == a[j]; ++ j) ;
		if (a[i] >= i && a[i] <= j - 1) {
			if ((j - a[i]) & 1) printf("Second") ; else printf("First") ;
			return 0 ;
		}
		H[1][a[i]] = j - 1 ;
	}
	rep(i, 2, n) if (a[i] != a[i - 1]) {
		int x = i - 1, y = a[i] ;
		if (x != y) continue ;
		int p = (y - H[0][x]) & 1, q = (H[1][y] - x) & 1 ;
		if (p || q) printf("First") ; else printf("Second") ;
		return 0 ; 
	}
	
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H=in();
    int W=in();
    char saisyo[H][W];
    bool h[H]={};
    bool w[W]={};
    string s;
    bool flg;
    REP(i,H){
        cin>>s;
        flg=true;
        REP(j,W){
            saisyo[i][j]=s[j];
            if(s[j]=='#')flg=false;
        }
        if(flg){
            h[i]=true;
        }
    }
    REP(i,W){
        
        flg=true;
        REP(j,H){
            if(saisyo[j][i]=='#'){
                flg=false;
            }
        }
        if(flg)w[i]=true;
    }
    REP(i,H){
        if(h[i]){
            //debug(i);
            continue;
        }
        REP(j,W){
            if(w[j]){
                //debug(j);
                continue;
            }
            cout<<saisyo[i][j];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
int n,m,t;
V e,x,z,w;
void M(const V &_x,const V &_y){
	int i=0,j;
	if(t&1){
		for(;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(_x[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m,w[i*n+j]=(_y[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
		swap(e,z);
	}else{
		for(;i<n;i++)for(j=0;j<n;j++)w[i*n+j]=(_y[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
	}
	x=w;
}
void O(const V &r,const V &s){
	int i=0;
    for(;i<n-1;i++)printf("%d ",(r[slice(i*n,n,1)]*s).sum()%m);
    printf("%d\n",(r[slice(i*n,n,1)]*s).sum()%m);
}
main(){
	int i,a,b,c;
	for(;scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&t),n;){
		x.resize(0);
		x.resize(n*n);
		e.resize(0);
		e.resize(n*n);
		z.resize(n*n);
		w.resize(n*n);

		x[0]=b;
		x[1]=c;
		e[0]=1;
		for(i=1;i<n-1;i++){
			x[i*n+i-1]=a;
			x[i*n+i]=b;
			x[i*n+i+1]=c;
			e[i*n+i]=1;
		}
		x[i*n+i-1]=a;
		x[i*n+i]=b;
		e[i*n+i]=1;
		for(;t;t>>=1)M(e,x);
		V s(n);
		for(i=0;i<n;i++)scanf("%d",&s[i]);
		O(e,s);
	}
}

Measured memory_bytes: 1108
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        int N = sc.nextInt();
        int C = sc.nextInt();
        var D = new int[C, C];
        for (int i = 0; i < C; i++) {
            for (int j = 0; j < C; j++) {
                D[i, j] = sc.nextInt();
            }
        }
        var c = new int[N, N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                c[i, j] = sc.nextInt();
            }
        }

        var zero = new long[C];
        var one = new long[C];
        var two = new long[C];
        for (int k = 0; k < C; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if ((i + j + 2) % 3 == 0) {
                        zero[k] += D[c[i, j] - 1, k];
                    } else if ((i + j + 2) % 3 == 1) {
                        one [k] += D[c[i, j] - 1, k];
                    } else {
                        two[k] += D[c[i, j] - 1, k];
                    }
                }
            }
        }

        var min = long.MaxValue;
        for (int i = 0; i < C; i++) {
            for (int j = 0; j < C; j++) {
                if (i == j) continue;
                for (int k = 0; k < C; k++) {
                    if (i == k) continue;
                    if (j == k) continue;

                    min = Math.Min(min, zero[i] + one[j] + two[k]);
                }
            }
        }
        WriteLine(min);
    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {


        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}

Measured memory_bytes: 16084
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define FOR(i, r, n) for (int i=(int)(r); i<=(int)(n); i++)
#define all(v) v.begin(), v.end()
#define INF 2147483647
#define INF64 9223372036854775807
#define MOD 1000000007

int main(){

    int n, k;cin>>n>>k;
    vector<int> p(n);
    rep(i, n)cin>>p[i];

    sort(all(p));
    int ans=0;
    rep(i, k) ans+=p[i];
    cout<<ans<<endl;

}

Measured memory_bytes: 3600
h=[[0]*10 for _ in range(10)]
n=int(input())
for i in range(1,n+1):
    k=i%10
    s=i//(10**(len(str(i))-1))
    h[s][k]+=1
ans=0
for i in range(10):
    for j in range(10):
        ans+=h[i][j]*h[j][i]
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;

class Dice{
public:
  int face[6];
  int top(){return face[0];}
  int left(string s, string r);
  int label(int n);
  void setFace(int i, int num);
  void moveFloor(char dir);
};

void Dice::setFace(int i, int num){
  face[i] = num;
  return;
}

int Dice::left(string s, string r){
  string a = "02530";
  string b = "01540";
  string c = "12431";
  if(a.find(s) != string::npos) return face[4];
  if(a.find(r) != string::npos) return face[1];
  if(b.find(s) != string::npos) return face[2];
  if(b.find(r) != string::npos) return face[3];
  if(c.find(s) != string::npos) return face[0];
  if(c.find(r) != string::npos) return face[5];
}

int Dice::label(int n){
  for(int i=0; i<6; i++){
    if(face[i] == n) return i;
  }
}

int main(){
  int num, q;
  Dice d;
  for(int i=0; i<6; i++){
    cin >> num;
    d.setFace(i, num);
  }

  cin >> q;
  for(int i=0; i<q; i++){
    int top, flont;
    cin >> top >> flont;

    string s, r;
    s = to_string(d.label(top)) + to_string(d.label(flont));
    r = to_string(d.label(flont)) + to_string(d.label(top));
    cout << d.left(s, r) << endl;
  }

  return 0;
}



Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair

void solve(int test)
{

    int n;
    cin>>n;

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

    int i,j;

    for(i=0;i<n;i++)
    {
        cin>>v[i].first;
        cin>>v[i].second;
    }

    for(i=2;i<n;i++)
    {
        if(v[i].first!=v[i].second)continue;
        if(v[i-1].first!=v[i-1].second)continue;
        if(v[i-2].first!=v[i-2].second)continue;

        cout<<"Yes"<<endl;
        return;
    }
    cout<<"No"<<endl;

    return;
}

int main() {

 int t = 1;
// cin>>t;

 for(int x=1;x<=t;x++)
 {
    solve(x);
 }
  return 0;
}


Measured memory_bytes: 3632
fn main() {
    proconio::input! {
        mut n: u64,
    }
    let mut x=2;
    let mut p=vec![];
    while x*x<=n {
        let mut c=0;
        while n%x==0 {
            c+=1;
            n/=x;
        }
        p.push(c);
        x+=1;
    }
    if n!=1 {
        p.push(1);
    }
    let mut m=0;
    for p in p {
        let mut c=p;
        let mut i=1;
        while c>=i {
            m+=1;
            c-=i;
            i+=1;
        }
    }
    println!("{}",m);
}

Measured memory_bytes: 6036
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

constexpr int MOD = 1e9+7;
struct mint
{
	int v;
	mint():v(0){}
	mint(int v):v((v+MOD)%MOD){}
	mint operator-()const{ return mint(0) - *this; }
	mint& operator+=(const mint& a){ if((v+=a.v)>=MOD) v-=MOD; return *this; }
	mint& operator-=(const mint& a){ if((v+=MOD-a.v)>=MOD) v-=MOD; return *this; }
	mint& operator*=(const mint& a){ (v*=a.v)%=MOD; return *this; }
	mint& operator/=(const mint& a){ (*this) *= a.inv(); return *this; }
	mint operator+(const mint& a)const{ return mint(*this) += a; }
	mint operator-(const mint& a)const{ return mint(*this) -= a; }
	mint operator*(const mint& a)const{ return mint(*this) *= a; }
	mint operator/(const mint& a)const{ return mint(*this) /= a; }
	bool operator<(const mint& a)const{ return v < a.v; }
	bool operator==(const mint& a)const{ return v == a.v; }
	mint pow(int k)const{ mint r(1),t(v); while(k){ if(k&1) r*=t; t*=t; k>>=1; } return r; }
	mint inv()const{ return pow(MOD-2); }
	static mint comb(int n, int k) {
		if(n-k<k) k=n-k;
		mint num(1), dom(1);
		for(int i=0;i<k;i++) { num*=n-i; dom*=i+1; }
		return num/dom;
	}
};
std::istream& operator>>(std::istream&i,mint&a){ int t; i>>t; a=mint(t); return i; }
std::ostream& operator<<(std::ostream&o,const mint&a){ o<<a.v; return o; }


signed main() {
	int n;
	std::cin >> n;
	std::vector<int> c(n);
	rep(i,n) std::cin >> c[i];
	std::sort(all(c));
	mint sum = 0;
	rep(i,n) {
		sum+=mint(c[i])*mint(2).pow(2*n-2)*(n-i+1);
	}
	print(sum);
	return 0;
}


Measured memory_bytes: 1792
const NMAX=60;
type realAry=array[1..NMAX]of real;
var v:realAry;
    n,i,binal:integer;
    ans:real;
procedure sort(s,t:integer);
  var i,j:integer;
      tmp,pivot:real;
begin
  i:=s; j:=t; pivot:=v[(s+t)div 2];
  repeat
    while v[i]<pivot do i:=i+1;
    while v[j]>pivot do j:=j-1;
    if i<=j then begin
      tmp:=v[i]; v[i]:=v[j]; v[j]:=tmp;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if j>s then sort(s,j);
  if i<t then sort(i,t);
end;

begin
  readln(n);
  for i:=1 to n do read(v[i]);
  sort(1,n);
  ans:=v[1];
  for i:=2 to n do ans:=(ans+v[i])/2;
  writeln(ans:5:5);
end.


Measured memory_bytes: 128
/****************************** بسم الله الرحمن الرحيم ************************/
/*---------------------------------------------------------------------*/
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ordered_set tree<pair<int, int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define compare bool operator <
#define main int main()
#define sf(n) scanf ("%d", &n)
#define pf(n) printf ("%d", n)
#define sfl(n) scanf ("%lld", &n)
#define pfl(n) printf ("%lld", n)
#define pfnewline() printf("\n")
#define pfspace() printf(" ")
#define mem(x,y) memset( (x), (y), sizeof(x) )
#define max3(a,b,c)   max(a , max(b,c) )
#define min3(a,b,c)  min(a, min(b,c) )
#define Ex 2.718281828
#define pi acos(-1.0)
#define toDecimal(n) fixed<< setprecision(n)
#define rep1(i, n) for(int i = 1; i<=n;i++)
#define rep(i, n) for(int i = 0; i<n;i++)
#define sfc(ch) scanf("%c",&ch)
#define sfs(ch) scanf("%[^\n]%*c", ch);

const ll mxn = 1e5+3;

/** ---8 moves --- **/
//int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
//int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/** ---4 moves--**/
//int dx[] = {-1,0,0,1};
//int dy[] = {0,-1,1,0};

using namespace __gnu_pbds;
using namespace std;

ll a[100005];
ll dp[100005];
int n,k;

int recur(int el)
{
    //cout << el << endl;
    if(el >=n)
    {
        return 0;
    }
    else if( dp[el] != 1000000000000000009)
    {
        //cout << el;
        return dp[el];
    }
    //cout << el << "el" << endl;
    for(int i = el+1;i<=min(el+k,n-1);i++ )
    {
      //  cout << i << endl;
        dp[el] = min( dp[el], recur( i ) + abs(a[el] - a[i])  );
    }
    return dp[el];
   // cout << "Shesh" << endl;
}

main
{
    fast;
    cin >> n >> k;
    for(int i = 0;i<n;i++)
    {
        dp[i] = 1000000000000000009;
    }
    rep(i,n)
    {
        cin >> a[i];
    }
    dp[n-1] = 0;
   // cout << dp[0] << endl;
    cout << recur(0) << endl;
    //cout << dp[n-2] << endl;
//    rep(i,n)
//    {
//        cout << dp[i] <<"  ";
//    }
//    cout << endl;
    //cout << dp[0] << endl;
}



Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll t,a,b,c,i,j,k,n;
    map<ll,ll>m;
    cin>>a>>b>>c;
    m[a]++;
    m[b]++;
    m[c]++;
    if(m[5]==2&&m[7]==1)
    {
        cout<<"YES"<<endl;
    }
    else
        cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 3520
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define resz resize
 
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;

ll gcd(ll a,ll b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
ll po(ll a,ll b)
{
    ll ans = 1;
    while(b--)
        ans*=a;
    return ans;
}
ll pom(ll a,ll b,ll mod)
{
    if(b==0)return 1;
    ll k = pom(a,b/2,mod);
    if(b%2==0)return (k*k)%mod;
    else return ((k*k)*mod*a)%mod;
}

int check(int n)
{
    if(n==2)return 1;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)return 0;
    }
    return 1;
}
int ch[3];

int check(int p,int q)
{
    if((p+1)%3==q)return ch[p];
    else if(p==q)return 0;
    else return 0;
}



void solve()
{
    int n,k;
    cin>>n>>k;
    cin>>ch[0]>>ch[1]>>ch[2];
    string str;
    cin>>str;
    int arr[n+1];
    FOR(i,0,n)
    {
        if(str[i]=='r')arr[i]=0;
        else if(str[i]=='s')arr[i]=1;
        else arr[i]=2;
    }
    int dp[n+1][3];
    FOR(i,0,n)
    {
        FOR(j,0,3)
        dp[i][j]=0;
    }
    dp[0][0]=check(0,arr[0]);
    dp[0][1]=check(1,arr[0]);
    dp[0][2]=check(2,arr[0]);
    FOR(i,1,k)
    {
        FOR(j,0,3)
        {
            dp[i][j]=max(max(dp[i-1][0],dp[i-1][1]),dp[i-1][2])+check(j,arr[i]);
        }
    }

    FOR(i,k,n)
    {
        FOR(j,0,3)
        {

            dp[i][j]=max(max(dp[i-1][0],dp[i-1][1]),dp[i-1][2])+check(j,arr[i]);
            int p = max(max(dp[i-k][0],dp[i-k][1]),dp[i-k][2]);
            //cout<<' '<<dp[i][j]<<' '<<k<<endl;
            if(j==0&&dp[i-k][0]==p)
                dp[i][j]=dp[i][j]-p+max(dp[i-k][1],dp[i-k][2]);
            if(j==1&&dp[i-k][1]==p)
                dp[i][j]=dp[i][j]-p+max(dp[i-k][0],dp[i-k][2]);
            if(j==2&&dp[i-k][2]==p)
                dp[i][j]=dp[i][j]-p+max(dp[i-k][0],dp[i-k][1]);
            //cout<<i<<' '<<j<<endl;
        }

    }
    // FOR(i,0,n)
    // {
    //     FOR(j,0,3)cout<<dp[i][j]<<' ';
    //     cout<<endl;
    // }
    cout<<max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);


}




int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    */
        ll t;
    //cin>>t;
    //while(t--)
        solve();
}



Measured memory_bytes: 2000
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	int i;
	string s;
	cin>>s;
	bool flag = true;
	int len = s.length();
	for(i=0;i<len;i++){
		if(i%2==0 && (s[i]!='D' && s[i]!='R' && s[i]!='U')){
			flag = false;
		}
		else if(i%2!=0 && (s[i]!='L' && s[i]!='D' && s[i]!='U')){
			flag = false;
		}
	}
	flag?cout<<"Yes":cout<<"No";
 	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll n,s,r,count=0;
	cin>>n;
	s=n;
	while(s>0){
		r=s%10;
		count+=r;
		s=s/10;
	}
	if(n%count==0){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007


int main() {
	ll n,p;
	cin>>n>>p;
	ll ans=1;
	if(n==1){
		cout << p;
		return 0;
	}
	for(ll i=2;i*i<=p;i++){
		ll cnt=0;
		while(p%i==0){
			cnt++;
			p/=i;
		}
		//cout << cnt <<i <<endl;
		if(cnt/n==0){
			continue;
		}
		ll key=pow(i,cnt/n);
		ans*=key;
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
#include<math.h>

using namespace std;
int facctorialMethod(int k);

int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	vector<int>b(n);
	vector<int>w(n);
	vector<int>wb(n);
	int ai = 1, bi = 1;

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

	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			if (w[j] == a[i]) {
				ai += j * facctorialMethod(n - i - 1);
				w.erase(w.begin() + j);
			}
		}
		for (int j = 0; j < n - i; j++) {
			//cout << w[j];
		}
		//cout << endl;
	}

	//cout << ai << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			if (b[i] == wb[j]) {
				bi += j * facctorialMethod(n - i - 1);
				wb.erase(wb.begin() + j);
				//cout<<bi<<endl;
			}

		}
	}
	//cout<<bi;
	cout << abs(ai - bi) << endl;

}

int facctorialMethod(int k) {
	int sum = 1;
	for (int i = 1; i <= k; ++i)
	{
		sum *= i;
	}
	return sum;
}

Measured memory_bytes: 256
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define ends ' '
#define endl '\n'
#define pb emplace_back
#define x first
#define y second
#define pii pair<int, int>
#define sz(x) (int)(x).size()

vector<vector<int>> h;
vector<int> G;
vector<vector<int>>mn;

const int prime = 1e9+7;

int mod(int a, int p = prime) { return (a%p + p) % p; }

deque<int> D;

void f(vector<int> &mn, vector<int> &h, int &b)
{
	D.clear();
	for(int i = 1; i <= b; ++i)
	{
		while(!D.empty() and h[D.back()] >= h[i])
			D.pop_back();
		D.push_back(i);
	}

	mn[b] = h[D.front()];

	for(int i = b+1; i < mn.size(); ++i)
	{
		if(D.front() <= i-b)
			D.pop_front();
		while(!D.empty() and h[D.back()] >= h[i])
			D.pop_back();
		D.push_back(i);
		mn[i] = h[D.front()];
	}
}


int32_t main()
{
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif
	IOS;

	int n;
	
	cin >> n;

	vector<int> a(n);

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

	reverse(a.begin(), a.end());

	multiset<int> ms;

	for(int i = 0; i < n; ++i)
	{
		ms.insert(a[i]);
		auto it = ms.upper_bound(a[i]);
		if(it != ms.end())
			ms.erase(it);
	}

	cout << ms.size();

	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;

const int mx=100010;
const ll mod=998244353;

int n,c;
ll ans=1;
map<ll, ll> s;

int main(){
  cin >> n;
  cin >> c;
  s[c]++;
  if(c!=0){cout << 0 << endl; return 0;}
  for(int i=1; i<n; i++){
    int d;
    cin >> d;
    s[d]++;
  }

  if(s[0]!=1){cout << 0 << endl; return 0;}

  for(int i=1, co=1; i<n && co<n; i++){
    for(int j=0; j<s[i]; j++){
      ans *= s[i-1];
      ans %= mod;
    }
    co += s[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 1000000007
using namespace std;
int n;
int fpow(int a,int b)
{
	int ans=1,t=a;
	while(b)
	{
		if(b&1)ans=(long long)ans*t%Mod;
		t=(long long)t*t%Mod;
		b>>=1;
	}
	return ans;
}
struct Fenwick{
	int c[200010];
	inline int lowbit(int x)
	{
		return x&(-x);
	}
	void add(int x,int y)
	{
		for(;x<=n;x+=lowbit(x))
			c[x]=(c[x]+y)%Mod;
		return ;
	}
	int query(int x)
	{
		int ans=0;
		for(;x;x-=lowbit(x))
			ans=(ans+c[x])%Mod;
		return ans;
	}
	void clear()
	{
		memset(c,0,sizeof(c));
		return ;
	}
}F;
int cnt[200010],num[200010];
int to[200010];
int A[200010];
int f[200010],g[200010];
int calcf(int l,int r)
{
	return (long long)f[r]*fpow(f[l-1],Mod-2)%Mod;
}
int calcg(int l,int r)
{
	if(to[l+1]>r)
		return (long long)g[r]*fpow(g[l-1],Mod-2)%Mod;
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&A[i]),cnt[A[i]]++;
	int all=1;
	for(int i=n;i>=1;i--)
	{
		if(i<n)cnt[i]+=cnt[i+1]-1;
		all=(long long)all*cnt[i]%Mod;
		if(!cnt[i]){
			printf("0\n");
			return 0;
		}
	}
	f[0]=1,g[0]=1;
	for(int i=1;i<=n;i++)
	{
		f[i]=(long long)cnt[i]*f[i-1]%Mod;
		if(cnt[i]>1)g[i]=(long long)g[i-1]*(cnt[i]-1)%Mod;
		else g[i]=g[i-1];
	}
	to[n+1]=n+1;
	for(int i=n;i>=1;i--)
		if(cnt[i]==1)to[i]=i;
		else to[i]=to[i+1];
	//A[i]<A[j]
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		int res=((long long)F.query(to[A[i]+1]-1)-F.query(A[i])+Mod)%Mod*cnt[A[i]]%Mod*f[A[i]-1]%Mod*fpow(g[A[i]],Mod-2)%Mod;
		ans=(ans+(long long)res*fpow(2,Mod-2))%Mod;
		F.add(A[i],(long long)calcf(A[i]+1,n)*g[A[i]]%Mod);
	}
	//A[i]=A[j]
	for(int i=1;i<=n;i++)
		num[A[i]]++;
	for(int i=1;i<=n;i++)
		ans=(ans+((long long)num[i]*(num[i]-1)/2)%Mod*all%Mod*fpow(2,Mod-2))%Mod;
	//A[i]>A[j]
	F.clear();memset(num,0,sizeof(num));
	for(int i=1;i<=n;i++)
	{
		num[i]=F.query(n)-F.query(A[i]);
		F.add(A[i],1);
	}
	F.clear();
	for(int i=1;i<=n;i++)
	{
		int res=((long long)F.query(to[A[i]+1]-1)-F.query(A[i])+Mod)%Mod*cnt[A[i]]%Mod*f[A[i]-1]%Mod*fpow(g[A[i]],Mod-2)%Mod;
		ans=((ans+(long long)num[i]*all%Mod-(long long)res*fpow(2,Mod-2)%Mod)%Mod+Mod)%Mod;
		F.add(A[i],(long long)calcf(A[i]+1,n)*g[A[i]]%Mod);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 5760
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	int ans = min(A, B) + min(C, D);
	cout << ans;
}

Measured memory_bytes: 256
H,W=map(int,input().split())
zu=["."*(W+2)]

for i in range(H):
  zu.append("."+input()+".")

zu.append(zu[0])
#print(zu)

for h in range(1,H+2):
    for w in range(1,W+2):
        if zu[h][w]=="#":
          if zu[h-1][w]==".":
            if zu[h][w-1]==".":
              if zu[h+1][w]==".":
                if zu[h][w+1]==".":
                  print("No")
                  break
   
    else:
        continue
    break

else:
  print("Yes")
  
#if zu[h-1][w]=="." and zu[h][w-1]=="." and zu[h+1][w]=="." and zu[h][w+1]==".":

Measured memory_bytes: 9152
N,M = map(int,input().split())
Data = list(map(int,input().split()))
Sum = [0]*(N+1)
Sum[0] = 0
for i in range(1,N+1):
    Sum[i] = (Sum[i-1]+Data[i-1]) % M

Dic = {}
ans = 0
for i in range(N+1):
    if Sum[i] in Dic:
        ans += Dic[Sum[i]]
        Dic[Sum[i]] += 1
    else:
        ans += 0
        Dic[Sum[i]] = 1
print(ans)


Measured memory_bytes: 16296
local str = io.read()
local ans = 0
local tbl = {}
for cur=1, string.len(str) do
	tbl[cur] = string.sub(str,cur,cur)
end
local used = {}
local cur = 1
local Anum = 0
while cur <= #tbl -2 do
	local flag = false
	if tbl[cur] == "A" and tbl[cur+1] == "B" and tbl[cur+2] == "C" then

		ans = ans + 1
		tbl[cur] = "B"
		tbl[cur+1] = "C"
		tbl[cur+2] = "A"
		-- l = cur -1 
		-- while l > 0 and tbl[l] == "A"  do
		-- 	flag = true
		-- 	ans = ans + 1
		-- 	tbl[l] = "B"
		-- 	tbl[l+1] = "C"
		-- 	tbl[l+2] = "A"
		-- 	l = l - 1
		-- end
		-- print("######", Anum)
		if Anum > 0 then
			ans = ans + Anum
			tbl[cur +1] = "A"
			if Anum > 1 then
				tbl[cur] = "A"
			end
			Anum = Anum - 1
		end
	elseif tbl[cur] == "A" then
		if cur - 1 > 0 and tbl[cur - 1] == "A" then
			Anum = Anum + 1
		else
			Anum = 1
		end
	else
		Anum = 0
	end

    cur = cur + 1
end
print(ans)

Measured memory_bytes: 6656
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

class node {
public:
	int parent,children[2],sib,val;
	node() {
		parent = -1;
		children[0] = -1;
		children[1] = -1;
		sib = -1;
		val = -1;
	}
	int deg() {
		int c = 0;
		for(int i=0;i<2;i++)if(children[i]!=-1)c++;
		return c;
	}
	string typ() {
		if(parent == -1)return "root";
		else if(deg() == 0)return "leaf";
		else return "internal node";
	}
};

int n = 0,c = 0;
node d[600000];

void pre(int i) {
	cout << " " << d[i].val;
	if(d[i].children[0] != -1) pre(d[i].children[0]);
	if(d[i].children[1] != -1) pre(d[i].children[1]);
}

void ino(int i) {
	if(d[i].children[0] != -1)ino(d[i].children[0]);
	cout << " " << d[i].val;
	if(d[i].children[1] != -1)ino(d[i].children[1]);
}

void pos(int i) {
	if(d[i].children[0] != -1)pos(d[i].children[0]);
	if(d[i].children[1] != -1)pos(d[i].children[1]);
	cout << " " << d[i].val;
}

void ins(int v) {
	d[c].val = v;
	if(c == 0){c++;return;}
	int h = 0;
	while(1) {
		int g;
		if(d[h].val < v) {
			g = d[h].children[1];
			if(g == -1) {
				d[h].children[1] = c;
				break;
			} else {
				h = g;
			}
		} else {
			g = d[h].children[0];
			if(g == -1) {
				d[h].children[0] = c;
				break;
			} else {
				h = g;
			}
		}
	}
	c++;
}

int main(void) {
	cin >> n;
	string s;
	int t;
	for(int i = 0;i < n;i++) {
		cin >> s;
		if(s == "insert") {cin >> t;ins(t);}
		else {ino(0);cout << endl;pre(0);cout << endl;}
	}
}



Measured memory_bytes: 14800
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int head[maxn], cnt = 1, inq[maxn], n, m, d[maxn], flag;
struct Node {int v, nxt, w;} G[maxn << 1];
void ins(int u, int v, int w) {G[cnt] = (Node) {v, head[u], w}; head[u] = cnt++;}
void spfa(int x, int col) {
	if(flag) return;
	inq[x] = col;
	for (int i = head[x]; i; i = G[i].nxt) {
		int v = G[i].v;
		if(d[v] > d[x] + G[i].w) {
			d[v] = d[x] + G[i].w;
			if(!inq[v]) spfa(v, col);
			if(flag) return;
			else if(inq[v] == col) {flag = 1; return;}
		}
	}
	inq[x] = 0;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z); ins(y, x, -z); ins(x, y, z);
	}
	memset(d, 0x3f, sizeof d); 
	for (int i = 1; i <= n; ++i) {
		spfa(i, i);
		if(flag) {puts("No"); break;}
	}
	if(!flag) puts("Yes");
	return 0;
}

Measured memory_bytes: 11392
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 9223372036854775807

signed main()
{
    int k;
    cin >> k;
    int r = 0;
    queue<int> q;
    for (int i = 1; i < 10; i++)
    {
        r++;
        q.push(i);
        if (r == k)
        {
            cout << q.back() << endl;
            return 0;
        }
    }

    while (r < k)
    {
        int n = q.front();
        q.pop();
        int t = n % 10;
        if (t - 1 >= 0)
        {
            q.push(n * 10 + t - 1);
            r++;
            if (r == k)
            {
                cout << q.back() << endl;
                return 0;
            }
        }
        q.push(n * 10 + t);
        r++;
        if (r == k)
        {
            cout << q.back() << endl;
            return 0;
        }
        if (t + 1 < 10)
        {
            q.push(n * 10 + t + 1);
            r++;
            if (r == k)
            {
                cout << q.back() << endl;
                return 0;
            }
        }
    }
    /*
    map<int, bool> flag;
    flag[0] = 1;
    int keta = 1;

    for (int i = 1; i <= 3234566667; i++)
    {
        if (i % (keta * 10) == 0)
            keta *= 10;
        if (keta > 1)
        {
            if (flag[i % keta] == 1 && abs(i / keta - (i % keta) / (keta / 10)) <= 1)
            {
                r++;
                flag[i] = 1;
            }
        }
        else
        {
            r++;
            flag[i] = 1;
        }
        if (r == k)
        {
            cout << i << endl;
            return 0;
        }
    }
    */
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(max(c,max(a,b))==7&&min(a,min(b,c))==5&&a+b+c==17)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

class BIT {
public:
	int size_ = 1;
	vector<int> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos += 1;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		int s = 0; pos += 1;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

// 入力
int N, Q;
int C[1 << 19];
int L[1 << 19], R[1 << 19];

// 出力
int Answer[1 << 19];

// その他の変数
vector<int> G[1 << 19];
vector<pair<int, int>> H[1 << 19];
vector<pair<int, int>> J[1 << 19][2];

int main() {
	// 入力
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
	for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);

	// 前処理
	for (int i = 1; i <= N; i++) G[C[i]].push_back(i);
	for (int i = 1; i <= Q; i++) H[L[i]].push_back(make_pair(R[i], i));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= G[i].size(); j++) {
			int cl = 1, cr = N;
			if (j >= 1) cl = G[i][j - 1] + 1;
			if (j < G[i].size()) cr = G[i][j] - 1;
			if (cl > cr) continue;
			J[cl][0].push_back(make_pair(cl, cr));
			J[cr][1].push_back(make_pair(cl, cr));
		}
	}

	// 平面走査
	BIT Z; Z.init(N + 2);
	for (int i = 1; i <= N; i++) {
		for (pair<int, int> j : J[i][0]) { Z.add(j.first, 1); Z.add(j.second + 1, -1); }
		for (pair<int, int> j : H[i]) { Answer[j.second] = N - Z.sum(j.first); }
		for (pair<int, int> j : J[i][1]) { Z.add(j.first, -1); Z.add(j.second + 1, 1); }
	}

	// 出力
	for (int i = 1; i <= Q; i++) printf("%d\n", Answer[i]);
	return 0;
}

Measured memory_bytes: 127428
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include <queue>

using namespace std;

void solve(int n){
	int a[51];
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int beg = a[0];
	int cur = a[0];
	bool first = true;
	for(int i=1;i<n;i++){
		if(cur+1 == a[i]){
			cur++;
		}else{
			// ??????
			if(first){
				first = false;
			}else{
				printf(" ");
			}
			if(beg==cur){
				printf("%d",beg);
			}else{
				printf("%d-%d",beg,cur);
			}
			beg = a[i];
			cur = a[i];
		}
	}
	// ??????
	if(first){
		first = false;
	}else{
		printf(" ");
	}
	if(beg==cur){
		printf("%d",beg);
	}else{
		printf("%d-%d",beg,cur);
	}
	printf("\n");
}

int main(){
	while(true){
		int n;
		scanf("%d",&n);
		if(n==0)break;
		solve(n);
	}
	return 0;
}

Measured memory_bytes: 1192