akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010,INF=1e18;
struct edge
{
	int a,b;
	bool operator < (const edge&e)const
	{
		if(a!=e.a)return a<e.a;
		return b<e.b;
	}
};
int n;
int to[N<<1];
int nxt[N<<1];
int val[N<<1];
int f[N];
int head[N];
int siz[N];
int dis[N];
vector<edge>g[N];
vector<edge>o;
int cnt=0ll;
void add(int u,int v,int w)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	val[cnt]=w;
	head[u]=cnt;
}
int a1,a2,b1,b2;
int get(int x,int y,int p)
{
	int l=0ll,r=g[y].size()-1;
	while(l<r-1)
	{
		int mid=(l+r)>>1;
		a2=g[y][mid].a,b2=g[y][mid].b;
		if(b1+a2+dis[x]+dis[y]<=p)l=mid;
		else r=mid;
	}
	a2=g[y][r].a,b2=g[y][r].b;
	if(b1+a2+dis[x]+dis[y]<=p)return r;
	a2=g[y][l].a,b2=g[y][l].b;
	if(b1+a2+dis[x]+dis[y]<=p)return l;
	return -1;
}
void work(int x,int t)
{
	o.clear();
	int u=0,v=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int p=to[i];
		if(p==f[x])continue;
		if(!u)u=p;
		else v=p;
	}
	if(siz[u]>siz[v])swap(u,v);
	int lenu=g[u].size(),lenv=g[v].size();
	if(lenu==0ll||lenv==0ll)return ;
	for(int i=0ll;i<lenu;i++)
	{
		a1=g[u][i].a,b1=g[u][i].b;
		if(get(u,v,t)==-1)continue;
		o.push_back((edge){a1+dis[u],b2+dis[v]});
		o.push_back((edge){b2+dis[v],a1+dis[u]});
	}
	sort(o.begin(),o.end());
	int leno=o.size();
	int maxn=INF;
	for(int i=0ll;i<leno;i++)
	{
		if(o[i].b<maxn)
		{
			g[x].push_back(o[i]);
			maxn=o[i].b;
		}
	}
}
void dfs(int u,int fa,int x)
{
	siz[u]=1ll;
	int son=0ll;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)continue;
		f[v]=u;
		dis[v]=val[i];
		dfs(v,u,x);
		siz[u]+=siz[v];
		son++;
		if(son==2ll)work(u,x);
	}
	if(son==0ll)g[u].push_back((edge){0ll,0ll});
}
bool check(int x)
{
	for(int i=1;i<=n;i++)g[i].clear();
	dfs(1,0,x);
	if(g[1].size()>0)return 1;
	return 0;
}
signed main()
{
	scanf("%lld",&n);
	int a,b;
	int all=0ll;
	for(int i=1;i<n;i++)
	{
		scanf("%lld %lld",&a,&b);
		add(i+1,a,b);
		add(a,i+1,b);
		all+=b;
	}
	int l=0ll,r=all;
	while(l<r-1)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid;
	}
	if(check(l))printf("%lld",l);
	else printf("%lld",r);
	return 0;
}
/*
7
1 1
1 1
2 1
2 1
3 1
3 1
*/

Measured memory_bytes: 70004
n=int(input())
ans=9999999999999
for i in range(1,int(n/2)+1):
  tempa=list(str(i))
  tempb=list(str(n-i))
  s=0
  for j in range(len(tempa)):
    s=s+int(tempa[j])
  for j in range(len(tempb)):
    s=s+int(tempb[j])
  ans=min(ans,s)
print(ans)


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

#define mx 100005
#define ll long long

int ar[mx];
char ch[mx];

int n,m,k,ii;

void solve()
{
    cin>>n>>m>>k;
    int re=0;
    for(int i=n;i<=m;i++)
    {
        if(i%k==0)re++;
    }
    cout<<re<<endl;
}

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   int t=1;
  // scanf("%d",&t);
   while(t--)solve();
   return 0;
}


Measured memory_bytes: 3592
n,k=map(int,input().split())
dp=[[0,0,0] for i in range(n)]
janken=list(map(int,input().split( )))
t=[0 if i=="r" else 1 if i=="s" else 2 for i in input()]
#直後の手を見て決める
for i in range(n):
    if i<k:
        for j in range(3):
            if (j+1)%3==t[i]:
                dp[i][j]=janken[j]
    else:
        #更新
        for j in range(3):
            #遷移の元
            for l in range(3):
                if j!=l:
                    if (j+1)%3==t[i]:
                        dp[i][j]=max(dp[i][j],janken[j]+dp[i-k][l])
                    else:
                        dp[i][j]=max(dp[i][j],dp[i-k][l])
ans=0
for i in range(n-k,n):
    ans+=max(dp[i])
print(ans)

Measured memory_bytes: 90764
#include "bits/stdc++.h"
using namespace std;

int main(){
	long long N;
	cin >> N;
	long long sum = 0;
for(long long x = 1; x<=N; x++){
	if(x%3!=0 && x%5!=0){
		sum+=x;
	}
}
cout << sum;
	

}
	
	


