akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
 
template <class T>
std::vector<T> ToFixedArray(std::istream& is, int n) {
	std::vector<T> ret(n);
	auto* dst = ret.data();
	while(n-- > 0)
		is >> *dst++;
	return ret;
}
 
#define _For(idx, from, to, inc, cmp) \
	for(auto idx=(from) ; idx cmp (to) ; inc idx)
#define ForLE(idx, from, to) \
	_For(idx, from, to, ++, <=)
#define ForGE(idx, from, to) \
	_For(idx, from, to, --, >=)
#define ForLT(idx, from, to) \
	_For(idx, from, to, ++, <)
#define ForGT(idx, from, to) \
	_For(idx, from, to, --, >)
#define For(idx, from, to) \
	_For(idx, from, to, ++, <)
 
void DisableIOSync() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios::sync_with_stdio(false);
}
using Dist_t = uint32_t;
constexpr auto DistMax = std::numeric_limits<Dist_t>::max()/2;
using DistV = std::vector<Dist_t>;
int main() {
	DisableIOSync();

	using std::cin;
	using namespace std;
	int NCity, NLink, NDest;
	cin >> NCity >> NLink >> NDest;

	auto dest = ToFixedArray<int>(std::cin, NDest);
	for(auto& d : dest)
		--d;

	using DistV = std::vector<Dist_t>;
	DistV dist(NCity * NCity, DistMax);
	const auto fdist = [&dist, NCity](const int from, const int to) -> decltype(auto) {
		return dist[from + to*NCity];
	};
	For(i, 0, NCity) {
		fdist(i,i) = 0;
	}
	For(i, 0, NLink) {
		int id0, id1, cost;
		cin >> id0 >> id1 >> cost;
		--id0;
		--id1;
		fdist(id0, id1) = cost;
		fdist(id1, id0) = cost;
	}
	For(inter, 0, NCity) {
		For(from, 0, NCity) {
			if(inter == from)
				continue;
			For(to, 0, NCity) {
				if(inter == to)
					continue;
				if(from == to)
					continue;
				fdist(from, to) =
					std::min(
						fdist(from, to),
						fdist(from, inter) + fdist(inter, to)
					);
			}
		}
	}
	Dist_t res = DistMax;
	std::sort(dest.begin(), dest.end());
	do {
		Dist_t sum = 0;
		For(i, 1, NDest) {
			sum += fdist(dest[i-1], dest[i]);
		}
		res = std::min(res, sum);
	} while(std::next_permutation(dest.begin(), dest.end()));
	std::cout << res << std::endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int v, e, r;
V< V< P<int, int> > > edges;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> v >> e >> r;
    edges.resize(v);
    for (int i = 0; i < e; i++) {
        int s, t, d; cin >> s >> t >> d;
        edges[s].emplace_back(make_pair(t, d));
    }

    V<int> dist(v, INF); dist[r] = 0;
    priority_queue< P<int, int> > que; que.push(make_pair(0, r));
    while (!que.empty()) {
        P<int, int> q = que.top(); que.pop();
        for (P<int, int> e: edges[q.second]) {
            if (dist[e.first] > dist[q.second] + e.second) {
                dist[e.first] = dist[q.second] + e.second;
                que.push(make_pair(-dist[e.first], e.first));
            }
        }
    }

    for (int i = 0; i < v; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << '\n';
    }
    return 0;
}



