akhauriyash/Code-Regression huggingface dataset:
// vvvvvvvvvvvvvvvvv Library code start


#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>


#define forn(t, i, n) for (t i = 0; i < (n); ++i)

#define rforn(t, i, n) for (t i = (n) - 1; i >= 0; --i)


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}


// ^^^^^^^^^^^^^^^^^ Library code end

void solve(istream& in, ostream& out) {
    int n = next<int>(in);
    int qc = next<int>(in);
    vector<uint64_t> qs;
    qs.push_back(n);
    forn (int, i, qc) {
        qs.push_back(next<uint64_t>(in));
    }
    map<uint64_t, uint64_t> m;
    m[qs.back() - 1] = 1;
    qs.pop_back();
    while (!qs.empty()) {
        uint64_t q = qs.back();
        qs.pop_back();
        uint64_t whole = 0;
        while (!m.empty() && m.rbegin()->first >= q) {
            auto it = m.end();
            auto p = *--it;
            m.erase(it);
            whole += (p.first / q) * p.second;
            m[p.first % q] += p.second;
        }
        if (whole) {
            m[q - 1] += whole;
        }
    }
    vector<uint64_t> ans(n);
    for (auto& p : m) {
        ans[p.first] += p.second;
    }
    rforn (int, i, n - 1) {
        ans[i] += ans[i + 1];
    }
    forn (int, i, n) {
        out << ans[i] << "\n";
    }
}


int main() {
    solve(cin, cout);
    return 0;
}



Measured memory_bytes: 9076
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N; i >= 0; i--)
const ll INF = 1000000000000000000;
//input
int N,K;


//processing



//dpTable
//int dp[100050];