Measured memory_bytes: 3636
//C
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();

		long[] P = new long[5];

		long ans = 0;

		P[0] = sc.nextLong();

		long min = P[0];

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

			P[i] = sc.nextLong();

			min = Math.min(min, P[i]);

		}

		if(N%min==0) ans = N/min + 4;

		else ans = N/min + 5;

		System.out.println(ans);
	}

}


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

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;
}
bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}
int digsum(int n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}
int stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}

int main(void){
    string S;
    cin >> S;
    if(S[0]==S[1]&&S[1]==S[2])cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
    
}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>

using namespace std;

typedef long long ll;

int main() {
  int N, cnt2 = 0, cnt4 = 0;
  cin >> N;
  rep(i, N) {
    int a;
    cin >> a;
    if (a % 4 == 0) {
      cnt4++;
    } else if (a % 2 == 0) {
      cnt2++;
    }
  }
  if ((N - 1) - cnt4 * 2 - max(0, (cnt2 - 1)) <= 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#pragma region cp-helper
#include <bits/stdc++.h>
using namespace std;
#define AC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ii pair<int, int>
#define lll pair<ll, ll>
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define vll vector<lll>
#define vvl vector<vl>
#define vii vector<ii>
#define all(a) a.begin(), a.end()
#define qsort(a) sort(all(a))
#define qsortd(a) sort(all(a), greater<>())
#define qsortf(a, f) sort(all(a), f)
#define pb(n) push_back(n)
#define eb(n) emplace_back(n)
#define pp(a, b) emplace_back(make_pair(a, b))
#define umap unordered_map
#define nl '\n'
#define fileio(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)
#define qmod %mod
#define pls int
#define give main()
const int mod = 1000000007;
#pragma endregion

pls give {
    AC;
    int n, count=0;
    string s;
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        bool flag = false;
        for (int j=i; j<i+3; j++) {
            if (s[j] != "ABC"[j-i]) {
                flag = true;
                break;
            }
        }
        if (!flag) count++;
    }
    cout << count;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var march = []rune("MARCH")

func main() {
	n := getInt()
	cnt := [5]int{0, 0, 0, 0, 0}
	for i := 0; i < n; i++ {
		s := []rune(getString())

		for j, r := range march {
			if s[0] == r {
				cnt[j]++
			}
		}
	}

	cs := combi(5, 3)
	ans := 0
	for _, c := range cs {
		a := cnt[c[0]] * cnt[c[1]] * cnt[c[2]]
		ans += a
	}

	fmt.Println(ans)
}

func combi(n, r int) [][]int {
	c := make([]int, r)
	ret := make([][]int, 0)

	var recCombi func(n, r int, c []int)
	recCombi = func(n, r int, c []int) {
		if r == 0 {
			x := make([]int, len(c))
			copy(x, c)
			ret = append(ret, x)
		} else {
			if n < 0 {
				return
			}

			recCombi(n-1, r, c)

			c[r-1] = n
			recCombi(n-1, r-1, c)
		}
	}

	recCombi(n-1, r, c)
	return ret
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


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

int main() {
	int N, W;
	cin >> N >> W;
	vector<vector<long long>> Items(N, vector<long long>(2));
	for (int i = 0; i < N; i++) {
		cin >> Items[i][0] >> Items[i][1];
	}
	
	vector<vector<long long>> Knap(N, vector<long long>(W+1, 0));
	Knap[0][Items[0][0]] = Items[0][1];
	for (int i = 0; i < N - 1; i++) {
		for (int w = 0; w <= W; w++) {
			Knap[i + 1][w] = max(Knap[i + 1][w], Knap[i][w]);
			if (w + Items[i+1][0] <= W) {
				Knap[i + 1][w + Items[i + 1][0]] = max(Knap[i + 1][w + Items[i + 1][0]], Knap[i][w] + Items[i + 1][1]);
			}
		}
	}

	long long maxValue = Knap[N-1][0];
	for (int w = 1; w <= W; w++) {
		maxValue = max(maxValue, Knap[N - 1][w]);
	}
	cout << maxValue << endl;
}

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


long long cnt[5];
int main(){
    string S;
    string t = "MARCH";
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> S;
        for(int j = 0; j < 5; j++){
            if(S[0] == t[j]){
                cnt[j]++;
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < (1 << 5); i++){
        int num = 0;
        for(int j = 0; j < 5; j++){
            num += (i >> j) % 2;
        }
        if(num != 3){
            continue;
        }
        long long pattern = 1;
        for(int j = 0; j < 5; j++){
            if((i >> j) & 1){
                pattern *= cnt[j];
            }
        }
        ans += pattern;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll mod = 1000000007;
ll INF = 1000000009;


int t;
vector<int> d;
bool judge(int x){
    bool b=true;
    while(x!=0){
        for(auto p:d){
            //cout << p << " " << x%10 << endl;
            if(p==x%10) b=false;
        }
        x = x/10;
    }
    return b;
}


void solve(){
    int n,k;
    cin >> n >> k;
    rep(i,k){
        int tmp;
        cin >> tmp;
        d.emplace_back(tmp);
    }

    int i = n;
    while(!judge(i)){
        //cout << i << endl;
        i++;
    }
    cout << i << endl;
}

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


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

int main(){
  long s;
  cin >> s;
  int x, z, ans;
  ans = 999;
  while(s > 99){
    x = s % 1000;
    z = max(753 - x, x - 753);
    s = s / 10;
    ans = min(z, ans);

  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import copy
n = int(input())
a = []
for s in range(n):
    a.append(int(input()))
m = max(a)
b = sorted(a)
if b[-2] == m:
  for c in range (n):
    print(m)
else:
  for t in range(n):
    if a[t] == m:
      b = copy.copy(a)
      b[t:t+1] = []
      print(max(b))
    else:
      print(m)

Measured memory_bytes: 16092
n = int(input())
h = list(map(int, input().split()))

ans = 'Yes'
for i in range(-1, -n, -1):
  if h[i]+1 == h[i-1]:
    h[i-1] -= 1
  elif h[i-1] - h[i] > 1:
    ans = 'No'
    break

print(ans)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

ll d = 1e9 + 7;

ll gyaku(ll num){
    ll jou = d-2;
    ll ret = 1;
    ll kake = num;
    while(jou != 0){
        if (jou%2 == 1){
            ret *= kake;
            ret %= d;
        }
        kake = (kake*kake) % d;
        jou /= 2;
    }
    return ret;
}


int main(void){
    ll n; cin >> n;
    vector <ll> cs;
    REP(i, n){
        ll c; cin >> c;
        cs.push_back(c);
    }
    sort(cs.begin(), cs.end());
    vector <ll> twos = {1};
    REP(i, n){
        twos.push_back((twos[i] * 2) % d);
    }
    ll ans = 0;
    dumparr(twos)
    REP(i, n){
        ll tasu = 0;
        tasu += twos[n-1];
        tasu += ((n-1-i)*twos[n-2]) % d;
        tasu %= d;
        //dump(tasu)
        ans += tasu*cs[i] % d;
        ans %= d;
        //dump(ans)
    }
    ans *= twos[n];
    ans %= d;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4848
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, k;
  cin >> n >> k;
   vector<int> anko(n);
 
  for (int i = 0; i < n; i++) {
    cin >> anko.at(i);
  }
  sort(anko.begin(), anko.end());
  int x = 0;
  for (int j = 0; j < k; j++) {
    x = x + anko.at(j);
  }
  cout << x << endl;
}


Measured memory_bytes: 3472
N,M = map(int,input().split())
AB = []

for _ in range(N):
    A, B = map(int,input().split())
    AB.append([A,B])
    
AB.sort()

cnt = 0
money = 0

for i in range(N):
    if cnt + AB[i][1] < M:
        cnt += AB[i][1]
        money += AB[i][0]*AB[i][1]
    else:
        for j in range(AB[i][1]):
            money += AB[i][0]
            if cnt + j + 1 == M:
                break
        break

print(money)   

Measured memory_bytes: 20072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    int N;
    cin >> N;
    vvec<ll> A(N,vec<ll>(N));
    vvec<ll> dist(N,vec<ll>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        cin >> A[i][j];
        dist[i][j] = A[i][j];
    }
    for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
    }
    bool ok = true;
    ll ans = 0;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        ok &= A[i][j]==dist[i][j];
        bool use = true;
        for(int k=0;k<N;k++) if(k!=i && k!=j){
//            cerr << dist[i][j] << " " << dist[i][k]+dist[k][j] << "\n";
            use &= (dist[i][j]<dist[i][k]+dist[k][j]);
        }
        if(use) ans += dist[i][j];
    }
    cout << (ok? ans/2:-1) << "\n";
}

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

int po(int n, int x){

    if(x == 0) return 1;
    int ans = n;
    for(int i = 1; i < x; i++){
        ans = ans * n;
    }

    return ans;
}

int ke(int n){
    for(int i = 1; i < 10; i++){
        if(pow(10, i) > n) return i;
    }
}

int main(){

    //cout << ke(10000) << endl;
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    int MAX = -1;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            int pair = a[i] * a[j];
            int temp = pair;
            int keta = ke(pair);

            //cout << pair << " " << keta << endl;
            vector<int> a(keta + 1);
            for(int i = keta; i >= 1; i--){
                a[i] = pair / po(10, i - 1);
                pair = pair % po(10, i - 1);
                //cout << a[i] << " " << pair << endl;
            }
            
            /*for(int i = 1; i <= keta; i++){
                cout << a[i] << " ";
            }*/

            bool flag = true;
            for(int i = keta; i >= 2; i--){
                if(a[i] != a[i - 1] - 1){
                    flag = false;
                    break;
                }
            }

            if(flag) MAX = max(MAX, temp);
            
        }
    }

    cout << MAX << endl;
}


Measured memory_bytes: 3284
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		long K = scn.nextLong();
		int[] A = new int[N];

		final long MOD = 1000000007;

		for(int i = 0;i < N;i++) {
			A[i] = scn.nextInt();
		}

		long[] sin = new long[N], dob = new long[N];

		for(int i = 0;i < N;i++) {
			long buf = 0;
			for(int j = 0;j < N;j++) {
				if(A[i] > A[j]) {
					buf++;
				}
			}
			dob[i] = buf;
		}
		for(int i = 0;i < N;i++) {
			long buf = 0;
			for(int j = i+1;j < N;j++) {
				if(A[i] > A[j]) {
					buf++;
				}
			}
			sin[i] = buf;
		}

		long ans = 0;
		for(int i = 0;i < N;i++) {
			ans += (sin[i]*K)%MOD;
			ans += ((((K)*(K-1)/2)%MOD) * dob[i])%MOD;
			ans %= MOD;
		}
		System.out.println(ans);

	}

}


Measured memory_bytes: 26328
#include<string>
using namespace std;
int main(){
	string s; int p,c;
	while(cin>>s){
		for(p=0,c=0;(p=s.find("JOI",p))!=s.npos;p++)c++; cout<<c<<endl;
		for(p=0,c=0;(p=s.find("IOI",p))!=s.npos;p++)c++; cout<<c<<endl;
	}
	return 0;
}

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

int main() {
  int n, tmp;
  while(cin >> n && n != 0){
    vector<int> s;
    for(int i = 0; i < n; i++) {
      cin >> tmp;
      s.push_back(tmp);
    }
    sort(s.begin(), s.end());
    s.erase(s.begin()); s.erase(s.end() - 1);
    tmp = 0;
    for(auto i: s) {
      tmp += i;
    }
    cout << tmp / (n - 2)<< endl;
  }
}

Measured memory_bytes: 2992
N=int(input())
h=list(map(int,input().split()))
h.insert(0,0)
count=0
def find(h,x):
    count=0
    for i in range(0,N):
        if h[i]<x and h[i+1]>=x:
            count=count+1
    return count
for j in range(1,max(h)+1):
    count=count+find(h,j)
print(count)

Measured memory_bytes: 3064
//84104971101048411497 - Can you guess what does this mean?
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i,  r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define X real()
#define Y imag()
#define maxN 100005
#define oo 2000000007

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

string s;
bool avail[256];

int main () {
    cin >> s;
    forit(it, s) avail[*it] = true;

    puts(((!avail['N']^avail['S'])&(!avail['W']^avail['E'])) ? "Yes" : "No");

    return 0;
}


Measured memory_bytes: 256
from heapq import heappop, heappush

N, K = map(int, input().split())
td = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[1], reverse=True)
q = []
v = set()
cnt = 0
for t, d in td[:K]:
    cnt += d
    if t in v:
        heappush(q, d)
    else:
        v.add(t)