Measured memory_bytes: 12980
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n, m;
	cin >> n >> m;
	priority_queue<ll> que;
	for(int i = 0; i  < n; i++){
		ll temp;
		cin >> temp;
		que.push(temp);
	}
	for(int i = 0; i < m; i++){
		ll temp;
		temp = que.top();
		que.pop();
		temp /= 2;
		que.push(temp);
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
		ans += que.top();
		que.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 1528
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long int
#define MOD 1000000007
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(long long int i=a;i<b;i++)
using namespace std;
int main()
{
	fast;
	string s1,s2;
	cin>>s1>>s2;
	ll c=0;
	rep(i,0,3)
	{
		if(s1[i]==s2[i])
		{
			c++;
		}
	}
	cout<<c<<endl;
}

Measured memory_bytes: 256
N,X = gets.strip.split.map(&:to_i)
bounds = gets.strip.split.map(&:to_i)

state = []
state[0] = 0
count = 0
result = 0

if state[0] <= X
        result += 1
    end

N.times do |i|
    state[i+1] = bounds[i] + count
    count = state[i+1]
    if state[i+1] <= X
        result += 1
    end
end

puts result

Measured memory_bytes: 1788
from itertools import accumulate
from collections import Counter


def solve(string):
    n, m, *lr = map(int, string.split())
    t = [0] * (n + 2)
    for l, r in zip(*[iter(lr)] * 2):
        t[l] += 1
        t[r + 1] -= 1
    *t, = accumulate(t)
    c = Counter(t)
    return str(c[m]) if m in c.keys() else "0"


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))


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

const long long INF = 1LL << 60;

int main() {
    int N; cin >> N;
    vector<long long> h(N);
    for(int i = 0; i < N; ++i) cin >> h[i];
    
    vector<long long> dp(N, INF);
    dp[0] = 0;
    for(int i = 1; i < N; ++i) {
        dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
        if(i > 1) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
    }
    
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 1792
using System;

class Program {
  static void Main() {
    var s = Console.ReadLine();
    int[] a = new int[26];
    foreach (var c in s) {
      a[c - 97]++;
    }
    var ans = "Yes";
    foreach (var n in a) {
      if ((n & 1) == 1) {
        ans = "No";
        break;
      }
    }
    Console.WriteLine(ans);
  }
}

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

int main() {
    string s;
    cin >> s;
    
    int y = 700;
    if (s[0]=='o') y += 100;
    if (s[1]=='o') y += 100;
    if (s[2]=='o') y += 100;

    cout << y << endl;
}


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

int main() {
	int n, r; cin >> n >> r;
	if (n >= 10) cout << r << endl;
	else cout << r + (100 * (10 - n)) << endl;
	return 0;
}


Measured memory_bytes: 256
K, N = list(map(int,input().split()))
A = list(map(int,input().split()))

max = K - A[N-1] + A[0]

for i in range(N-1):
  if(max < A[i+1] - A[i]):
    max = A[i+1] - A[i]

  
print(K - max)

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

using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;

const double eps = 1e-7;
#define Loop(i, n) for(int i = 0; i < int(n); i++)
#define Loopll(i, n) for(ll i = 0; i < ll(n); i++)
#define Loop1(i, n) for(int i = 1; i <= int(n); i++)
#define Loopll1(i, n) for(ll i = 1; i <= ll(n); i++)
#define Loopr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = int(n); i >= 1; i--)
#define Looprll1(i, n) for(ll i = ll(n); i >= 1; i--)
#define Foreach(buf, container) for(auto buf : container)
#define Loopdiag(i, j, h, w, sum) for(int i = ((sum) >= (h) ? (h) - 1 : (sum)), j = (sum) - i; i >= 0 && j < (w); i--, j++)
#define Loopdiagr(i, j, h, w, sum) for(int j = ((sum) >= (w) ? (w) - 1 : (sum)), i = (sum) - j; j >= 0 && i < (h); j--, i++)
#define Loopdiagsym(i, j, h, w, gap) for (int i = ((gap) >= 0 ? (gap) : 0), j = i - (gap); i < (h) && j < (w); i++, j++)
#define Loopdiagsymr(i, j, h, w, gap) for (int i = ((gap) > (h) - (w) - 1 ? (h) - 1 : (w) - 1 + (gap)), j = i - (gap); i >= 0 && j >= 0; i--, j--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(ex_i, vector.size()) { cout << vector[ex_i] << " "; } cout << endl;
#define printmx(matrix) Loop(ex_i, matrix.size()) { Loop(ex_j, matrix[ex_i].size()) { cout << matrix[ex_i][ex_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
#define Comp(type_t) bool operator<(const type_t &another) const
#define fst first
#define snd second
#define INF INFINITY
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) { Foreach(x, xs) if (!(x >= 0 && x < t)) return false; return true; }
int ceillog2(ll x) { int ret = 0;	x--; while (x > 0) { ret++; x >>= 1; } return ret; }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (m * m <= x ? 0 : -1); }
ll ceilsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }

