akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
using namespace std;
string s;
int ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;
	ans=s.length();
	for(char c='a';c<='z';c++){
		string t[2];
		int cur=0,cnt=0;
		t[0]=s;
		while(t[cur].length()>1){
			bool frog=true;
			t[cur^1].clear();
			for(int i=0;i<t[cur].length()-1;i++){
				if(t[cur][i]!=c || t[cur][i+1]!=c)frog=false;
				if(t[cur][i]==c || t[cur][i+1]==c)t[cur^1]+=c;
				else t[cur^1]+=t[cur][i];
			}
			if(frog)break;
			cnt++;
			cur^=1;
		}
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0

    lst1 = [0] * n
    lst2 = [0] * n

    for i in range(1, n+1):
        p = i - a[i-1]
        q = i + a[i-1]

        if 0 <= p < n:
            lst1[p] += 1
        if 0 <= q < n:
            lst2[q] += 1

    for i in range(n):
        cnt += lst1[i] * lst2[i]

    print(cnt)

if __name__ == '__main__':
    main()


Measured memory_bytes: 32368
r, c = map(int, input().split())
a = []
csum = []

for i in range(r):
    a.append(list(map(int,input().split())))
    a[i].append(sum(a[i]))
for i in range(r):
    print(' '.join(list(map(str,a[i]))))

for j in range(c+1):
    su=0
    for i in range(r):
        su+=a[i][j]
    csum.append(su)
print(' '.join(list(map(str,csum))))


Measured memory_bytes: 5704
n,p=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*2 for i in range(n+1)]
dp[0][0]=1
dp[0][1]=0
for i in range(1,n+1):
	if a[i-1]%2==1:
		dp[i][1]=dp[i-1][0]+dp[i-1][1]
		dp[i][0]=dp[i-1][1]+dp[i-1][0]
	else:
		dp[i][1]=dp[i-1][1]*2
		dp[i][0]=dp[i-1][0]*2
print(dp[n][p])
	