cnt += len(v) ** 2
ans = cnt
for t, d in td[K:]:
    if t not in v and len(q) != 0:
        x = heappop(q)
        cnt += d + 2 * len(v) + 1 - x
        v.add(t)
        ans = max(ans, cnt)
print(ans)


Measured memory_bytes: 30848
import itertools
 
N, M = map(int, input().split())
graph = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
 
p = list(itertools.permutations(range(N)))
 
Sum = 0
 
for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1
 
print(Sum)

Measured memory_bytes: 8052
import math
import itertools

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
new_p = sorted(p)
new_q = sorted(q)
check = 0
roop = math.factorial(n)

list_p = []
list_q = []
for i in itertools.permutations(new_p):
    list_p.append(i)
for i in itertools.permutations(new_q):
    list_q.append(i)

check = 0
for i in range(roop):
    if list_p[i] == tuple(p):
        a = i
        check += 1
    if list_q[i] == tuple(q):
        b = i
        check += 1
    if check == 2:
        break

print(abs(a-b))

Measured memory_bytes: 12788
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
a,b,c,x,y = ips()
c*=2
z = 0
sum = x*a+b*y
cm = sum
while x and y:
    x-=1
    y-=1
    z+=1
    sum-=(a+b)
    sum+=c
    cm = min(cm,sum)