//========================================================================//

int main() {
	int n; cin >> n;
	vi a(n);
	Loop(i, n) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int x = a[n / 2 - 1];
	int y = a[n / 2];
	cout << y - x << endl;
}

Measured memory_bytes: 768
// https://atcoder.jp/contests/arc091/tasks/arc091_b

#include "algorithm"
#include "cmath"
#include "functional"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll N, K;
  cin >> N >> K;

  ll res = 0;

  rep(b, N + 1) {
    if (b - 1 < K) continue;
    ll round_down = N / b;
    // round_down 回 0 ~ b-1 の余りが一度ずつ現れている
    res += max(0ll, round_down * (b - 1 - (K - 1)));

    // 残りの 1, 2.. rest について K 以上のものをカウント
    ll rest = N - round_down * b;
    res += max(0ll, rest - max(0ll, (K - 1)));
  }

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(){
	double len;
	double rad;
	double x,y;
	
	int i,n;
	
	while(1){
		rad = 0.0;
		len = 1.0;
		scanf("%d",&n);
		if(n == -1)	break;
		
		for(i=1;i<n;i++){
			len = sqrt(len*len + 1.0);
			rad += asin(1/len);
		}
		
		x = len * cos(rad);
		y = len * sin(rad);
		
		printf("%f\n%f\n",x,y);
		
	}
	
	return 0;
}

Measured memory_bytes: 676
#include<cstdio>
#include<algorithm>
using namespace std;

int JOI(char c){
  if(c=='J') return 0;
  if(c=='O') return 1;
  if(c=='I') return 2;
}

int main(){
  int n,dp[1000][8];
  char s[1001];
  scanf("%d %s",&n,s);
  for(int i=0;i<8;i++){
    dp[0][i] = 0;
    if(i&1&&i>>JOI(s[0])&1) dp[0][i] = 1;
  }
  for(int i=1;i<n;i++){
    for(int j=0;j<8;j++){
      dp[i][j] = 0;
      if(j>>JOI(s[i])&1){
        for(int k=0;k<8;k++){
          if(j&k) dp[i][j] += dp[i-1][k];
        }
      }
      dp[i][j] %= 10007;
    }
  }
  int ans = 0;
  for(int i=0;i<8;i++) ans += dp[n-1][i];
  printf("%d\n",ans%10007);
  return 0;
}

Measured memory_bytes: 2764
H, W = map(int, input().split())
a = [[int(i) for i in input().split()] for j in range(H)]

ans = []
for i in range(H):
    for j in range(W):
        if a[i][j] % 2 == 1:
            if j < W - 1:
                a[i][j + 1] += 1
                a[i][j] -= 1
                ans.append((i, j, i, j + 1))
            elif i < H - 1:
                a[i + 1][j] += 1
                a[i][j] -= 1
                ans.append((i, j, i + 1, j))
                
print(len(ans))
for i in ans:
    print(i[0] + 1, i[1] + 1, i[2] + 1, i[3] + 1)

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

int main(void){
    vector< pair<int, int> > res;
    while(1) {
        int h, w;
        cin >> h >> w;
        if(w == 0) break;
        vector< pair<int, int> > d[100100];
        int min_ = h*h+w*w;
        int ans = 1 << 30;
        for(int i = 2; i < 150; i++) {
            for(int j = 1; j < i; j++) {
                if(min_ <= i*i+j*j && ans >= i*i+j*j) {
                    if(min_ != i*i+j*j) {
                        ans = i*i+j*j;
                        d[ans].push_back(make_pair(j, i));
                    }
                    else if(j > h) {
                        ans = i*i+j*j;
                        d[ans].push_back(make_pair(j, i));
                    }
                }
            }
        }
        sort(d[ans].begin(), d[ans].end());
        for(pair<int, int> p : d[ans]) {
            res.push_back(make_pair(p.first, p.second));
            //cout << p.first << " " << p.second << endl;
            break;
        }
    }
    for(int i = 0; i < res.size(); i++) {
        cout << res[i].first << " " << res[i].second << endl;
    }
    return 0;
}