Measured memory_bytes: 38384
#include <iostream>
using namespace std;
int main(){
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=n-1;i>=0;i--){
        cout<<a[i];
        if(i)cout<<" ";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3132
b = [0,0,0,0]

while line = gets
n1,n2 = line.chomp.split(",")
if n2 == "A"
  b[0] += 1
  elsif n2 == "B"
  b[1] += 1
  elsif n2 == "AB"
  b[2] += 1
  elsif n2 == "O"
  b[3] += 1
end
end
puts b


Measured memory_bytes: 6876
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
const ll MOD = 1000000007;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    string N;
    cin>>N;
    
    if(N.length()>=4&&N[0]=='Y'&&N[1]=='A'&&N[2]=='K'&&N[3]=='I'){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    if((abs(a-b))%2){
        cout << "IMPOSSIBLE"<<endl;
    }
    else{
        cout << (a+b)/2<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int n, k, x[100000], ans = INT_MAX;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    for(int i = 0; i <= n - k; i++){
        ans = min(ans, x[i+k-1] - x[i] + min(abs(x[i]), abs(x[i+k-1])));
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	int i, j;
	for (i = 1; i <= 9; i++) {
		for (j = 1; j <= 9; j++) {
			cout<<i<<'x'<<j<<'='<<i*j<<'\n';
		}
	}
	return 0;
}

Measured memory_bytes: 3104
#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	priority_queue<int>q;
	int m,n,t,i;
	long long s=0;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>t;
		q.push(t);
	}
	while(m>0){
		t=q.top()/2;
		q.push(t);
		q.pop();
		m--;
	}
	while(!q.empty()){
		s+=q.top();
		q.pop();
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 892
def main():
    S = input()
    dp = [0]*(len(S)+1)
    for i in range(len(S)):
        if(S[i]=='A' or S[i]=='C' or S[i]=='G' or S[i]=='T'):
            dp[i+1] = dp[i]+1
    print(max(dp))
main()

Measured memory_bytes: 2940
def p(b):
    print(*box[b])

n, q = map(int, input().split())
box = [[]for i in range(n)]
for _ in range(q):
    a, b, *c = map(int, input().split())
    if a == 0:
        box[b] += [c[0]]
    elif a == 1:
        p(b)
    else:
        box[b] = []



Measured memory_bytes: 29760
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

struct War {
	int left, right;
	bool operator < (const War& b) const{
		return right < b.right;
	}
};

War X[100010];
int main()
{
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> X[i].left >> X[i].right;
	}
	sort(X, X + M);
	int ans = 0;
	int before_break = 0;
	for (int i = 0; i < M; i++) {
		if (!(X[i].left <= before_break && X[i].right >= before_break)) {
			ans++;
			before_break = X[i].right - 1;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#import
#import math
#import numpy as np
#= int(input())
S = input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

s = S[0]

r = 0

for i in range(1, len(S)):
    if s != S[i]:
        r += 1

    s = S[i]

print(r)

Measured memory_bytes: 9176
#include <iostream>

using namespace std;

void buble_sort(int high[]){
    int i,j,v;

    for(i = 0;i < 9;i++){
        v = i;
        for(j = i;j <= 9;j++){
            if(high[v] < high[j]){
                v = j;
            }
        }
        int box = high[i];
        high[i] = high[v];
        high[v] = box;

    }
}

int main() {
    int i,high[10];

    for (i = 0;i <= 9;i++){
        cin >> high[i];
    }

    buble_sort(high);

    for(i = 0;i <= 2;i++){
        cout << high[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
typedef long long ll;
typedef vector<int> vi;
typedef unsigned long ul;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef set<int> si;
typedef multiset<int> mi;
 
const ll INF = 1e18;
const int MOD = 1e9+7;

int main() {
	
	int N;
	cin>>N;
	
	vl L(N);
	for(ll&num : L) cin>>num;
	
	int ans=0;
	
	for(int i=0; i<N; ++i) {
		for(int j=i+1; j<N; ++j) {
			if(L[i]==L[j]) continue;
			for(int k=j+1; k<N; ++k) {
				if(L[j]==L[k] || L[i]==L[k]) continue;
				ll sum=L[i]+L[j]+L[k];
				ll longest=max({L[i],L[j],L[k]});
				if(longest>=(sum-longest)) continue;
				else ++ans;
				
				//cout<<i<<" "<<j<<" "<<k<<"\n";
				
			}
		}
		
	}
	
	cout<<ans<<"\n";
	return 0;
	
}




Measured memory_bytes: 3624
//Getting Started - Insertion Sort
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		 int n =Integer.parseInt(in.readLine());

		 String[] data = in.readLine().split(" ");

//		 int n =6;
//		 String[] data = "5 2 4 6 1 3".split(" ");

		 
		 int[] A = new int[n];
		 
		 for(int i=0;i<n;i++){
			 A[i]=Integer.parseInt(data[i]);
		 }
		 
		 
		 System.out.print(A[0]); 
		 for(int k=1;k<n;k++){
			 System.out.print(" " + A[k]);
		 }
		 System.out.println(); 
		 
		 for(int i=1;i<n;i++){

			 int v= A[i];
			 
			 int j=i-1;
			 
			 while( j>=0&&A[j]>v){
				 
				 A[j+1]=A[j];
				 j--;
			 }
			 A[j+1]=v;
			 
			 System.out.print(A[0]); 
			 for(int k=1;k<n;k++){
				 System.out.print(" " + A[k]);
			 }
			 System.out.println(); 
		 }
		 
	}
}

Measured memory_bytes: 23880
import collections


def main():
    n = int(input())
    abList = [0] * n
    for i in range(n):
        abList[i] = list(map(int, input().split()))
    abList.sort(key=lambda x: x[0], reverse=True)
    print(sum(abList[0]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 29012
n,k = map(int, input().split())
a = list(map(int, input().split()))

dp = [0]*(k+1)

for i in range(a[0]):
    dp[i] = 2

for i in range(a[0],k+1):
    for j in a:
        if(j > i):
            dp[i] = 2
            break
        if(dp[(i-j)]==2):
            dp[i] = 1
            break
        dp[i] = 2

if(dp[k] == 1):
    print('First')
else:
    print('Second')

Measured memory_bytes: 42988
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
D = [0] * (10 ** 5 + 1)
for i in range(N):
    D[A[i]] += 1

Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    S += (C - B) * D[B]
    print(S)
    
    D[C] += D[B] 
    D[B] = 0

Measured memory_bytes: 20844
n=int(input())
k=0
c=0
while True:
    if c+1<=n<=26**(k+1)+c:
        k+=1
        break
    k+=1
    c+=26**k

if k==1:
    print(chr(96+n))
    exit()

l=[]
n-=c #その桁数の何番めか
for i in range(1,k+1):
    k1=n//26**(k-i)
    l.append(k1)
    n-=26**(k-i)*(k1-1)

l1=[]
for i in range(1,len(l)+1):
    if l[-i]>=27:
        l[-(i+1)]+=1
        l[-i]-=26
    l1.append(chr(96+l[-i]))

l2=[]
for i in range(1,len(l1)+1):
    l2.append(l1[-i])
print(''.join(l2))

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

int main()
{
  int64_t N, r = 0, b = 0;
  cin >> N;
  char c;
  for (int i = 0; i < N; i++)
  {
    cin >> c;
    c == 'R' ? r++ : b++;
  }
  cout << (r > b ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define fst first
#define snd second
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << endl; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  ll h, w, n; cin >> h >> w >> n;

  map<P, int> cnt;

  rep(_, n) {
    int a, b; cin >> a >> b;
    --a; --b;
    rep(i, 3) rep(j, 3) {
      if (a-i >= 0 && a-i < h-2 && b-j >= 0 && b-j < w-2) ++cnt[P(a-i, b-j)];
    }
  }

  Vll ans(10);
  for (auto &e : cnt) ++ans[e.snd];
  ans[0] = (w-2) * (h-2);
  rep2(i, 1, 10) ans[0] -= ans[i];

  cout << ans;
  return 0;
}


Measured memory_bytes: 56576
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
	long int i, j;
	long int n, k;
	long int count = 0;;
	long int h[100000];
	
	scanf("%ld%ld", &n, &k);
	
	for(i = 0; i < n; i++) {
		scanf("%ld", &h[i]);
		if(h[i] >= k) {
			count++;
		}
	}
	
	printf("%ld\n", count);
	
	return 0;
}


Measured memory_bytes: 896
N, M = map(int, input().split())                       # 区間の数

imos = [0]*(10**5+2)

for _ in range(M):
    a, b = map(int, input().split())    # 区間は閉区間 [a,b] で与えられる
    imos[a] += 1
    imos[b+1] -= 1                      # 半開区間を作るために b+1 としておく点に注意。区間を使った回数を聞かれた場合はまた変わるので注意。

res = [0]
for k in imos:
    res.append(res[-1] + k)

print(res.count(M))


Measured memory_bytes: 81448
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "boost/multi_array.hpp"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)

//時間が厳しいとき使う
#define INI(...) int __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#pragma endregion RegionDefs

void solve()
{
    IN(n, m);
    vector<pair<int,int>> v;
    rep(i, m)
    {
        IN(s, c);
        v.emplace_back(s, c);
    }
    if (n == 1)
    reps(i, 0, 10)
    {
        for (auto&& p : v)
        {
            if (i != p.second)
            {
                goto end3;
            }
        }
        cout << i << endl;
        return;
        end3:;
    }
    else if (n == 2)
    reps(i, 1, 10)
    {
        rep(j, 10)
        {
            for (auto&& p : v)
            {
                if (p.first == 1 && i != p.second || p.first == 2 && j != p.second)
                {
                    goto end;
                }
            }
            cout << i << j << endl;
            return;
            end:;
        }
    }
    else if (n == 3)
    reps(i, 1, 10)
    {
        rep(j, 10)
        {
            rep(k, 10)
            {
                for (auto&& p : v)
                {
                    if (p.first == 1 && i != p.second || p.first == 2 && j != p.second || p.first == 3 && k != p.second)
                    {
                        goto end2;
                    }
                }
                cout << i << j << k << endl;
                return;
                end2:;
            }
        }
    }
    cout << -1 << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> trp;
typedef vector<ll> vi;
typedef vector<pll> vp;

#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define f1(i,n)     for(ll i=1;i<=n;i++)
#define fs(i,s)     for(ll i=0;i+1<=s.length();i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define fuv(i,a)    for(ll i=0;i<a.size();i++)
#define fdv(i,a)    for(ll i=(ll)a.size()-1;i>=0;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<endl
#define pr2(a,b)    cout<<a<<" "<<b<<endl
#define rpr(a)      return cout<<a<<endl,0
#define prY         cout<<"YES"<<endl
#define prN         cout<<"NO"<<endl
#define bit(n,i)    (((n)>>(i))&1)
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(all(a),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()		
#define ast(x,a,b)  assert(x>=a and x<=b)				
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define	mp3(a,b,c)  make_pair(a,make_pair(b,c))
#define se          second
#define fi          first 
#define sse         second.second
#define sfi         second.first
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline ll mnz(ll& a,ll b){return a=(a>b?b:a);}
inline ll mxz(ll& a,ll b){return a=(a<b?b:a);}
inline string toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=998244353,oo=1e17,MAXN=1e5;


ll A[MAXN+5],B[MAXN+5];
ll fac[MAXN+5];
ll inline mu(ll a,ll x){
	if(!x)re 1;
	if(x&1)re a*mu(a,x-1)%Base;
	else{
		ll t=mu(a,x>>1);
		re t*t%Base;
	}
}
ll Solves(){
	
	ll n,m,k,cnt=0,ans=1,x,y,q,c,sum=0,v,t;
	// PROCESS IN HERE
	sc(n);
	f1(i,n)sc(A[i]),B[A[i]]++;
	if(A[1]!=0)rpr(0);
	fu(i,2,n)if(!A[i])rpr(0);
	
	f1(i,n){
		if(B[i])ans=(ans*(mu(B[i-1],B[i])%Base))%Base;
	}
	pr(ans);
	
	
	
	re 0;
	// Hack it if you can :)
}

int main(){
	//INPUT;
	if(fopen("locin.txt", "r"))INPUT;
	ll JUDGE_ONLINE = 1;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll test=1;
//	sc(test);
	fu(T,1,test){
//		cout<<"Case #"<<T<<": ";
		Solves();
	}
	if (!JUDGE_ONLINE) cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";  
		
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
vector<ll> v1[100005];
pair<ll,ll> dp[100005];
pair<ll,ll> dfs(ll i,ll j)
{
    pair<ll,ll> k3={-1,-1};
    if(dp[i]!=k3) return dp[i];
    ll sum1=1,sum2 = 1;
    for(auto &k:v1[i])
    {
        if(k==j) continue;
        sum1=(sum1%mod*(dfs(k,i).second+dfs(k,i).first)%mod)%mod;
        sum2=(sum2%mod*dfs(k,i).first%mod)%mod;
    }
    return dp[i]=make_pair(sum1,sum2); 
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	memset(dp,-1,sizeof dp);
	ll N,i,x,y;
	cin>>N;
	for(i=0;i<N-1;i++) { cin>>x>>y; v1[x].push_back(y); v1[y].push_back(x);}
	dfs(1,-1);
	ll ans=(dp[1].first+dp[1].second)%mod;
	ans=(ans+mod)%mod;
	cout<<ans<<endl;
	return 0;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

map<string,int> table;
map<string,vector<string>> recipe;
map<string,int> opt;

int dfs(string& name,map<string,int>& state){
    state[name]=1;
    int& res=opt[name];
    res=table[name];
    if(recipe[name].empty()) return res;

    int tmp=0;
    for(auto &next:recipe[name]){
        if(state[next]==1) tmp+=table[next];
        else if(state[next]==2) tmp+=opt[next];
        else tmp+=dfs(next,state);
    }
    res=min(res,tmp);

    state[name]=2;
    return res;
}

void solve(){
    int n;
    while(true){
        cin >> n;
        if(!n) break;

        table.clear();
        recipe.clear();
        opt.clear();

        rep(i,0,n){
            string name;
            int cost;
            cin >> name >> cost;
            table[name]=cost;
            opt[name]=inf;
        }

        int m;
        cin >> m;
        rep(i,0,m){
            string name1;
            int k;
            cin >> name1 >> k;
            rep(j,0,k){
                string name2;
                cin >> name2;
                recipe[name1].push_back(name2);
            }
        }

        string str;
        cin >> str;
        map<string,int> state;
        cout << dfs(str,state) << endl;
    }
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	solve();
	return 0;
}

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

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n1 = s.size();
    int n2 = t.size();
    int pos = -1, i, j;
    for(i = 0; i < n1; i++){
        if(s[i] == '?' || s[i] == t[0]){
            j = 0;
            while(j < n2){
                if((i + j < n1) && (s[i + j] == t[j] || s[i + j] == '?'))
                    j++;
                else
                    break;
            }
            if(j == n2){
                pos = i;
            }
        }
    }
    if(pos == -1){
        cout << "UNRESTORABLE";
    }
    else{
        for(i = pos, j = 0; i < pos + n2, j < n2; i++, j++){
            if(s[i] == '?')
                s[i] = t[j];
        }
        for(i = 0; i < n1; i++){
            if(s[i] == '?')
                s[i] = 'a';
        }
        cout << s;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

const int   INF=1e9;
long long mod=1000000007;
using namespace std;
int N,M;
int a[1050],b[1050],c[1050][20];



template<class T>
inline bool chmin(T &a, T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
void input(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        cin>>a[i]>>b[i];
        for(int j=1;j<=b[i];j++)cin>>c[i][j];
    }
}

void solve(){
    input();
    vector<int>dp(5000,INF);
    //dp[i][j]:=i+1番目以降の鍵は購入せずに
    //状態をjにするのに必要な最小費用
    dp[0]=0;
    for(int item=1;item<=M;item++){
        int now=0;
        for(int j=1;j<=b[item];j++){
            now |=(1<<(c[item][j]-1));
            //開けられたものを数えたしていく
        }
        //Nビット分シフトして
        for(int bits=0;bits<(1<<N);bits++){
            //bit表現なのでorで和をとっていく
                chmin(dp[bits | now],dp[bits]+a[item]);
        }
    }
    //全ての宝箱を開けることができない時
    if(dp[(1<<N)-1]==INF)dp[(1<<N)-1]=-1;
    cout<<dp[(1<<N)-1]<<endl;
    return;
}
//ABC142E
int main(){
    solve();

 return 0;
}
/*
2 3
10 1
1
15 1
2
30 2
1 2

25


12 1
100000 1
2

-1

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

69942
*/

Measured memory_bytes: 384
#include <iostream>
     
    int main()
    {
        int n;
        std :: cin >> n;
     
        long long monsters[n + 1];
        for(int i = 0 ; i <= n ; i++)
            std :: cin >> monsters[i];
     
        long long heroes[n];
        for(int i = 0 ; i < n ; i++)
            std :: cin >> heroes[i];
     
        long long d = 0;
     
        for(int i = 0 ; i < n ; i++)
        {
            if(monsters[i] >= heroes[i])
            {
                d += heroes[i];
                continue;
            }
            else
            {
                d += monsters[i];
                heroes[i] -= monsters[i];
                if(monsters[i + 1] >= heroes[i])
                {
                    d += heroes[i];
                    monsters[i + 1] -= heroes[i];
                    continue;
                }
                else
                {
                    d += monsters[i + 1];
                    monsters[i + 1] = 0;
                }
            }
        }
     
        std :: cout << d << '\n';
    }

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e4 + 7;
int dp[N][103][2];
const int MOD = 1e9 + 7;
#define pb push_back

int recur(int id, string n, int k, int flg, int sum, vector<int> res)
{
    if(id == n.length())
    {
        if(sum == 0)
        {
            // for(auto i : res)
            //     cout << i;
            // cout << "\n";
            return 1;
        }
        return 0;
    }

    if(dp[id][sum][flg] != -1)
    {
        //cout << id << " " << sum << " " << flg << "\n";
        return dp[id][sum][flg] % MOD;
    }

    int ans = 0;

    if(flg)
    {
        int j = n[id] - '0';

        for(int i = 0; i <= j; i++)
        {
            if(i == j)
            {
                //res.pb(i);
                ans = (ans + recur(id + 1, n, k, 1, (sum + i) % k, res)) ;
                //res.pop_back();
            }
            else
            {
                //res.pb(i);
                ans = (ans + recur(id + 1, n, k, 0, (sum + i) % k, res)) ;
                //res.pop_back();
            }
        }
    }
    else
    {
        for(int i = 0; i <= 9; i++)
        {
            //res.pb(i);
            ans = (ans + recur(id + 1, n, k, 0, (sum + i) % k, res)) ;
            //res.pop_back();
        }
    }

    return dp[id][sum][flg] = ans % MOD;
}

int32_t main()
{
    string n;
    cin >> n;
    int k;
    cin >> k;
    
    memset(dp, -1, sizeof(dp));
    vector <int> v;
    cout << (recur(0, n, k, 1, 0, v) - 1 + MOD) % MOD<< "\n";
}


Measured memory_bytes: 116480
using System;

namespace q2
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int sum = 0;
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                if (S[i] == 'A') {
                    cnt = 1;
                }
                else if (cnt == 1 && S[i] == 'B') {
                    cnt = 2;
                }
                else if (cnt == 2 && S[i] == 'C') {
                    cnt = 0;
                    sum++;
                }
                else {
                    cnt = 0;
                }
            }
            Console.WriteLine(sum);
        }
    }
}


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

//定义数组
const int SZ=1e2+4;//定义数组大小
long long sj[SZ]={};//定义数组 
 
int main() {
	//读取数据
	long long n;
	cin>>n;
	
	int i;
	for (i=1; i<=n; i++) {
		cin>>sj[i];
	}

	long long ans=0;
	int j,k;
	for (i=1; i<=n; i++) {
		for (j=i+1; j<=n; j++) {
			for (k=j+1; k<=n; k++) {
				if (sj[i]!=sj[j] && sj[j]!=sj[k] && sj[i]!=sj[k] && sj[i]+sj[j]>sj[k] && sj[i]+sj[k]>sj[j] && sj[j]+sj[k]>sj[i]) {
					ans++;
				}
			}
		}
	}	
	
	cout<<ans<<"\n"; 
	
	return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define FOR(i,a,b)  for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n)    FOR(i,0,n)
#define RER(i,n)    FOR(i,0,(n+1))
#define pb          push_back
#define mp(a,b)     make_pair((a),(b))
#define mset(m,v)   memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pair<ll, ll> > vpll;
typedef vector<string> vs;
typedef long double ld;
const double EPS    = 1e-10;
const int INF       = 1e+9;
const double PI     = acos(-1);


auto main() -> int
{
    int x, y;
    cin >> x >> y;

    vector<vector<int> > g;
    g.push_back(vector<int>{1, 3, 5, 7, 8, 10, 12});
    g.push_back(vector<int>{4, 6, 9, 11});
    g.push_back(vector<int>{2});

    for ( auto h : g ) {
        if ( find(begin(h), end(h), x) != h.end() ) {
            if ( find(begin(h), end(h), y) != h.end() ) {
                cout << "Yes" << endl;
                break;
            } else {
                cout << "No" << endl;
                break;
            }
        }
    }

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

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

    int n, m; cin >> n >> m;
    vi p(n); for(auto& e : p) cin >> e, e--;
    vi x(m), y(m);
    rep(i, m) cin >> x[i] >> y[i], x[i]--, y[i]--;

    UnionFind uf(n);
    rep(i, m){
        uf.unionSet(x[i], y[i]);
    }

    int res = 0;
    rep(i, n){
        if(uf.findSet(i, p[i])) res++;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

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

    for (ll h = 1; h < 3501; h++) {
        for (ll n = 1; n < 3501; n++) {
            if (4 * h * n - N * n - N * h <= 0) continue;
            if (N * h * n % (4 * h * n - N * n - N * h) == 0) {
                cout << h << " " << n << " " << N * h * n / (4 * h * n - N * n - N * h) << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int n; cin>>n;
  vector<int>p(n);
  for(int i=0;i<n;i++) cin>>p.at(i);
  int cnt=0;
    for(int i=1;i<n-1;i++){
    if(min(p.at(i-1),min(p.at(i),p.at(i+1)))!=p.at(i)&& max(p.at(i-1),max(p.at(i),p.at(i+1)))!=p.at(i))
    cnt++;
    }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
x=int(input())
if x==1:
    print(0,-1)
    exit()
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
li=sorted(make_divisors(x))
for i in range(len(li)):
    j=li[i]
    k=j//2
    while pow(k,5)-pow(k-j,5)<=x:
        if pow(k,5)-pow(k-j,5)==x:
            print(k,k-j)
            exit()
        else:
            k+=1
    continue




Measured memory_bytes: 9288
//Never stop trying
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

#define dbg(x) cerr << " - " << #x << " : " << x << endl;
#define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;

void IO() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}


int32_t main() {
	boost; IO();

	int N; cin>>N;
	vi a(N),b(N),c(N),d(N);

	FOR(i,0,N){
		int x,y; cin>>x>>y;
		a[i]=x+y;
		b[i]=x-y;
		c[i]=-x+y;
		d[i]=-x-y;
	}

	sort(all(a)); sort(all(b)); sort(all(c)); sort(all(d));

	cout << max(max(a[N-1]-a[0],c[N-1]-c[0]),max(b[N-1]-b[0],d[N-1]-d[0])) << endl;



	return 0;
}

/* Careful!!!
	.Array bounds
	.Infinite loops
	.Uninitialized variables / empty containers
	.Order of input

   Some insights:
	.Binary search
	.Graph representation
	.Write brute force code
	.Change your approach
*/


Measured memory_bytes: 9488
#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  if(a + b > c + d){
    cout << "Left" << endl;    
  } else if(a + b == c + d) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int ans = 0;
	int N;
	scanf("%d\n", &N);
	char s[N];
	scanf("%s\n", s);
	char search[] = "ABC";
	for (int i = 0; i < N - 2; i++) {
		bool f = true;
		for (int j = 0; j < 3; j++) {
			if (s[i + j] != search[j]) {
				f = false;
				break;
			}
		}
		if (f) ans++;
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 384
from bisect import bisect_left

N, M = map(int, input().split())
ab = [0]*M
for i in range(M):
    ab[i] = tuple(map(int, input().split()))
ab.sort()


used = [False]*M
count = 0
for i in range(M):
    if used[i]:
        continue
    head, tail = ab[i]
    used[i] = True
    j = i+1
    while j < M:
        h, t = ab[j]
        if tail <= h:
            break
        tail = min(tail, t)
        used[j] = True
        j += 1
    count += 1
print(count)


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

int main() {
  int N,M;
  cin>>N;
    M=N;
    int s=0;
   while(N>0){
    s+=N%10;
    N/=10;
  }
    if(M%s==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
  

Measured memory_bytes: 256
#ARC097-D
n,m=map(int,input().split())
P=list(map(int,input().split()))
edges=[list(map(int,input().split())) for _ in range(m)]

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(n+1)

    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
ans=0
for i,j in edges:
    uf.union(i,j)
for i in range(n):
    if uf.same_check(i+1,P[i]):
        ans+=1
print(ans)

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

using namespace std;

typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int arr[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << arr[k-1];

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<long long,long long> pll;

const int MAX=1e5+4;
int table[MAX];

int main(){ 
    int n,mask;
    cin >> n;
    int datos[n];
    int rta[n];
    for(int i=0;i<n;i++){
        cin >> datos[i];
    }
    mask=datos[0];
    for(int i=1;i<n;i++){
        mask=mask^datos[i];
    }
    for(int i=0;i<n;i++){
        rta[i]=mask^datos[i];
    } 
    for(int i=0;i<n;i++){
      if(i<n-1) cout << rta[i] << " ";
      else cout << rta[i] << endl;
    }
}

Measured memory_bytes: 5144
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <istream>
 
#define INPUT_FROM_FILE (0)
#if INPUT_FROM_FILE
#include <fstream>
#endif


 int main(int argc, char **argv){
	int n = 0;
	std::string buf;
 
#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
#endif
 
 
#if INPUT_FROM_FILE
	while(std::getline(ifs, buf)){
#else
	while(std::getline(std::cin, buf)){
#endif
		int count = 0;
		n = std::atoi(buf.c_str());

		for(int a = 0; a < 10; a++){
			for(int b = 0; b < 10; b++){
				for(int c = 0; c < 10; c++){
					for(int d = 0; d < 10; d++){
						if(a + b + c + d == n){
							count++;
						}
					}
				}
			}
		}
		std::cout << count << std::endl;
	}
    return 0;
}


Measured memory_bytes: 3168
/*
 * 	Heart beats fast
 * 		Colors and promises
 * 			How to be brave
 * 				How can I love when I am afraid to fall...
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define mod 1000000007
#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define f(i,n) for(int i=0;i<n;i++)
#define fp(i,k,n) for(int i=k;i<=n;i++)
#define fr(i,k,n) for(int i=k;i>=n;i--)
#define pb push_back
#define F first
#define S second
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
 
 
void solve()
{
  int n,lim;
  cin >> n >> lim;
  int wt[n+1],val[n+1];
  fp(i,1,n)
    cin >> wt[i] >> val[i]; 
  int dp[n+1][lim+1];
  
  fp(i,0,n)
   { 
       fp(w,0,lim)
       { 
           if(i==0 || w==0)
            dp[i][w]=0;
           else if(wt[i]<= w) 
              dp[i][w] = max(val[i] + dp[i-1][w-wt[i]],  dp[i-1][w]); 
           else
              dp[i][w] = dp[i-1][w]; 
       } 
   } 
      
  cout << dp[n][lim] << '\n';
  return ;
}

signed main()
{
   FAST;
	int T=1;
	// cin >> T;
	while(T--)
	{
		solve();
	}
    return 0;
}

Measured memory_bytes: 79232
from sys import stdin

W_MAX = 10000

n = int(stdin.readline().rstrip())
w = [int(x) for x in stdin.readline().rstrip().split()]
min_w = min(w)
idx = {}
for i, wi in enumerate(sorted(w)):
    idx[wi] = i

isVisited = [False]*n
cost = 0
for i in range(n):
    if isVisited[i]:
        continue

    cur = i
    cyc = []
    min_cyc = W_MAX
    while not isVisited[cur]:
        isVisited[cur] = True
        cyc.append(w[cur])
        min_cyc = min(min_cyc, w[cur])
        cur = idx[w[cur]]

    cost += min(sum(cyc) + (len(cyc)-2)*min_cyc, sum(cyc) + (len(cyc)+1)*min_w + min_cyc)

print(cost)



Measured memory_bytes: 5724
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n, m;std::cin >> n >> m;
  std::cout << (n*(n-1))/2 + (m*(m-1))/2 << '\n';
  return 0;
}


Measured memory_bytes: 888
import sys

inf = (1 << 31) - 1

def solve():
    n, q = map(int, sys.stdin.readline().split())

    sg = SegTree([0]*n)

    for qi in range(q):
        # print(sg.data)
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            x -= 1
            sg.add(x, y)
        else:
            x, y = x-1, y-1
            ans = sg.get_sum(x, y + 1, 0, 0, 2**sg.depth)
            print(ans)

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.depth = 0

        while 2**self.depth < self.n:
            self.depth += 1

        self.data = [0]*(2**(self.depth + 1) - 1)

        self.data[2**(self.depth) - 1:2**(self.depth) - 1 + self.n] = a[:]

        for i in range(2**self.depth - 2, -1, -1):
            self.data[i] = self.data[2*i + 1] + self.data[2*i + 2]

    def add(self, i, x):
        i += 2**self.depth - 1
        self.data[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.data[i] += x

    def get_sum(self, s, t, k, left, right):
        if t <= left or right <= s:
            return 0
        if s <= left and right <= t:
            return self.data[k]

        vl = self.get_sum(s, t, 2*k + 1, left, (left + right) // 2)
        vr = self.get_sum(s, t, 2*k + 2, (left + right) // 2, right)

        return vl + vr

if __name__ == '__main__':
    solve()

Measured memory_bytes: 13248
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<locale>
#include<cctype>

using namespace std;

int main() {
  cin.tie(0);
  string s;
  cin>>s;
  int ans=0;
  int kari=0;
  for(int i=0;i<s.length();i++){
    kari=0;
    for(int j=i;j<s.length();j++){
      if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T'){
        kari++;
      }
      else break;
    }
    if(ans<kari)ans=kari;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void dfs(int node,int parent,vector<vector<pair<int,ll> > >&adj,vector<ll>&dist)
{
	for(auto var : adj[node])
	{
		if(var.first!=parent){
			dist[var.first]=dist[node]+var.second;
			dfs(var.first,node,adj,dist);
		}
	}
}
int main()
{
	int n;
	cin>>n;
	vector<vector<pair<int,ll> > >adj(n+1);
	for(int i=1; i<n; i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		adj[a].push_back(make_pair(b,w));
		adj[b].push_back(make_pair(a,w));
	}
    vector<ll>dist(n+1);
    dfs(1,0,adj,dist);
    vector<int>color(n+1);
    for(int i=1; i<=n; i++){
    	if(dist[i]%2==0)
    	 color[i]=1;
    	else
    	 color[i]=0;
	}
	for(int i=1; i<=n; i++)
	 cout<<color[i]<<"\n";
	return 0;
}

Measured memory_bytes: 14848
# AGC023A - Zero-Sum Ranges
from collections import Counter
from itertools import accumulate


def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    C = Counter(list(accumulate(A)) + [0]).values()
    ans = sum(i * (i - 1) // 2 for i in C)
    print(ans)


if __name__ == "__main__":
    main()

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

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

  if (R < 1200) {
    cout << "ABC" << endl;
  } else if (1200 <= R && R < 2800) {
    cout << "ARC" << endl;
  } else if (2800 <= R)
    cout << "AGC" << endl;
}


Measured memory_bytes: 256