if x:
    while x>0:
        x-=1
        sum-=a
        sum+=c
        cm = min(cm,sum)
elif y:
    while y>0:
        y -= 1
        sum -= b
        sum += c
        cm = min(cm, sum)
print(cm)

Measured memory_bytes: 14468
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){
  string s,t;
  cin>>s>>t;
  bool flag=false;
  int n = s.size();
  for(int i = 0; i<n;i++){
    if(s.substr(i,n-i)+s.substr(0,i)==t) flag = true;
  }
  if(flag) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


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


void solve(char X, char Y){
    if(X == Y) cout << "=" << endl;
    if(X > Y) cout << ">" << endl;
    if(X < Y) cout << "<" << endl;
}

int main(){
    char X;
    std::cin >> X;
    char Y;
    std::cin >> Y;
    solve(X, Y);
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(a: str, b: str):
    print("HD"[(a == "H") ^ (b == "H")])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    solve(a, b)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e):
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum():
	d = int(raw_input())
	if d == 0: return False
	n, m = int(raw_input()), int(raw_input())
	S = [int(raw_input()) for _ in range(n-1)]
	K = [int(raw_input()) for _ in range(m)]
	S = [0] + sorted(S) + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum
	return True

while (print_sum()):
	pass

Measured memory_bytes: 13340
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# D以下orUより大きい場所への遷移
def to0or4(base: int, nex: int):
    return base + nex

# Dより大きくS以下 or Gより大きくU以下の場所への遷移
def to1or3(base: int, nex: int):
    if nex == 0:
        return base + 2
    
    elif nex % 2:
        return base + 1
    
    else:
        return base


# Sより大きくG以下の場所への遷移
def to2(base: int, nex: int):
    if nex % 2:
        return base
    
    else:
        return base + 1
    
n = ni()
a = [ni() for _ in range(n)]
suma = sum(a)  

# 配るDP
dp = [[suma]*5 for _ in range(n+1)]
dp[0] = [0]*5

for i in range(n):
    for idx in range(5):
        for jdx in range(idx,5):
            
            if jdx == 0 or jdx == 4:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to0or4(dp[i][idx], a[i]))
            
            elif jdx == 1 or jdx == 3:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to1or3(dp[i][idx], a[i]))
                
            elif jdx == 2:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to2(dp[i][idx], a[i]))
   