Measured memory_bytes: 5428
import sys
from math import gcd

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    g = A[0]
    for a in A[1:]:
        g = gcd(g, a)

    if max(A) >= K and K % g == 0:
        ans = "POSSIBLE"
    else:
        ans = "IMPOSSIBLE"

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 20024
#include <iostream>                                                                              
#include <string>                                                                                
                                                                                                 
using namespace std;                                                                             
                                                                                                 
int main (void) {                                                                                
  string s, s2, p;                                                                               
  getline(cin,s);                                                                                
  getline(cin,p);                                                                                
                                                                                                 
  s2 = s+s;                                                                                      
  if (s2.find(p)!=string::npos) {                                                     
    cout<<"Yes"<<endl;                                                                           
  } else {                                                                                       
    cout<<"No"<<endl;                                                                            
  }                                                                                              
}                                                                                                
                                     

Measured memory_bytes: 3228
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	const mod = 1000000007
	ans := 0
	for i := k; i <= n+1; i++ {
		mn := (i - 1) * i / 2
		mx := (n*2 - i + 1) * i / 2
		ans += mx - mn + 1
		ans %= mod
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1756
#include<stdio.h>

int parent(int);
int left(int);
int right(int);

int main(){
  int num,i,array[100001];
  scanf("%d",&num);

  for(i = 1;i <= num;i++){
    scanf("%d",&array[i]);
  }
  for(i = 1;i <= num;i++){
    printf("node %d: key = %d, ",i,array[i]);
    if(parent(i) >= 1){
      printf("parent key = %d, ",array[parent(i)]);
    }
    if(left(i) <= num){
      printf("left key = %d, ",array[left(i)]);
    }
    if(right(i) <= num){
      printf("right key = %d, ",array[right(i)]);
    }
    printf("\n");
}
return 0;
}

int parent(int i){
  return i / 2;
}
int left(int i){
  return 2 * i;
}
int right(int i){
  return 2 * i + 1;
}



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

using namespace std;
const int N = 1e5 + 3, MOD = 1e9 + 7;
int n, m, mem[N];
bool broken[N];
int go(int i) {
	if (i >= n)
		return i == n;
	int &ret = mem[i];
	if (~ret)
		return ret;
	ret = 0;
	if (!broken[i + 1])
		ret = go(i + 1);
	if (!broken[i + 2])
		ret = (ret + go(i + 2)) % MOD;
	return ret;
}

int main() {
#ifndef ONLINE_JUDGE
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
#endif
	scanf("%d %d", &n, &m);
	while (m--) {
		int x;
		scanf("%d", &x);
		broken[x] = true;
	}
	memset(mem, -1, sizeof mem);
	printf("%d\n", go(0));
	return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

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

int main() {
  int N, T;
  cin >> N >> T;
  vector<int> t(N);
  rep(i, N) cin >> t[i];
  ll ans = 0;
  rep(i, N-1)
    ans += min(T, t[i+1]-t[i]);
  ans += T;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

    def same(self, x, y):
        return self.root(x)==self.root(y)

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]


n,m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    uf.unite(x,y)

root = [uf.root(i) for i in range(n)]
print(len(set(root)))


Measured memory_bytes: 13992
def resolve():
    N, M = map(int, input().split())

    CNT = [0] * N
    for _ in range(M):
        x, y = map(lambda x: int(x) - 1, input().split())
        CNT[x] += 1
        CNT[y] += 1

    for c in CNT:
        if c % 2 == 1:
            print("NO")
            return
    else:
        print("YES")


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9580
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}
int in(){int a;scanf("%d",&a);return a;}
ll lin(){ll a;scanf("%lld",&a);return a;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int n, m;
string s, t;
int dp[2][2002][2002];
bool S[2002], T[2002];

int rec(int I, int a, int b) // I := ???I????????????, a := s??????????????????, b := t??????????????????
{
    int &res = dp[I][a][b];

    if (~res) return res;

    res = 0;
    
    if (a < m && I != S[a]) {
        chmax(res, 1 + rec(S[a], a + 1, b));
    }

    if (b < n && I != T[b]) {
        chmax(res, 1 + rec(T[b], a, b + 1));
    }

    return res;
}

int main()
{
    m = in(), n = in();
    cin >> s >> t;

    rep(i, m) S[i] = s[i] == 'I';
    rep(i, n) T[i] = t[i] == 'I';

    memset(dp, -1, sizeof dp);

    int ma = 0;

    rep(i, m) rep(j, n) {
        chmax(ma, rec(S[i], i+1, j) + S[i]);
        chmax(ma, rec(T[j], i, j+1) + T[j]);
    }

    printf("%d\n", ma == 0 ? 0 : (ma - (ma % 2 == 0)));
}

Measured memory_bytes: 34968
N, T = map(int, input().split())
A = list(map(int, input().split()))

m = 10**9+1
s = 0
c = 0
for a in A:
    m = min(m, a)
    if a - m > s:
        s = a - m
        c = 1
    elif a - m == s:
        c += 1

print(c)

Measured memory_bytes: 62704
#include<stdio.h>
#define SENTINEL 2000000000
#define MAX 200000
int L[MAX/2+2],R[MAX/2+2];
typedef long long llong;

llong merge(int A[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left;
    int n2 = right - mid;
    llong cnt=0;
    for (i=0; i<n1; i++) L[i]=A[left+i];
    for (i=0; i<n2; i++) R[i]=A[mid+i];
    L[n1]=SENTINEL;
    R[n2]=SENTINEL;
    i = 0;
    j = 0;
    for (k=left; k<right; k++) {
        if (L[i]<=R[j]) {
            A[k] = L[i];
            i+=1;
        } else {
            A[k] = R[j];
            j+=1;
            cnt+=n1-i;
        }
    }
    return cnt;
}

llong merge_sort(int A[], int left, int right) {
    llong v1, v2, v3;
    if (left+1<right) {
        int mid = (left + right) / 2;
        v1 = merge_sort(A, left, mid);
        v2 = merge_sort(A, mid, right);
        v3 = merge(A, left, mid, right);
        return v1 + v2 + v3;
    } else return 0;
}

int main() {
    int i, n;
    int A[MAX];
    llong cnt;

    scanf("%d", &n);
    for (i=0; i<n; i++) scanf("%d", &A[i]);
    cnt = merge_sort(A, 0, n);
    printf("%ld\n", cnt);
}


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

int main(){
    int n,m,place,tmp,cnt;
    while(cin >> n >> m, n && m){
        queue <int> que;
        int sugo[n+1];
        for(int i=1;i<=n;i++) cin >> sugo[i];
        for(int i=0;i<m;i++){
            cin >> tmp;
            que.push(tmp);
        }
        cnt = 0;
        place = 1;
        while(1){
            place += que.front();
            que.pop();
            cnt++;
            if(place >= n) break;
            place += sugo[place];
            if(place >= n) break;
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 1220
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

double getAvg(const int& n)
{
    double res = 0.f;
    for(int i = 1; i <= n; i++)
    {
        res += i;
    }
    res /= n;
    return res;
}
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(8);
    int n, k; cin >> n >> k;
    vector<int> p(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
    }
    int v = 0;
    for(int i = 0; i < k; i++) v += p[i];
    int M = v;
    pair<int, int> index = make_pair(0, k);
    for(int i = k; i < n; i++)
    {
        v += p[i];
        v -= p[i - k];
        if(M < v)
        {
            index = make_pair(i - k + 1, i + 1);
            M = v;
        }
    }
    double ans = 0.f;
    for(int i = index.first; i < index.second; i++)
    {
        ans += getAvg(p[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])

ans = float('inf')
for div in range(2 ** (H - 1)):
    g = 0
    ids = [0] * H
    for i in range(H):
        ids[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(1005)] for _ in range(10)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] += int(S[i][j])

    num = g - 1
    now = [0] * g
    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
                num = float('inf')
                break

    ans = min(ans, num)
print(ans)


Measured memory_bytes: 63452
import java.util.*;
public class Main {
    private static Scanner sc = new Scanner(System.in);
    public static void main(String[] args){
        int N = sc.nextInt();
        long[] A=new long[N];
        long allA=0;
        long Mod = (long)Math.pow(10,9)+7;
        for(int i=0; i<N; i++){
            A[i]=sc.nextLong();
            allA = (allA + A[i])%Mod;
        }
        long res=0;
        for(int i=0; i<N; i++){
            allA = allA - A[i];
            if(allA<0){
                allA = allA + Mod;
            }
            res = (res + A[i]*allA)%Mod;
        }

        System.out.println(res);
}

}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//main code
int main(int argc, char const* argv[])
{
	string s,t;
	cin >> s >> t;
	int r = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == t[i]) {
			r++;
		}
	}
	cout << r << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio() ios_base::sync_with_stdio(false)
#define rmod(x, y) ((((x)%(y))+(y))%(y))
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T, typename R = null_type, typename C = less<T>>
tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update> ordered_set(){
    return tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update>();
}


int main(){
	ld n; cin >> n;
	printf("%.10Lf", (ld)(n/3.0)*(n/3.0)*(n/3.0));
    return 0;
}


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

int main(){

    char X;
    char Y;

    cin >> X;
    cin >> Y;

    if((int) X < (int) Y){
        cout << "<" << endl;
    }else if((int) X > (int) Y){
        cout << ">" << endl;
    }else{
        cout << "=" << endl;
    }
    return 0;




}

Measured memory_bytes: 256
/*
Author : Xinyuan
*/
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int  ll;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int nxt() {int x;scanf("%d", &x);return x;}


int main(){
    int i,j, k;
    cin >> i >> j;
    multiset<int> myset;
    for (int x = 0; x < i; x++) {
         cin >> k;
         myset.insert(k);
    }
    auto it1 = myset.begin();
    int total = 0;
    for (int y = 0; y < j; y++) {
        total += *it1;
        it1++;
    }
    cout << total;
}


Measured memory_bytes: 3672
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);

		int count = 0;

		for (int i = 1; i <= n; i++) {
			if (i < 10 || (i < 1000 && i > 99) || (i < 100000 && i > 9999) && i != 100000) {
				count++;
			}
		}
		System.out.println(count);
	}
}

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

int N, A;
vector<int> nums;

long dp[50][50][2500];

long choose(int now, int chose_count, int all){
    if(now == N){
        return all == A * chose_count && chose_count;
    }else if(dp[now][chose_count][all] != -1){
        return dp[now][chose_count][all];
    }else{
        return dp[now][chose_count][all] = choose(now + 1, chose_count, all) + choose(now + 1, chose_count + 1, all + nums[now]);
    }
}

int main(){
    cin >> N >> A;
    nums.resize(N);
    for(int i = 0; i < N; i++){
        cin >> nums[i];
    }
    for(int i = 0; i < 50; i++){
        for(int j = 0; j < 50; j++){
            for(int k = 0; k < 2500; k++){
                dp[i][j][k] = -1;
            }
        }
    }
    cout << choose(0, 0, 0) << endl;
}


Measured memory_bytes: 49024
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;

int main(){
	cin>>n;
	if(n==1) cout<<2<<endl;
	else if(n>2) cout<<0<<endl;
	else cout<<1<<endl;
}


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

int main() {
	while(true){
	int m=0, n=0 ,move[1000]={} ,turn=0 ,flag=0;
	double masu[1000]={};
	cin>>m>>n;
	if (n==0||m==0)	break;
	for(int i=0;i<m;i++){
		cin>>masu[i];
	}
	for(int i=0;i<n;i++){
		cin>>move[i];
	}
	for(int i=0;i<n;i++){
		flag=flag+move[i];
		flag=flag+masu[flag];
		turn++;
		if (flag>=m)	break;
	}
	cout<<turn<<endl;

	}
return 0;
}

Measured memory_bytes: 1236
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a;
    int b = 1;
    int ans = 1;
    for (int i = 0;i<n;i++){
      a = sc.nextInt();
      ans *= 3;
      if (a%2 == 0){
        b*=2;
      }
    }
    System.out.println(ans-b);
  }
}