int main(){
    cin >> N >> K;
    int A[N];
    rep (i,N){
        cin >> A[i];
    }
    for (int i = 0; i + K < N; i++){
        if (A[i] < A[i + K]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 4392
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum Type{
	J,
	O,
	I,
};


int main(){

	int N;
	scanf("%d",&N);
	char* stamp = new char[N+1];

	scanf("%s",stamp);

	ll** JOI_table = new ll*[N+1];
	for(int i = 0; i <= N; i++){
		JOI_table[i] = new ll[3];
		for(int k = 0; k < 3; k++)JOI_table[i][k] = 0;
	}

	JOI_table[0][J] = 1;
	ll sum = 0,maximum;
	for(int i = 0; i < N; i++){
		switch(stamp[i]){
		case 'J':
			JOI_table[i+1][J] = JOI_table[i][J]+1;
			JOI_table[i+1][O] = JOI_table[i][O];
			break;
		case 'O':
			JOI_table[i+1][J] = JOI_table[i][J];
			JOI_table[i+1][O] = JOI_table[i][O] + JOI_table[i][J];
			break;
		case 'I':
			JOI_table[i+1][J] = JOI_table[i][J];
			JOI_table[i+1][O] = JOI_table[i][O];
			JOI_table[i+1][I] = JOI_table[i][O];
			sum += JOI_table[i+1][I];
			break;
		}
	}

	maximum = sum;

	for(int i = 0; i <= N; i++){
		for(int k = 0; k < 3; k++)JOI_table[i][k] = 0;
	}

	sum = 0;
	ll normal;
	for(int i = 0; i < N; i++){
		switch(stamp[i]){
		case 'J':
			JOI_table[i+1][J] = JOI_table[i][J]+1;
			JOI_table[i+1][O] = JOI_table[i][O];
			break;
		case 'O':
			JOI_table[i+1][J] = JOI_table[i][J];
			JOI_table[i+1][O] = JOI_table[i][O] + JOI_table[i][J];
			break;
		case 'I':
			JOI_table[i+1][J] = JOI_table[i][J];
			JOI_table[i+1][O] = JOI_table[i][O];
			JOI_table[i+1][I] = JOI_table[i][O];
			sum += JOI_table[i+1][I];
			break;
		}
	}
	normal = sum;
	sum += JOI_table[N][O];

	maximum = max(maximum,sum);

	ll J_num[N+1],I_num[N+1];

	for(int i = 0; i <= N; i++){
		J_num[i] = 0;
		I_num[i] = 0;
	}

	for(int i = 0; i < N; i++){
		if(stamp[i] == 'J'){
			J_num[i+1] = J_num[i]+1;
		}else{
			J_num[i+1] = J_num[i];
		}
	}

	if(stamp[N-1] == 'I')I_num[N] = 1;

	for(int i = N-2; i >= 0; i--){
		if(stamp[i] == 'I'){
			I_num[i+1] = I_num[i+2]+1;
		}else{
			I_num[i+1] = I_num[i+2];
		}
	}

	ll tmp_max = 0;

	for(int i = 1; i <= N-1; i++){
		tmp_max = max(tmp_max,J_num[i]*I_num[i+1]);
	}

	maximum = max(maximum,normal+tmp_max);

	printf("%lld\n",maximum);

	return 0;
}

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

int main() {
	int a, b;
	cin>>a>>b;
	if ((a>0 && a<21) || (a>0 && a<21)) 
		if (a>9 || b>9)
			cout<<-1;
		else
			cout<<a*b;
	
	return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>

#define MAX 2000
#define MOD 1000000007

int main(void){
  long i,j;
  long ans=0;

  long n,k;
  scanf("%ld%ld",&n,&k);

  long a[MAX]={};
  for(i=0;i<n;i++){
    scanf("%ld",&a[i]);
    for(j=0;j<i;j++){
      if(a[j]>a[i]){
        ans=(ans+k*(k+1)/2)%MOD;
      }else if(a[j]<a[i]){
        ans=(ans+k*(k-1)/2)%MOD;
      }
    }
  }

  printf("%ld\n",ans);

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for(int i=0; i<n; i++)

vector<bool> seen;
vector<int> num(200200);
void dfs(const Graph &G, int v) {
    seen[v] = true;

    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; 
        num[next_v]+=num[v];
        dfs(G, next_v); 
    }
}

int main() {
    int N; cin >> N;
    int Q; cin >> Q;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    int p[Q],x[Q];
    rep(i,Q){
        cin>>p[i]>>x[i];
        num[p[i]-1] += x[i];
    } 
    
    seen.assign(N, false); 
    dfs(G, 0);

    rep(i,N) cout<<num[i]<<" ";
    cout<<endl;
}

Measured memory_bytes: 25088
#include <bits/stdc++.h>
#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 irep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a.at(i);
    
    int ans=1000000000;
    irep(i,-100,101){
        int c=0;
        rep(j,n) c+=(a.at(j)-i)*(a.at(j)-i);
        ans=min(ans,c);
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 256
#include <iostream>

int main()
{
	int h, w;
	std::cin >> h >> w;
	
	int n, a[110][110] = { 0 }, count[11000] = { 0 }, totalCount = 0, coloursCount = 1;
	std::cin >> n;
	
	for (int i = 0; i < n; ++i)
		std::cin >> count[i];
	
	int i = 0, j = 0, smallCount = 0;
	bool flag = true;
	while (totalCount < h * w)
	{
		a[i][j] = coloursCount;
		++smallCount;
		
		if (smallCount == count[coloursCount - 1])
		{
			++coloursCount;
			smallCount = 0;
		}
		
		if (flag)
			++i;
		else
			--i;
		
		if (i == h)
		{
			++j;
			i = h - 1;
			flag = false;
		}
		else if (i == -1)
		{
			++j;
			i = 0;
			flag = true;
		}
		
		++totalCount;
	}
	
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			std::cout << a[i][j] << " ";
		}
		std::cout << "\n";
	}
}

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

min_m = int(N**0.5)
max_m = N
ans = 0
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        if(min_m<i-1 and i-1<max_m):
            ans += i-1
        if i != N // i:
            a = N//i-1
            if(min_m<a and a<max_m):
                ans += a
print(ans)


Measured memory_bytes: 3060
#include <stdio.h>
int main()
{
  int i, j, H, W;
  for(;;){
    scanf("%d %d",&H, &W);
    if(H == 0 && W == 0)break;
    for(i = 0; i < H; i++){
      for(j = 0; j < W; j++){
	if(i % 2 == 0 && j % 2 == 0){
	  printf("#");
	} else if(i % 2 == 0 && j % 2 == 1){
	  printf(".");
	} else if(i % 2 == 1 && j % 2 == 0){
	  printf(".");
	} else if(i % 2 == 1 && j % 2 == 1){
	  printf("#");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
#include <stdio.h>
#include <stdlib.h>

int main(void){

  int n,m;
  scanf("%d %d", &n, &m);
  long a[n];
  long b[n];
  for (int i = 0; i < n; i++) {
    scanf("%ld %ld", &a[i], &b[i]);
  }
  long c[m];
  long d[m];
  for (int i = 0; i < m; i++) {
    scanf("%ld %ld", &c[i], &d[i]);
  }

  long distance;
  long min;
  int point;
  for (int i = 0; i < n; i++) {
    min = -1;
    for (int j = 0; j < m; j++) {
      distance = labs(a[i]-c[j])+labs(b[i]-d[j]);
      if (min == -1 || distance < min) {
        min = distance;
        point = j+1;
      }
    }
    printf("%d\n", point);
  }

  return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  ll a,b;
  cin >> a >> b;
  cout << (a-1)*(b-1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n;
  int truss_a,truss_b,truss_c;
  int kazu_a,kazu_b;
  scanf("%d",&n);
  truss_a = n/100;
  kazu_a = n%100;
  truss_b = kazu_a/10;
  kazu_b = kazu_a%10;
  truss_c= kazu_b;
  if(truss_a==7||truss_b==7||truss_c==7)
    printf("Yes");
  else
    printf("No");
  return 0;
}

Measured memory_bytes: 1692
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def maxprofit(n, rs):
    maxp = rs[1] - rs[0]
    minp = rs[0]
    for i in range(1, n):
        maxp = max(maxp, rs[i] - minp)
        minp = min(minp, rs[i])
    return maxp


def main():
    n = int(input())
    rs = [int(input()) for i in range(n)]
    print(maxprofit(n, rs))

if __name__ == "__main__":
    main()

Measured memory_bytes: 15696
using System;

namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().ToCharArray();

            var x = 0;
            foreach(var c in s){
                if(c == '+'){
                    x += 1;
                }else{
                    x -= 1;
                }
            }

            Console.WriteLine(x);
        }
    }
}


Measured memory_bytes: 13140
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
  const usize f, l;

public:
  class itr {
    friend rep;
    usize i;
    constexpr itr(const usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
  constexpr itr begin() const noexcept { return itr(f); }
  constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
  const usize f, l;

public:
  class itr {
    friend revrep;
    usize i;
    constexpr itr(usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
  constexpr itr begin() const noexcept { return itr(l); }
  constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
  return a < b ? b - a : a - b;
}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

void main_() {
  usize r, g, b, n;
  std::cin >> r >> g >> b >> n;
  usize ans = 0;
  for (const auto i : rep(0, n + 1)) {
    for (const auto j : rep(0, n + 1)) {
      const usize t = r * i + g * j;
      if (t <= n && (n - t) % b == 0) {
        ++ans;
      }
    }
  }
  std::cout << ans << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


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

#define LL long long
#define COIN const int
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define REPD(i,n) for((i)=(n)-1;(i)>=0;(i)--)

#define ALL(c) (c).begin(), (c).end()
#define LEN(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/

using namespace std;

int a[100000],b[100000],x,y,z,i,c,d,m,ans,ans1=1e9,am=1e9,bm=1e9;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >>c >>d >>m;
	REP(i,c)
	{
		cin >>a[i];
		am=min(am,a[i]);
	}
	REP(i,d)
	{
		cin >>b[i];
		bm=min(bm,b[i]);
	}
	ans=am+bm;
	REP(i,m)
	{
		cin >>x >>y >>z;
		ans1=min(ans1,a[x-1]+b[y-1]-z);
	}
	cout <<min(ans,ans1)<<endl;
	return 0;
}
/******************************************************************************
******************************************************************************/


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

int main() {
  int N,cnt=0;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++) {
    cin >> vec[i];
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for(int i=0; i<N; i++) {
    if(i%2==0) {
      cnt+=vec[i];
    }
    else {
      cnt-=vec[i];
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let a: usize = read().unwrap();
    let b: usize = read().unwrap();

    // let aa = a.to_string().repeat(b);
    // let bb = b.to_string().repeat(a);
    let aa = (0..b).map(|_| a.to_string()).collect::<Vec<_>>().concat();
    let bb = (0..a).map(|_| b.to_string()).collect::<Vec<_>>().concat();

    if aa >= bb {
        println!("{}", bb);
    } else {
        println!("{}", aa);
    }
}

Measured memory_bytes: 4352
function gcd(input) {
    var x = +input.split(" ")[0];
    var y = +input.split(" ")[1];
    function _gcd(x, y) {
        if (x == y) {
            return x;
        }
        else if (x < y) {
            function swap(x, y) {
                var tmp = x;
                x = y;
                y = tmp;
            }
            swap(x, y);
        }
        if (y == 0) {
            return x;
        }
        return _gcd(y, x % y);
    }
    return _gcd(x, y);
}

console.log(gcd(require("fs").readFileSync("/dev/stdin", "UTF-8")));



Measured memory_bytes: 15128
#include <stdio.h>

int main(){
	int a,b,n=1,c;
	while(scanf("%d %d",&a,&b)!=EOF){
		//scanf("%d %d",&a,&b);
		c=a+b;
		while(1){
			c=c/10;
			n++;
			if(c<10) break;
			
		}
		printf("%d\n",n);
		n=1;
	}
	return 0;
}

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

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

// right, down, left, up
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

#define y0 icpc_y0
int n;
int x0, y0;
int t;
#define N 52
bool g[N][N][4];
bool st[2][N][N][16]; // 16 mean (nowdir, befdir)

int main(){
  scanf("%d%d%d%d",&n,&x0,&y0,&t);
  while(n--){
    int sx, sy, tx, ty;
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    if(sx == tx){
      if(sy>ty)swap(sy,ty);
      FOR(i,sy,ty){
        g[sx][i][1] = true;
        g[sx][i+1][3] = true;
      }
    }else{
      if(sx>tx)swap(sx,tx);
      FOR(i,sx,tx){
        g[i][sy][0] = true;
        g[i+1][sy][2] = true;
      }
    }
  }
  // REP(i,N){
  //   REP(j,N){
  //     REP(k,4)printf("%d",g[i][j][k]);
  //     printf(" ");
  //   }
  //   puts("");
  // }
  REP(i,N)REP(j,N)REP(k,16)st[0][i][j][k] = false;
  REP(k,16)if(((k>>2)^(k&3))!=2 && g[x0][y0][k>>2]){
    st[0][x0][y0][k] = true;
  }
  while(t--){
    int d;
    char buf[25];
    scanf("%d%s",&d,buf);
    int tdir = 0;
    if(buf[0]=='E')tdir = 0;
    if(buf[0]=='N')tdir = 1;
    if(buf[0]=='W')tdir = 2;
    if(buf[0]=='S')tdir = 3;
    while(d--){
      // step
      REP(i,N)REP(j,N)REP(k,16)st[1][i][j][k] = false;
      REP(i,N)REP(j,N)REP(k,16)if(st[0][i][j][k]){
        int bdir = k>>2;
        int ni = i + dx[bdir];
        int nj = j + dy[bdir];
        // printf("from %d,%d,%d(%d)\n", i,j,k,bdir);
        REP(ndir,4){
          if((bdir ^ ndir) == 2)continue;
          if(!g[ni][nj][ndir])continue;
          st[1][ni][nj][(ndir<<2) | bdir] = true;
          // printf("    -> %d,%d,%d(%d)\n", ni,nj,(ndir<<2)|bdir,ndir);
        }
      }
      REP(i,N)REP(j,N)REP(k,16){
        st[0][i][j][k] = st[1][i][j][k];
      }
    }
    REP(i,N)REP(j,N)REP(k,16){
      if((k>>2)!=tdir && (k&3)!=tdir){
        st[0][i][j][k] = false;
      }
    }
  }
  REP(i,N)REP(j,N){
    bool ok = false;
    REP(k,16)if(st[0][i][j][k])ok=true;
    if(ok){
      printf("%d %d\n",i,j);
    }
  }
  return 0;
}

Measured memory_bytes: 3320
from fractions import Fraction
n,k = map(int,input().split())
ans = Fraction(0,1)
for i in range(n):
    tmp = i + 1
    tmpP = 1
    while tmp < k:
        tmp *= 2
        tmpP *= 2
    ans += Fraction(1,tmpP)
print(float(ans/n))

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

int cnt[35][35];

int main() {
	unsigned long long ans = 0;
	int n; scanf("%d", &n);
	for(int i=1;i<=n;i++) {
		long double x; cin >> x;
		long double y = x; for(int j=1;j<=10;j++) y *= 10;
		unsigned long long p = (unsigned long long)(y + 0.5);
		int c2 = 0, c5 = 0;
		while( p % 2 == 0 ) p /= 2, c2++;
		while( p % 5 == 0 ) p /= 5, c5++;
		c2 = min(c2, 30), c5 = min(c5, 30), cnt[c2][c5]++;
		if( (unsigned long long)(x * x) == x * x ) ans--;
	}
	
	for(int i=0;i<=30;i++) for(int j=0;j<=30;j++)
	for(int p=0;p<=30;p++) for(int q=0;q<=30;q++)
		if( i + p >= 20 && j + q >= 20 && cnt[i][j] && cnt[p][q] )
			ans += 1ull * cnt[i][j] * cnt[p][q];
	
	printf("%llu\n", ans / 2);
}

Measured memory_bytes: 3824
fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}

const M: i64 = 1000000000 + 7;
const N: usize = 1000000 + 1;
fn main() {
    let n = get_line().parse().unwrap();

    let mut xs = vec![0; N];
    xs[1] = n;
    xs[2] = n * n % M;

    let mut ys = vec![0; N];
    ys[1] = n;
    ys[2] = (ys[1] + xs[2]) % M;

    for i in 3..(n as usize + 1) {
        xs[i] = xs[i - 1];
        xs[i] += (n - 1) * (n - 1) % M;
        xs[i] += (ys[i - 3] + n - i as i64 + 2) % M;
        xs[i] %= M;
        ys[i] += (ys[i - 1] + xs[i]) % M;
    }

    println!("{}", xs[n as usize]);
}


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

typedef long long ll;

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n;
    ll summ = 0;
    cin >> n;
    ll arr[n];

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

    for (int i = 0; i < n; i ++) {
        cout << (arr[i] ^ summ) << " ";
    }

    return 0;

}

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

int main(){
    int a,b,c,i,j;
    j=0;
    cin>>a>>b>>c;
    for ( i = a; i <= b; i++)
    {        
        if (c%i==0) j++;
    }
    cout<<j<<endl;    
    return 0;
}


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

int main(){
int x,y,z,v,r,a,l;
cin>>x;
y=x/500;
z=x%500;
a=y*1000;
l=z/5;
v=l*5;
r=a+v;
cout<<r;
    return 0;
}


Measured memory_bytes: 3596
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1_11_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] Dice = new int[6];
            string[] dice = Console.ReadLine().Split(' ');
            string Orders = Console.ReadLine();

            for (int i = 0; i < 6; i++)
            {
                string s = dice[i].ToString();
                Dice[i] = int.Parse(s);
            }

            for (int i = 0; i < Orders.Length; i++)
            {
                string order = Orders[i].ToString();
                if (order == "N")
                {
                    int a = Dice[0];
                    Dice[0] = Dice[1]; Dice[1] = Dice[5];//Dice[2] = Dice[2];
                    Dice[5] = Dice[4]; Dice[4] = a; //Dice[3] = Dice[3];

                }
                else if (order == "E")
                {
                    int a = Dice[0];
                    Dice[0] = Dice[3]; Dice[3] = Dice[5]; //Dice[1] = Dice[1];
                    Dice[5] = Dice[2]; Dice[2] = a; //Dice[4] = Dice[4];

                }
                else if (order == "S")
                {
                    int a = Dice[0];
                    Dice[0] = Dice[4]; Dice[4] = Dice[5]; //Dice[2] = Dice[2];
                    Dice[5] = Dice[1]; Dice[1] = a; //Dice[3] = Dice[3];
                }
                else
                {
                    int a = Dice[0];
                    Dice[0] = Dice[2]; Dice[2] = Dice[5]; //Dice[1] = Dice[1];
                    Dice[5] = Dice[3]; Dice[3] = a;  //Dice[4] = Dice[4];
                }
            }
            Console.WriteLine("{0}",Dice[0]);
        }
    }
}


Measured memory_bytes: 17984
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N;
int A[101010];
int d[101010];

signed main()
{
  cin >> N;
  int sum = 0;
  REP(i,N) {
    cin >> A[i];
    sum += A[i];
  }

  REP(i,N) {
    if (i + 1 < N) {
      d[i] = A[i+1] - A[i];
    } else {
      d[i] = A[0] - A[i];
    }
  }

  if (sum % (N * (N + 1) / 2) == 0) {
    int k = sum / (N * (N + 1) / 2);
    REP(i,N) {
      d[i] -= k;
    }
    REP(i,N) {
      while (k > 0 && d[i] < 0) {
        d[i] += N;
        k--;
      }
    }
    REP(i,N) {
      if (d[i] != 0) {
        cout << "NO" << endl;
        return 0;
      }
    }
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program {
    static Scanner cin = new Scanner();
    static void Main() {
        int N = cin.Int();
        var a = cin.ArrayLong(N);

        long ans = long.MaxValue;
        for(long i = -100; i <= 100; i++) {
            long tmp = 0;
            for (int j = 0; j < N; j++) {
                tmp += (i - a[j]) * (i - a[j]);
            }
            ans = Math.Min(ans, tmp);
        }

        Console.WriteLine(ans);

        Console.ReadLine();
    }
}

class Scanner //標準入力
{
    string[] s;
    int i;

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

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

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

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

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

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

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


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


Measured memory_bytes: 13268
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>

using namespace std;

int main(){

    //long long int ans=0;
    bool ans=false;

    long long int a,b,c;
    cin>>a>>b>>c;

    if(c-(a+b)>0){
        if(4*a*b<((c-a-b)*(c-a-b))){
            ans=true;
        }
    }

    if(ans){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <math.h>
 
int main(int argc, const char * argv[]) {
    long double x1, x2, y1, y2, pow1, pow2, distance;
    scanf("%Lf %Lf %Lf %Lf", &x1, &y1, &x2, &y2);
    pow1 = powl((x1 - x2), 2);
    pow2 = powl((y1 - y2), 2);
    distance = sqrtl(pow1 + pow2);
    printf("%5Lf\n", distance);
     
    return 0;
}


Measured memory_bytes: 2112
#include <stdio.h>

int main()
{
    int th,ts,ah,as;
    scanf("%d %d",&th,&ts);
    scanf("%d %d", &ah,&as);
    while(1){
        ah-=ts;
        if(ah<=0) break;
        th-=as;
        if(th<=0) break;
    }
    if(th>0) printf("Yes");
    else printf("No");
    return 0;
}

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

const int N=310;

int n,m,A[N][N],app[N],p[N],chose[N];

void Init() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) scanf("%d",&A[i][j]);
}

bool check(int ans) {
	for (int i=1;i<=m;++i) app[i]=0,chose[i]=1;
	for (int i=1;i<=n;++i) {
		app[A[i][1]]++; p[i]=1;
	}
	while (1) {
		bool fl=1;
		for (int i=1;i<=n;++i) {
			while (app[A[i][p[i]]]>ans || !chose[A[i][p[i]]]) {
				fl=0;
				chose[A[i][p[i]]]=0;
				p[i]++; app[A[i][p[i]]]++;
				if (p[i]>n) return 0;
			}
		}
		if (fl) break;
	}
	return 1;
}

void Solve() {
	int l=1,r=n;
	while (l<=r) {
		int mid=(l+r)>>1;
		if (check(mid)) r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
}

int main() {
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

			var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];

			//N <= 1+2+  + kのとき、kを最大とする数の和で表現できる
			//まずkを求める

			long k = 0;
			long kSum = 0;


			while (true) {
				kSum += k;
				if (N <= kSum) {
					break;
				}
				k++;
			}

			while (true) {
				Console.WriteLine(k);
				N = N - k;
				if (N == 0) {
					return;
				}

				if (N >(k-1)) {
					k--;
				}
				else {
					Console.WriteLine(N);
					break;
				}
			}
		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 13396
n,k = map(int, input().split( ))
a = list(map(int, input().split( )))
l = max(max(a),k).bit_length()###
x = 0
ans = 0
flag = False#既にx<kが確定しているか否か,ループ内だとおかしい
for i in range(l-1,-1,-1):
    cnt = 0
    
    for j in range(n):#i bit目に1が立っている数を数える
        cnt += a[j]>>i&1
    if (k>>i&1 or flag) and cnt<n-cnt:#i bit目に1が立てられてかつ立てたほうが良い
        x += 1<<i
        ans += (n-cnt)*(1<<i)
    else:
        ans += cnt*(1<<i)
    if (k>>i)>(x>>i):
        flag = True
print(ans)


Measured memory_bytes: 69008
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

ld EPS = (1e-10);
const ld PI = acos(-1);


ld r;

pair<ld, ld> rot(ld x, ld y) {
    ld xx = x*cos(r)-y*sin(r);
    ld yy = x*sin(r)+y*cos(r);
    return mp(xx, yy);
}

int main(void) {
    cin >> r;
    r = PI/180.0*r;

    ll k = 0;
    ld x = 0, y = 1;
    ld vx = 0, vy = 1;
    do {
        auto p = rot(vx, vy);
        vx = p.first, vy = p.second;
        x = x+vx, y = y+vy;
        k++;
    } while (abs(0.0-x)>EPS || abs(1.0-y)>EPS);
    

    cout << k << "\n";
    return 0;
}



Measured memory_bytes: 4088
n, k = map(int, input().split())

max_i = max(n, k)


if n>=k:
    n = n%k
if n==0 or k==1:
    print(0)
else:
    for _ in range(max_i):
        tmp = abs(n-k)
        if tmp >= n:
            break
        else :
            n = tmp
    
    print(n)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define inf 1e9
#define F first
#define S second
#define dbg(x) cout<<#x<<" value : "<<x<<"\n";
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--)
#define mst(a,b) memset(a,b,sizeof(a))
#define sf(n) scanf("%d",&n)
#define stf(n,m) scanf("%d%d",&n,&m)
#define pf(n) printf("%d\n",n)
#define slf(n) scanf("%lld",&n)
#define plf(n) printf("%lld\n",n)
priority_queue<int,vector<int>,less<int> > q;
const int N=1e5+10;
const int mod=1e9+7;
int n,m,sum,t;
int main()
{
	stf(n,m);
	rep(i,0,20){
		sum=(n*i-i+1);
		if(sum>=m){
			t=i;
			break;
		}
	}
	cout<<t<<endl;
	return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e3+10;

int n, m;
int a[maxn];
int b[maxn];
ll dp[maxn][maxn];//dp[i][j]: #of subseq ending at a[i] and b[j]

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>m;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=1; i<=m; i++) {
	cin>>b[i];
    }

    ll ans=1;
    //dp[0][0] = 1;
    for (int i=1; i<=n; i++) {
	for (int j=1; j<=m; j++) {
	    if (a[i]==b[j]) {
		dp[i][j]=1;
		dp[i][j]+=dp[i-1][j-1];
		dp[i][j]%=mod;
		ans += dp[i][j];
		ans %= mod;
	    } else {
		dp[i][j]=0;
	    }

	    dp[i][j] += dp[i][j-1];
	    dp[i][j] += dp[i-1][j];
	    dp[i][j] -= dp[i-1][j-1];
	}
    }


    ans %= mod;
    ans += mod;
    ans %= mod;

    cout<<ans<<endl;
    return 0;
}


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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);

    int n;
    cin>>n;
    string s;
    cin>>s;

    if(n%2)
    {
        cout<< "No";
        return 0;
    }

    string a=s.substr(0,n/2);
    string b=s.substr(n/2,n/2);
    if(a==b)
    {
        cout<< "Yes";

    }
    else cout<< "No";
    return 0;
}


Measured memory_bytes: 3652
gets

nums = gets.split(" ").map(&:to_i)
ans = "Yes"
(0..(nums.length - 2)).each do |i|
  if nums[i] < nums[i + 1]
    nums[i + 1] -= 1
  elsif nums[i] > nums[i + 1]
    ans = "No"
    break
  end
end

puts ans


Measured memory_bytes: 10116
#include <stdio.h>

int main(void){
 int a, b, c, ans=0;
 scanf("%d %d %d", &a, &b, &c);
 for(int i=a; i<=b; i++){
  if(c%i==0){
   ans++;
   }
 }
 printf("%d\n", ans);
 return 0;
}


Measured memory_bytes: 2756
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace ABC164
{
    public class Solve
    {
        public static void Main(string[] args)
        {
            new ABC_C();
        }
    }
    public class ABC_A
    {
        public ABC_A()
        {
            var l = Ex.ReadIntArray();
            var s = l[0];
            var w = l[1];
            var str = (s <= w) ? "unsafe" : "safe";
            str.Cw();
        }
    }
    public class ABC_B
    {
        public ABC_B()
        {
            var l = Ex.ReadIntArray();
            var a = l[0];
            var b = l[1];
            var c = l[2];
            var d = l[3];

            int i = 0;
            while (a > 0 && c > 0)
            {
                if (i % 2 == 0)
                {
                    c -= b;
                }
                else
                {
                    a -= d;
                }
                i++;
            }
            var res = (a > 0) ? "Yes" : "No";
            res.Cw();
        }
    }
    public class ABC_C
    {
        public ABC_C()
        {
            var n = Ex.ReadLong;
            string s;
            var ans = new HashSet<string>();
            for (int i = 0; i < n; i++)
            {
                s = Ex.Read;
                ans.Add(s);
            }
            ans.Count.Cw();
        }
    }
    public class ABC_D
    {
        public ABC_D()
        {
        }
    }
    public class ABC_E
    {
        public ABC_E()
        {
        }
    }
    public class ABC_F
    {
        public ABC_F()
        {
        }
    }
    public static class Ex
    {
        public static void Cw(this object s) { Console.WriteLine(s); }

        public static List<string> FastSort(this List<string> s) { s.Sort(StringComparer.Ordinal); return s.ToList(); }
        public static string yesno(this bool b) { return b ? "yes" : "no"; }
        public static string YesNo(this bool b) { return b ? "Yes" : "No"; }
        public static string YESNO(this bool b) { return b ? "YES" : "NO"; }

        public static string Read { get { return Console.ReadLine().Trim(); } }
        public static int ReadInt { get { return int.Parse(Read); } }
        public static long ReadLong { get { return long.Parse(Read); } }
        public static double ReadDouble { get { return double.Parse(Read); } }
        public static string[] ReadArray() { return Read.Split(' '); }
        public static int[] ReadIntArray() { return Read.Split(' ').Select(int.Parse).ToArray(); }
        public static long[] ReadLongArray() { return Read.Split(' ').Select(long.Parse).ToArray(); }
        public static string[] ReadArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public static int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public static long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 43016
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
x=max(a)
c=Counter(a)
flg=1
for i in range((x+1)//2,x+1):
  if i == (x+1)//2:
    if x%2==0:
      if c[i]!=1:
        flg=0
    else:
      if c[i]!=2:
        flg=0
  else:
    if c[i]<=1:
      flg=0
if flg:
  print("Possible")
else:
  print("Impossible")

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main() {
    string S;
    int ans=0;
    int ifans=0;
    cin >> S;
    for(int i=0;i<S.length();i++){
        ifans=0;
        for(int j=i;j<S.length();j++){
            if(S.at(j)=='R'){
                ifans++;
            }
            else{
                break;
            }
        }
        if(ans<ifans)
            ans=ifans;
    }
    cout << ans<<endl;
           
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define rep(shoki,i,n) for(int i=shoki; i<n; i++)
#define _GLIBCXX_DEBUG
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;

int main(){
    int n,m; cin>>n>>m;
    vi a(m),b(m);
    rep(0,i,m) cin>>a[i]>>b[i];

    vi c(n,0);
    rep(0,i,m){
        c[a[i]-1]++;
        c[b[i]-1]++;
    }

    rep(0,i,n){
        cout << c[i] << endl;
    }
}

Measured memory_bytes: 256
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n,x,i,ans=0;
    cin>>n;
    ll a[n-1];
    for(i=0; i<n-1; i++)
        cin>>a[i];
    ans=a[0];
    for(i=1; i<n-1; i++)
    {
        ans+=min(a[i-1],a[i]);
    }
    ans+=a[n-2];
    cout<<ans<<endl;



    return 0;
}





Measured memory_bytes: 3588
/*
 * ABC094_B.cpp
 *
 *  Created on: May 21, 2018
 *      Author: 13743
 */
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}



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

	int N, M, X;
	cin >> N >> M >> X;
	++N;
	int left = 0, right = 0;
	REP(i, M) {
		int a;
		cin >> a;
		if(a > X) ++right;
		else ++left;
	}

	cout << min(left, right) << endl;
}






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

int main(){

    int a, b, c, num ;

    cin >> a >> b >> c;

    for(int i=a; i<=b; i++){
        if(c%i==0){
            num += 1;
        }
    }

    cout << num << "\n";

    return 0;  
}


Measured memory_bytes: 3092
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    def calc(n):
        return (n * (n-1)) // 2 + n

    def merge(A, B):
        if len(A) > len(B):
            A, B = B, A
        for a in A:
            if a in B:
                B[a] += A[a]
            else:
                B[a] = A[a]
        return B

    N = int(input())
    C = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    size = [1] * (N+1)
    dic = [{} for _ in range(N+1)]
    ans = [calc(N)] * (N+1)
    for v in seq:
        for u in child[v]:
            size[v] += size[u]
        c = C[v-1]
        for u in child[v]:
            if c in dic[u]:
                ans[c] -= calc(size[u] - dic[u][c])
            else:
                ans[c] -= calc(size[u])
            dic[v] = merge(dic[v], dic[u])
        dic[v][c] = size[v]
    for c in range(1, N+1):
        if c in dic[1]:
            print(ans[c] - calc(N - dic[1][c]))
        else:
            print(ans[c] - calc(N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 208200
#include <iostream>
#include <string>

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

  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) {
    std::cout << "Bad" << std::endl;
  } else {
    std::cout << "Good" << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int i;
    for(i=1;i<=4;i++){
        int t,n;
        cin>>t>>n;
        if(t==1)    cout<<6000*n;
        if(t==2)    cout<<4000*n;
        if(t==3)    cout<<3000*n;
        if(t==4)    cout<<2000*n;
        cout<<endl;
    }
}



Measured memory_bytes: 3092
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
///(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)///
char prev(char c) {
	if (c == 'a')return 'Z';
	if (c == 'A')return 'z';
	else return c - 1;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (1) {
		int n;
		cin >> n;
		if (!n)break;
		vi v(n);
		REP(i, n)cin >> v[i];
		string s;
		cin >> s;
		REP(i, s.size()) {
			char c = s[i];
			REP(j, v[i%n])c = prev(c);
			cout << c;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3184
#include<iostream>
using namespace std;
int t[100000];
int n,m,a,b,ans=0,L,R,M;
int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>t[i];
  cin>>m;
  for(int i=0;i<m;i++){
    cin>>a;
    L=0;
    R=n;
    while(L<R){
      M=(L+R)/2;
      if(t[M]==a){
	break;
      }else if(t[M]<a){
	L=M+1;
      }else{
	R=M;
      }
    }
    
    if(L<R)ans++;
    
  }
  cout<<ans<<endl;
  return 0;
}

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

string s;
int n, k = 1, ans;
char a = '0';
int main() {
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++) {
		if (k == 1) {
			if (a != s[i]) {
				ans++;
				a = s[i];
			}
			else {
				k = 2;
			}
		}
		else {
			ans++;
			k = 1;
			a = '0';
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
int ga, sa, ba, gb, sb, bb;
int dp[26000000];
signed main() {
	cin >> n >> ga >> sa >> ba >> gb >> sb >> bb;
	int g = 0, s = 0, b = 0;
	int ans = n;
	//AとBの換どんパートが終わった時点での最大値
	for (int i = 0; i <= n; i += ga) {
		s = 0;
		for (int j = 0; i + j <= n; j += sa) {
			if (bb > ba) {
				int b = (n - i - j) / ba;
				ans = max(ans, n - i - j - b * ba + g * gb + s * sb + b * bb);
			}
			else {
				ans = max(ans, n - i - j + s * sb + g * gb);
			}
			s++;
		}
		g++;
	}
	int res = ans;
	//現在ドングリ250000個
	//dp[i]=使っていないドングリが残りiこの時の換金した後の増える値の最大値
	//これと決めたやつしか使う必要はない
	if (ga > gb) {
		for (int i = ans; i >= 0; i--) {
			if (i - gb >= 0) {
				dp[i - gb] = max(dp[i - gb], dp[i] + ga - gb);
			}
		}
	}
	if (sa > sb) {
		for (int i = ans; i >= 0; i--) {
			if (i - sb >= 0) {
				dp[i - sb] = max(dp[i - sb], dp[i] + sa - sb);
			}
		}
	}
	if (ba > bb) {
		for (int i = ans; i >= 0; i--) {
			if (i - bb >= 0) {
				dp[i - bb] = max(dp[i - bb], dp[i] + ba - bb);
			}
		}
	}
	int rer = 0;
	for (int i = 0; i <= ans; i++) {
		rer = max(rer, ans + dp[i]);
	}
	cout << rer << endl;
}

Measured memory_bytes: 196864