print(min(dp[n]))

Measured memory_bytes: 86100
#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cfloat>
#include <cmath>
#include <functional>
#include <forward_list>
#include <list>


#define DEBUG(x) cout << #x << "\t:" << x << endl;
#define EPS (1e-9)
#define INF (INT_MAX/3)
#define MOD 1000000007
#define PI 3.14159265358979
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define REPV(it,v) for(auto it = (v).begin(); it != (v).end(); ++it)

#define NUM 5000

#define ll long long
#define ull unsigned long long

using namespace std;

typedef pair<int, int> iiPair;


class Main {
public:
	int getAns(vector<int> ss) {
		int sum = 0;
		REP(i, ss.size()) {
			sum += ss[i];
		}
		vector<bool> dp(sum + 1, false);

		dp[0] = true;
		REP(i, ss.size()) {
			vector<bool> nextDp = dp;
			REP(j, dp.size()) {
				if (dp[j] && j + ss[i] < dp.size()) {
					nextDp[j + ss[i]] = true;
				}
			}
			dp = nextDp;
		}

		for (int i = dp.size() - 1;i >= 0;i--) {
			if (i % 10 != 0 && dp[i]) {
				return i;
			}
		}
		return 0;
	}
};

int main(void) {
	Main main;
	int n;
	vector<int> ss;
	cin >> n;
	REP(i, n) {
		int inp;
		cin >> inp;
		ss.push_back(inp);
	}

	cout << main.getAns(ss) << endl;

	return 0;
}

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

using namespace std;

int dp[234567][4];