Measured memory_bytes: 23892
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist, prev
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A-1].append((B-1, C))
    graph[B-1].append((A-1, C))
shortest_path = [dijkstra(graph, i) for i in range(N)]
from itertools import permutations
ans = 10**9

for path in permutations(rlist):
    cost = 0
    for i in range(R-1):
        cost += shortest_path[path[i]-1][0][path[i+1]-1]
    ans = min(ans, cost)
print(ans)

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

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define RREP(i, N) for (int i =(int)N-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;


int main(){
  int n;
  cin>>n;
  ll ans=0;
  REP(i,n){
    ans+=i;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
N = int(input())

if N % 2 == 1:
    M = N * (N - 1) / 2 - (N - 1) / 2
    print(int(M))
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            if i != j and i + j != N:
                print(str(i) + " " + str(j))

else:
    M = N * (N - 1) / 2 - N / 2
    print(int(M))
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            if i != j and i + j != N + 1:
                print(str(i) + " " + str(j))


Measured memory_bytes: 3344
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	text := stdin.Text()

	if len(text) != 6 {
		panic(fmt.Errorf("unexpected text"))
	}

	a := strings.Split(text[2:4], "")
	b := strings.Split(text[4:6], "")

	if a[0] == a[1] && b[0] == b[1] {
		fmt.Print("Yes")
		return
	}
	fmt.Print("No")
}

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

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

    vector<long long> A(N, 0);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    sort(A.begin(), A.end(), greater<int>());

    long long out = 0;
    for(int i = 1; i < N; i++){
        int index = i / 2;
        out += A[index];
    }
    cout << out << endl;
}

Measured memory_bytes: 4820
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int a,b,c,x,ans=0;
  	cin >> a >> b >> c >> x;
    rep(i,a+1)rep(j,b+1)rep(k,c+1)if(i*500+j*100+50*k==x)ans++;
    cout << ans << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ a, b, k ] <- readInts
	mapM_ print $ map head $ group $ sort $ filter ( \x -> a <= x && x <= b ) $ [ a .. a + k - 1 ] ++ [ b - k + 1 .. b ]

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