int main(){
  int N; cin >> N;
  int a[N+2], b[N+2], c[N+2];
  for(int i=1; i<=N; ++i) cin >> a[i] >> b[i] >> c[i];
  for(int i=1; i<=N; ++i)
    for(int j=1; j<=3; ++j){
      if(j == 1){
        dp[i][j] = max(dp[i-1][2], dp[i-1][3]) + a[i];
      }
      else if(j == 2){
        dp[i][j] = max(dp[i-1][1], dp[i-1][3]) + b[i];
      }
      else{
        dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + c[i];
      }
    }
  cout << max({dp[N][1], dp[N][2], dp[N][3]}) << "\n";
  return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
using namespace std;

vector<int> SortedArrayUniqueCnt(vector<string> str){
    int cnt = 1, num_len = 0;
    vector<int> num(str.size());
    vector<string> num_tmp;

    string tmp;
    tmp = str.at(0);

    for(int i = 1; i < str.size(); i++){
        if(tmp == str.at(i)){
            cnt++;
        }
        else{
            num.at(num_len++) = cnt;
            cnt = 1;
            tmp = str.at(i);
        }

        if((i+1) == str.size()){
            num.at(num_len++) = cnt;
        }
    }
    return num;
}

int main () {
    int N, M, cnt = 0, num = 0;
    string tmp;

    cin >> N;

    vector<string> input_s(N);
    vector<string> unique_s(N);
    vector<int> cnt_s(N);

    for(int i = 0; i < N; i++){
        cin >> input_s.at(i);
    }

    cin >> M;

    vector<string> input_t(M);
    vector<string> unique_t(M);
    vector<int> cnt_t(M);

    for(int i = 0; i < M; i++){
        cin >> input_t.at(i);
    }

    sort(input_s.begin(), input_s.end());
    sort(input_t.begin(), input_t.end());

    unique_s = input_s;
    unique_t = input_t;

    tmp = input_s.at(0);

    cnt_s = SortedArrayUniqueCnt(input_s);
    cnt_t = SortedArrayUniqueCnt(input_t);

    unique_s.erase(unique(unique_s.begin(), unique_s.end()), unique_s.end());

    unique_t.erase(unique(unique_t.begin(), unique_t.end()), unique_t.end());


    for(int i = 0; i < unique_s.size(); i++){
        for(int j = 0; j < unique_t.size(); j++){
            if(unique_s.at(i) == unique_t.at(j)){
                cnt_s.at(i) -= cnt_t.at(j);
            }
        }
    }

    int max = 0;

    for(int i = 0; i < cnt_s.size(); i++){
        if(cnt_s.at(i) > max){
            max = cnt_s.at(i);
        }
    }

    cout << max << endl;
}


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

using namespace std;

int main(){

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

int mn=a[0],mx=a[0];
long long sum=0;
for(int i=0;i<n;i++){
mn=min(mn,a[i]);
mx=max(mx,a[i]);
sum += a[i];
}

cout<<mn<<" "<<mx<<" "<<sum<<endl;

return 0;
}



Measured memory_bytes: 3120
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100 * 1000 + 47;


int A[MAX];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    FOR(i, 0, n)
    {
        scanf("%d", A + i);
    }
    int idx = 0;
    FOR(i, 0, n-1)
        if (A[i] + A[i+1] > A[idx] + A[idx+1])
            idx = i;
    
    if (A[idx] + A[idx+1] < m)
    {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    FOR(i, 0, idx)
    printf("%d\n", i+1);
    RFOR(i, n-1, idx+1)
    printf("%d\n", i+1);
    
    printf("%d\n", idx + 1);
    

}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll L;

ll i, j, k;
int main(){
    scanf("%lld", &L);
    double ans = (double)L / 3.0;
    ans = ans * ans * ans;
    printf("%.12lf", ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;
const int inf = 1e9;
const lli mod = 998244353;

lli ExGCD(lli a, lli b, lli &x, lli &y){
	lli d=a;
	x=1; y=0;
	if(b!=0){ d=ExGCD(b, a%b, y, x); y-=a/b*x; }
	return d;
}
lli inverse(lli a){
	lli x,y;
	ExGCD(a, mod, x, y);
	return x>0? x: mod+x;
}

lli fact[300001];
lli inv[300001];
void maketable(){
	fact[0] = 1;
	for(int i=0; i<300000; i++){
		fact[i+1] = fact[i]*(i+1) %mod;
	}
	lli y;
	for(int i=0; i<300000; i++){
		ExGCD(fact[i], mod, inv[i], y);
		while(inv[i]<0) inv[i]+=mod;
	}
}
lli nCr(lli n, lli r){
	if(n < r) return 0;
	return fact[n] *inv[n-r] %mod *inv[r] %mod;
}

lli modpow(lli a, lli p){
	lli ret = 1;
	for(int i=63; i>=0; i--){
		ret *= ret;
		ret %= mod;
		if((1LL<<i & p) != 0){
			ret *= a;
			ret %= mod;
		}
	}
	return ret;
}

int main(){
	maketable();
	lli n,m,k;
	cin >> n >> m >> k;
	lli ans = 0;
	for(int i=0; i<k+1; i++){
		ans += m*nCr(n-1, i)%mod *modpow(m-1, n-1-i) %mod;
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8292
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] s = new int[n];
        int[] c = new int[n];
      	int counter = 0;
        for(int i = 0; i < n; i ++){
            s[i] = scan.nextInt();
            c[i] = s[i];
        }
        Arrays.sort(c);
        for(int j = 0; j < n; j++){
            if(c[j] == s[j]){
                counter++;
            }
        }
        System.out.print((counter>=n-2 ? "YES" : "NO"));
        scan.close();
    }
}

Measured memory_bytes: 23380
from itertools import permutations

n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
cnt=1
for i in permutations(range(1,n+1),n):
    i=list(i)
    if i==p:
        a=cnt
    if i==q:
        b=cnt
    cnt+=1
print(abs(a-b))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef long int lint;
typedef vector<char> vchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
#define vsort(v) sort((v).begin(), (v).end())
#define vreverse(v) reverse((v).begin(), (v).end())
#define pb(a) push_back(a)
#define INF 1000000007
#define MOD 1e9+7
int main(){
  //input
int a,s,d;cin>>a>>d>>s;

  //caricurate
if((a<s)&&(s<d)){cout<<"Yes"<<endl;return 0;}
if((a>s)&&(s>d)){cout<<"Yes"<<endl;return 0;}
cout<<"No"<<endl;
  //output


}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  for(int i=n-1;i>0;i--){
    // cout<<a[i-1]<<" "<<a[i]<<endl;
    if(a[i-1]-a[i]>=2){
     	cout<<"No"<<endl;
      	return 0;
    }
    else if(a[i]<a[i-1]){
      a[i-1]--;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>


int N, M, C, count, kekka;
int array[10000][20];
int array1[20];
int main()
{
	std::cin >> N >> M >> C;
	for(int i = 1; i <= M; i++)
	{
		std::cin >> array1[i];
	}

	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <=M; j++)
		std::cin >> array[i][j];
	}
	for(int i = 1; i <= N; i++)
	{
		kekka = 0;
		for(int j = 1; j <=M; j++)
		{
			if(j == M)
			{
				kekka += array[i][j] * array1[j];
				kekka += C;
				if(kekka > 0)
				{
					count++;
				}
			}else
			{
				kekka += array[i][j] * array1[j];
			}
		}
		
	}
	std::cout << count;
}

Measured memory_bytes: 256
def main():  
    n = int(input())
    a = list(map(int,input().split()))
    asum = sum(a)
    asum2 = asum // 2
    x = 0
    tmp = 0
    for i in range(len(a)):
        tmp += a[i]
        if tmp >= asum2:
            x = i
            break
    spa1 = sum(a[0:x])
    spa2 = sum(a[0:x+1])
    ans1 = asum - 2*spa1
    ans2 = 2*spa2 - asum
    print(min([ans1,ans2]))
    
if __name__ == '__main__':
    main()

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

int w, h, n;

int main(){
  cin >> w >> h >> n;
  int right = w, left = 0, upper = h, lower = 0;
  rep(i, n){
    int x, y, a;
    cin >> x >> y >> a;
    if(a == 1){
      left = max(x, left);
    }else if(a == 2){
      right = min(x, right);
    }else if(a == 3){
      lower = max(y, lower);
    }else if(a == 4){
      upper = min(y, upper);
    }
  }
  int height = max(0, upper - lower);
  int width = max(0, right - left);
  cerr << height <<" "<< width;
  cout << height * width << endl;
  return 0;
}


Measured memory_bytes: 256
H,W,K=map(int,input().split())
C=[input() for _ in range(H)]
ans=0

for i in range(2**(H+W)):
  flag=[[True for _ in range(W)] for u in range(H)]
  for j in range(H):
    if ((i>>j)&1)==1:
      flag[j]=[False for _ in range(W)]
  for j in range(W):
    if ((i>>(j+H))&1)==1:
      for k in range(H):
        flag[k][j]=False
  num=0
  for i in range(H):
    for j in range(W):
      if flag[i][j] and C[i][j]=="#":
        num+=1
  if num==K:
    ans+=1

print(ans)

Measured memory_bytes: 9108
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    double x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double res = sqrt(pow((y1-y2), 2)+pow((x1-x2), 2));
    cout << fixed << setprecision(8) << res << endl;
    return 0;
}



Measured memory_bytes: 3292
#include<iostream>
#include<algorithm>
using namespace std;
int t[100005] = {0};
int s[100005];
int main() {
	int a, b,c,d;
	cin >> a >> b;
	d = 0;
	for (int i = 0; i < a;i++) {
		cin >> s[i];
	}
	sort(s, s + a );
	//cout<<" "<<s[0]<<endl;
	int ans = 1000000000;
	for (int i = b-1; i < a ;i++) {
		if(s[i]-s[i-b+1]<ans)ans=s[i]-s[i-b+1];
	}
	cout << ans << endl;
}

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

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

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

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

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

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

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

  int n;
  cin >> n;
  vector<int> x(n);
  REP(i, n) cin >> x[i];
  int m, k;
  cin >> m >> k;
  vector<int> a(m);
  REP(i, m) cin >> a[i], a[i]--;

  // iがjについて反転
  // (x[i] + x' ) / 2 = x[j]
  // x' = 2x[j] - x[i]
  // aが反転するなら
  // E[x'] = E[2x[a-1]-x[a]]/2 + E[2x[a+1]-x[a]]/2 = E[x[a-1]] + E[x[a+1]] - E[x[a]]

  // xについて差分をとった数列dxを用意すると上の操作は swap(dx[a-1], dx[a]) となる
  // 1セット分の運動は置換として考えられる
  // K回置換は二分累乗のようにするとO(NlogK)でできる

  auto func = [&](vector<int> v1, vector<int> v2) {
    vector<int> ret(v1.size());
    REP(i, v1.size()) ret[i] = v2[v1[i]];
    return ret;
  };

  vector<int> p(n-1);
  REP(i, n-1) p[i] = i;
  // cout << p << endl;
  REP(i, m) {
    swap(p[a[i]-1], p[a[i]]);
    // cout << p << " " << a[i] << endl;
  }

  vector<int> ret(n-1);
  REP(i, n-1) ret[i] = i;
  while(k > 0) {
    // cout << ret << " " << p << endl;
    if(k%2 == 0) {p = func(p, p); k /= 2;}
    else {ret = func(ret, p); k--;}
    // cout << k << " " << ret << endl;
  }


  vector<int> dx(n-1), dy(n-1);
  FOR(i, 1, n) dx[i-1] = x[i] - x[i-1];

  vector<int> ans(n);
  ans[0] = x[0];
  REP(i, n-1) ans[i+1] = ans[i] + dx[ret[i]]; 

  REP(i, n) cout << ans[i] << endl;

  return 0;
}


Measured memory_bytes: 7532
#include <stdio.h>

int main(void){
	int n, m, x, a;
	int bef = 0, af = 0;
	scanf("%d%d%d", &n, &m, &x);
	for (int i = 0; i < m; i++) {
		scanf("%d", &a);
		if (a <= x) bef++;
		if (a >= x) af++;
    }
	printf("%d\n", (bef > af ? af : bef));
	return 0;
}


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

int main() {
	// your code goes here
	int x, n, a;
	if(n == 0){
		cout << x << endl;
		return 0;
	}
	cin >> x >> n;
	set<int> s;
	for(int i = 0;i < n; ++i){
		cin >> a;
		s.insert(a);
	}
	int ans1 = x, ans2 = x;
	while(true){
		if(!s.count(ans1)){
			cout << ans1 << endl;
			return 0;
		}
		if(!s.count(ans2)){
			cout << ans2 << endl;
			return 0;
		}
		--ans1;
		++ans2;
	}
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long N;
    cin >> N;
    vector<pair<long long, int>> A(N+1);
    A.at(0).first = 0;
    for (long long i = 1; i < N+1; i++){
        A.at(i).second= i;
        cin >> A.at(i).first;
    }
    sort(A.begin() + 1, A.end(), greater<pair<long long, int>>() );
    vector<vector<long long>> dp(N+1, vector<long long> (N+1));
    dp.at(0).at(0) = 0;
    for (int xy = 1; xy < N+1; xy++){
        for (int x = 1; x < xy; x++){
            dp.at(x).at(xy-x) = max( dp.at(x-1).at(xy-x) + A.at(xy).first * abs( A.at(xy).second - x ) , 
                                  dp.at(x).at(xy-x-1) + A.at(xy).first * abs( A.at(xy).second - N + xy - x - 1 ));
        }
        dp.at(0).at(xy) = dp.at(0).at(xy-1) + A.at(xy).first * abs( A.at(xy).second - N + xy - 1 );
        dp.at(xy).at(0) = dp.at(xy-1).at(0) + A.at(xy).first * abs( A.at(xy).second - xy );
    }
    long long ans = 0;
    for (int i = 0; i <= N; i++){
        ans = max(ans, dp.at(i).at(N-i));
    }
    printf("%lld\n", ans);
}

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