int main() {
  int N, M;
  cin >> N >> M;
  map<int, int> accepted;
  map<int, int> wa_count;
  int p;
  string s;
  for(int i = 0; i < M; ++i) {
    cin >> p >> s;
    if(s == "AC") {
      accepted[p]++;
    } else {
      if(accepted[p] == 0) {
        wa_count[p]++;
      }
    }
  }
  int ans_ac = 0;
  for(auto ac : accepted) {
    if(ac.second > 0) {
      ans_ac++;
    }
  }
  int ans_wa = 0;
  for(auto wa : wa_count) {
    if(accepted[wa.first] > 0) {
      ans_wa += wa.second;
    }
  }
  cout << ans_ac << " " << ans_wa << endl;
  return 0;
}

Measured memory_bytes: 6144
def calc(a)
  stack = []
  symbol = '+-*/'
  a.each do |e|
    if symbol.include?(e)
      a, b = stack.pop(2)
      stack << eval("#{a}#{e}#{b}")
    else
      stack << e.to_i
    end
  end
  stack[0]
end

p calc(gets.split)

Measured memory_bytes: 8680
#include <stdio.h>
int main() {
  int k, a, b, num;
  scanf("%d", &k);
  scanf("%d%d", &a, &b);
  for(int i=1; 1; i++){
    num = k * i;
    if(num>=a && num<=b){
      printf("OK\n");
      break;
    }else if(num>b){
      printf("NG\n");
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 1664
N = int(input())
xys = set([tuple(map(int, input().split())) for _ in range(N)])

z = []
w = []

for xy in xys:
    z.append(xy[0]+xy[1])
    w.append(xy[0]-xy[1])

#print(z)
#print(w)

print(max(abs(max(z) - min(z)), abs(max(w) - min(w))))

Measured memory_bytes: 61280
n = int(input())
data = [int(s) for s in input().split()]

change = 0
flag = True
while flag:
	flag = False
	for idx in range(1,n):
		if data[idx-1] > data[idx]:
			data[idx-1],data[idx] = data[idx],data[idx-1]
			flag = True
			change += 1

print(' '.join([str(d) for d in data]))
print(change)

Measured memory_bytes: 7672
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define P pair<int, int>
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const double LIM = (1 << 8);

string calc2(double N) {
  stringstream ss;
  for(int i = 0; N != 0.0 && i < 10; ++i){
    double nn = N * 2;
    if(nn >= 1.0){
      ss << 1;
      nn -= 1.0;
    }
    else ss << 0;
    N = nn;
  }
  while(ss.str().length() < 4) ss << 0;
  string s = ss.str();
  return (s.length() == 4 ? s : "NA");
}

string calc(int N) {
  stringstream ss;
  while(N){
    if(N & 1) ss << 1;
    else ss << 0;
    N >>= 1;
  }
  while(ss.str().length() < 8) ss << 0;
  string s = ss.str();
  REVERSE(s);
  return (s.length() == 8 ? s : "NA");
}

int main() {
  double N;
  while(cin >>N && N >= 0.0) {
    string a = calc(floor(N)), b = calc2(N - floor(N));
    if(a == "NA" || b == "NA") {
      cout <<"NA" <<endl;
      continue;
    }
    cout <<a + "." + b <<endl;
  }
  return 0;
}

Measured memory_bytes: 1260
def func(A, x, lower, upper):
    if lower+1 == upper:
        if (A[lower] == x)or(A[upper] == x):
            return 1
        else:
            return 0
    idx = (upper+lower)//2
    if x < A[idx]:
        return func(A, x, lower, idx)
    else:
        return func(A, x, idx, upper)


N = int(input())
S = list(map(int, input().split()))
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for t in T:
    ans += func(S, t, 0, N)
print(ans)



Measured memory_bytes: 16716
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k; string s;
char maze[60][60];
int dis[101][101];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll dp[100010][2]; int x[509][509]; int c[509][509];
int gcd(int x, int y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
int main() {
	int r;
	cin >> r;
	string res = "ABC";
	if (r < 1200) {
		res = "ABC";
	}
	else if (1200 <= r && r < 2800) {
		res = "ARC";
	}
	else {
		res = "AGC";
	}
	cout << res << endl;
}




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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
//#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
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;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}


void solve(long long a, long long b, long long x){
    if(2*x<=a*a*b){
        double d=2.0*(double)x/(double)a/(double)b;
        double ans=atan((double)b/d);
        cout << fixed << setprecision(10) << ans/M_PI*180 << endl;
    }else{
        double d=2*(double)b-2*(double)x/(double)a/(double)a;
        double ans=atan(d/(double)a);
        cout << fixed << setprecision(10) << ans/M_PI*180 << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
signed main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long x;
    scanf("%lld",&x);
    solve(a, b, x);
    return 0;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

const int M = 100000;
int n, m, dp[M];
vector<int> g[M];

int f(int v) {
	if(dp[v] != 0) { return dp[v]; }
	
	int ma = 0;
	for(auto && e: g[v]) { setmax(ma, f(e)); }
	
	return (dp[v] = ma + 1);
}

int main() {
	cin >> n >> m;
	inc(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		g[y].PB(x);
	}
	
	int ans = 0;
	inc(i, n) { setmax(ans, f(i) - 1); }
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 10624