#define MOD 1000000007
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}

int n;
int m;

#define MAX 1<<11
int ans[MAX][MAX];



int main(){
	cin>>n>>m;
	int mx=max(n,m);
	ans[0][0]=0;
	for(int i=0;i<mx;i++){
		for(int j=0;j<(1<<i);j++){
			for(int k=0;k<(1<<i);k++){
				ans[j+(1<<i)][k]=ans[j][k];
				ans[j][k+(1<<i)]=ans[j][k];
				ans[j+(1<<i)][k+(1<<i)]=ans[j][k]^1;
			}
		}
	}
	n=(1<<n);
	m=(1<<m);
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			int flag=ans[i][j];
			flag^=ans[i-1][j];
			flag^=ans[i][j-1];
			flag^=ans[i-1][j-1];
			printf("%d",flag);
		}
		puts("");
	}
	return 0;
}


Measured memory_bytes: 11520
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repeq(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define rep1(i,x,n) for(int (i)=(x);(i)<(int)(n);(i)++)
#define rep1eq(i,x,n) for(int (i)=(x);(i)<=(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;
typedef pair<int,int> P;
typedef std::priority_queue<int> IntPrioQueue;
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue;

//少数点表示
//cout << std::fixed << std::setprecision(14) << 値

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    ll n,k;
    cin >> n >> k;
    ll ans=0,m=0,M=n;
    rep1(i,2,n+2){
        m = m+(i-1);
        M = M+n-(i-1);
        //cout << "m:"<<m<<" M:"<<M<<endl;
        if(i>=k){
            ans += (M-m+1); 
        }
    }
    if(k==1){
        ans += n+1;
    }

    ans = ans%MOD;
    cout << ans << endl;
    return 0;
    
}

Measured memory_bytes: 3656
#include <iostream>
using namespace std;
int f(int a){
  if(a%2 == 0) return a/2;
  else return 3*a+1;
}

int main(){
  int s;
  cin >> s;
  int cnt = 1;
  while(s!=4 && s!=2 && s!=1){
    s = f(s);
    cnt++;
  }
  cout << cnt+3 << endl;
  return 0;
}

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

int main(){
 int N;
  cin>>N;
  int64_t H[100010];
  for(int i=0;i<N;i++)cin>>H[i];
  int MAX=0;
  int count=0;
  for(int i=0;i<N-1;i++){
    if(H[i+1]<=H[i]){
      count++;
      MAX=max(MAX,count);
    }
    else count=0;
  }
  cout<<MAX<<endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            Console.ReadLine();
            var s = new List<string>(Console.ReadLine().Split());
            s.Sort();
            Console.ReadLine();
            int count = 0;
            foreach(var item in Console.ReadLine().Split()) {
                count += s.BinarySearch(item) >= 0 ? 1 : 0;
            }
            Console.WriteLine(count);
        }
    }
}

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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}

//char->int
int ctoi(char c){
    return c-'0';
}



int main(){
    int n,a,b;
    cin >> n >> a >> b;
    int ans = 0;
    
    for(int i=1;i<=n;i++){
        int x = digsum(i);
        if(x>=a&&x<=b){
            ans+=i;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())





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

	int m, d;
	cin >> m >> d;

	int ans = 0;
	for (int i = 1; i <= m;i++) {
		for (int j = 1; j <= d;j++) {
			if (j%10 >= 2 && j/10 >=2 && i == (j/10)*(j%10)) {
				ans++;
			}
		}
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <numeric>
// #include <fstream>
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long mod = 1e9 + 7;

int main()
{
    long long int n; std::cin >> n;
    std::string s; std::cin >> s;

    // 個数だけ引く
    long long int cntr = std::count(s.begin(), s.end(), 'R');   
    long long int cntg = std::count(s.begin(), s.end(), 'G');
    long long int cntb = std::count(s.begin(), s.end(), 'B');
    long long int ans = cntr * cntg * cntb, sub = 0;
    for(long long int i=0; i<n; i++)
    {
        for(long long int j=i+1; j<n; j++)
        {
            if(s[i]==s[j]) continue;
            long long int k = 2 * j - i;
            if(k>=n || s[j]==s[k] || s[i]==s[k]) continue;
            ans--;
        }
    }
    
    std::cout << ans - sub << std::endl;
    return 0;
}


Measured memory_bytes: 3604