akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int prime[10000];
void init()
{
    memset(prime,0,sizeof(prime));
    for(int i=2;i<10000;i++)
    if(!prime[i])
    for(int j=i*2;j<10000;j+=i)
    prime[j]=1;
}
int main()
{
    long long  x,y;
    init();
    scanf("%lld%lld",&x,&y);
    if(x%y==0) printf("-1");
    else
    {
        for(int i=2;i<10000;i++)
        if(!prime[i]&&(i*x)%y!=0)
        {
            printf("%lld",i*x);
            break;
        }
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <climits>

using namespace std;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    vector<int> vc;
    int current = 0;
    for (int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        vc.push_back(x);
    }

    unsigned long cost = LONG_MAX;
    for (int l = 0; l <= n - k; ++l) {
        unsigned long lCost, rCost;
        int r = l + k - 1;
        lCost = abs(vc[l]) + abs(vc[r] - vc[l]);
        rCost = abs(vc[r]) + abs(vc[l] - vc[r]);
        cost = min(cost, min(lCost, rCost));
    }

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

    return 0;
}

Measured memory_bytes: 892
from bisect import bisect_left
import random
import time
import math
time_start = time.perf_counter()


#入力
D = int(input())
C = [int(c) for c in input().split()]
S = []
for _ in range(D):
    s = [int(x) for x in input().split()]
    S.append(s)
#初期解
T = []
for _ in range(D):
    t = random.randrange(26)
    T.append(t)


last_day = [[-1] for _ in range(26)]
for d in range(D):
    test = T[d]
    last_day[test].append(d)
for i in range(26):
    last_day[i].append(D)


T0 = 4000
while True:
    time_now = time.perf_counter()
    if time_now - time_start > 1.8:
        break
    #時間を正規化して温度を設定
    time_n = (time_now - time_start) // 1.8
    T1 = T0 * (1 - time_n)
    #ランダムな日のテストをランダムに入れ替え
    d = random.randrange(365)
    q = random.randrange(26)
    old = T[d]
    T[d] = q
    #日程dでの元のテストold
    l = last_day[old]
    ind_old = l.index(d)
    dd_left = l[ind_old] - l[ind_old-1] - 1
    dd_right = l[ind_old+1] - l[ind_old] - 1
    dd = l[ind_old+1] - l[ind_old-1] - 1
    dif_old = C[old] * (((dd_left * (dd_left + 1)) // 2) + ((dd_right * (dd_right + 1)) // 2) - ((dd * (dd + 1)) // 2))
    #日程dでのテストq
    l = last_day[q]
    ind_q = bisect_left(last_day[q],d)
    dd_left = d - l[ind_q-1] - 1
    dd_right = l[ind_q] - d - 1
    dd = l[ind_q] - l[ind_q-1] - 1
    dif_q = C[q] * (((dd * (dd + 1)) // 2) - ((dd_left * (dd_left + 1)) // 2) - ((dd_right * (dd_right + 1)) // 2))
    #変更による差
    dif_s = (dif_old + dif_q - S[d][old] + S[d][q])
    if (dif_s > 0) or (math.exp(dif_s / T1) > random.random()):
        del last_day[old][ind_old]
        last_day[q].insert(ind_q,d)
    else:
        T[d] = old
for d in range(365):
    print(T[d] + 1)



Measured memory_bytes: 87824
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static Input in = new Input(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int N = in.nextInt();
        int M = in.nextInt();
        Map<Integer, List<Integer>> road = new HashMap<>();
        for (int i = 0; i < M; i++) {
            int A = in.nextInt();
            int B = in.nextInt();
            road.computeIfAbsent(A, k -> new ArrayList<>()).add(B);
            road.computeIfAbsent(B, k -> new ArrayList<>()).add(A);
        }
        int[] C = new int[N + 1];
        C[1] = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(1);
        while (!deque.isEmpty()) {
            int from = deque.removeFirst();
            for (int to : road.get(from)) if (C[to] == 0) {
                C[to] = from;
                deque.addLast(to);
            }
        }
        out.println("Yes");
        for (int i = 2; i <= N; i++)
            out.println(C[i]);

        out.flush();
    }

    static class Input {
        private BufferedReader br;
        private String[] buff;
        private int index = 0;

        Input(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }
        String next() {
            while (buff == null || index >= buff.length) {
                buff = nextLine().split(" ");
                index = 0;
            }
            return buff[index++];
        }
        byte nextByte() {
            return Byte.parseByte(next());
        }
        short nextShort() {
            return Short.parseShort(next());
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        float nextFloat() {
            return Float.parseFloat(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
        BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }
    }
}



Measured memory_bytes: 80244
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#define INF 1000000000
using namespace std;
int main() {

	
		int h, w; cin >> h >> w;
		char c[60][60];
		int sx, sy, gx, gy;
		sx = 0; sy = 0; gx = h - 1; gy = w - 1;
		//cin >> sx >> sy >> gx >> gy;
		//sx--; sy--; gx--; gy--;
		int white = 0; int brack = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {	
				cin >> c[i][j];
				if (c[i][j] == '.') { white++; }
			}
		}

		vector<vector<int> > data(h, vector<int>(w, INF));
		queue<pair<int, int> > s;

		auto update = [&](int tate, int yoko, int kyori) {
			if (data[tate][yoko] != INF) { return; }
			data[tate][yoko] = kyori;
			s.push(pair<int, int>(tate, yoko));
		};

		update(sx, sy, 0);
		int di[4] = { -1,0,1,0 };
		int dj[4] = { 0,-1,0,1 };

		while (!s.empty()) {
			int i = s.front().first;
			int j = s.front().second; s.pop();

			for (int rin = 0; rin < 4; rin++) {
				int nta = i + di[rin], nyo = j + dj[rin];
				if (nta < 0 || nta >= h || nyo < 0 || nyo >= w) { continue; }
				if (c[nta][nyo] == '#') { continue; }
				update(nta, nyo, data[i][j] + 1);
			}
		}

		/*for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (data[i][j] == INF) { cout << "INF "; }
				else cout << data[i][j] << " ";
			}
			cout << endl;
		}*/
		
		if (data[gx][gy] == INF) { cout << "-1" << endl; return 0; }
		cout << white - (data[gx][gy] + 1) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int a,i,j,c=0;
    scanf("%d",&a);
    for(i=1;i<=9;i++)
    {
            for(j=1;j<=9;j++)
{
 
        if(i*j==a)
        {
         c++;
        }
}}
 
    if(c>0)
    printf("Yes");
    else
    printf("No");
    return 0;
}

Measured memory_bytes: 128
import java.lang.Math.*
fun main(args: Array<String>?): Unit {
    while(true){
        val n = readLine()!!.trim().toInt()
        if (n == 0) break
        val dices = List(n){Dice(readLine()!!.trim().split(' ')).normalization()}.distinct()
        println(n - dices.size)
    }
}
enum class Color : Comparable<Color>{
    Red, Yellow, Blue, Magenta, Green, Cyan
}
fun String.asColor(): Color {
    return when(this){
        "Red" -> Color.Red
        "Yellow" -> Color.Yellow
        "Blue" -> Color.Blue
        "Magenta" -> Color.Magenta
        "Green" -> Color.Green
        "Cyan" -> Color.Cyan
        else -> TODO()
    }
}
data class Dice(val top: Color, val bottom: Color, val up: Color, val down: Color, val right: Color, val left: Color) : Comparable<Dice> {
    override fun compareTo(other: Dice): Int {
        return listOf(top, bottom, up, down, right, left).compareTo(listOf(other.top, other.bottom, other.up, other.down, other.right, other.left))
    }
    fun normalization(): Dice = allPerspective().min()!!
    private fun allPerspective(): List<Dice> {
        return listOf(this, rotateUp(), rotateDown(), rotateRight(), rotateLeft(), flip()).flatMap{listOf(it, it.rotate90(), it.rotate180(), it.rotate270())}
    }
    private fun rotateUp(): Dice = Dice(down, up, top, bottom, right, left)
    private fun rotateDown(): Dice = rotateUp().rotateUp().rotateUp()
    private fun rotateRight(): Dice = Dice(left, right, up, down, top, bottom)
    private fun rotateLeft(): Dice = rotateRight().rotateRight().rotateRight()
    private fun flip(): Dice = rotateRight().rotateRight()
    private fun rotate90(): Dice = Dice(top, bottom, left, right, up, down)
    private fun rotate180(): Dice = rotate90().rotate90()
    private fun rotate270(): Dice = rotate90().rotate90().rotate90()
    companion object {
        operator fun invoke(faces: List<String>): Dice {
            return Dice(faces[0].asColor(), faces[5].asColor(), faces[4].asColor(), faces[1].asColor(), faces[2].asColor(), faces[3].asColor())
        }
    }
}
fun <T: Comparable<T>> List<T>.compareTo(that: List<T>): Int {
    for ((a, b) in this.zip(that)) {
        if (a != b) return a.compareTo(b)
    }
    return this.size.compareTo(that.size)
}


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

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

  int A, B;
  A = 1;
  while (A < 120) {
    bool judge = false;
    for (int i = -119; i < 119; i++) {
      int n = A*A*A*A*A - i*i*i*i*i;
      if (n == X) {
        judge = true;
        B = i;
        break;
      }
    }
    if (judge) break;
    A++;
  }
   cout << A << ' ' << B << endl;
}


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

int main()
{
	std::string s;
	std::cin >> s;
	unsigned int n{s.size() / 2};
	int count{};
	for (unsigned int i{}; i < s.size(); i++)
	{
		if (i < n && s[i] == 'g') count++;
		else if (i >= n && s[i] == 'p') count--;
	}
	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 512
n,x,y = map(int,input().split())
x -= 1
y -= 1
ans = [0 for _ in range(n)]
for i in range(n):
  for j in range(i+1,n):
    tmp = min(j-i,abs(j-y)+abs(i-x)+1)
    ans[tmp] += 1
    #print(i,j,tmp)
for i in range(1,n):
  print(ans[i])

Measured memory_bytes: 47708
#include<bits/stdc++.h>
#include<queue>
#include<utility>

using namespace std;
typedef pair<int, int> P;
const int MAX_N = 400;

const int di[] = {1, 0, -1, 0};
const int dj[] = {0, 1, 0, -1};

bool color[MAX_N][MAX_N];
int H, W;

char ch[MAX_N + 1];

void input(){
    cin>>H>>W;
    for(int i = 0; i < H; ++i){
        scanf("%s", ch);
        for(int j = 0; j < W; ++j){
            color[i][j] = (ch[j] == '#');
        }
    }
}

bool isin_(int i, int j){
    return i >= 0 && i < H && j >= 0 && j < W;
}

bool check_(int i, int j, int d){
    int ni = i + di[d];
    int nj = j + dj[d];
    if(!isin_(ni, nj)) return false;
    if(color[i][j] == color[ni][nj]) return false;
    return true;
}

bool used[MAX_N][MAX_N];

long long solve() {
    long long ans = 0;
    long long b = 0, w = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (used[i][j]) continue;
            b = 0;
            w = 0;
            queue<P> que;
            used[i][j] = true;
            que.push(P(i, j));
            while (!que.empty()) {
                P p = que.front();
                que.pop();
                int ci = p.first, cj = p.second;
                if (color[ci][cj]) b++;
                else w++;
                for (int d = 0; d < 4; ++d) {
                    if (!check_(ci, cj, d)) continue;
                    int ni = ci + di[d], nj = cj + dj[d];
                    if (used[ni][nj]) continue;
                    used[ni][nj] = true;
                    que.push(P(ni, nj));
                }
            }
            ans += b * w;
        }
    }
    return ans;
}

int main(){
    input();
    long long ans = solve();
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 512
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;

int main() {
	string S; cin >> S;
	long N; N = S.length();
	long res[100009] = {};

	long hm = 0;
	for (int i = 0; i < N; i++) {
        long start = i;
		while (S[i] == 'R') { hm++; i++; }
		long icon = i;

		while (S[i] == 'L') { hm++; i++; if (i == N) break;}
        long goal = i;
        long s1 = (icon - start) / 2;
        long s2 = (icon - start) - s1;
        long g1 = (goal - icon) / 2;
        long g2 = (goal - icon) - g1;
		res[icon - 1] = s2 + g1; res[icon] = s1 + g2;
        i--; hm = 0;
	}
	for (int i = 0; i < N; i++) cout << res[i] << " ";
    cout << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

vector<int> osa_k;
const int MAX = 1000010;
vector<int> sieve(int n) {
  vector<int> res(n);
  iota(res.begin(), res.end(), 0);
  for (int i = 2; i*i <= n; i++) {
    if (res[i] < i)
      continue;
    for (int j = i*2; j < n; j+=i)
      res[j] = i;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  osa_k = sieve(MAX);
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<bool> used(MAX);
  bool flag = true;
  rep(i, n) {
    int num = a[i];
    set<int> st;
    while (num > 1) {
      st.insert(osa_k[num]);
      num /= osa_k[num];
    }
    for (auto e : st) {
      if (used[e]) {
        flag = false;
        break;
      }
      used[e] = true;
    }
    if (!flag)
      break;
  }
  if (flag) {
    cout << "pairwise coprime\n";
    return 0;
  }
  int g = a[0];
  for (int i = 1; i < n; i++)
    g = gcd(a[i], g);
  if (g == 1)
    cout << "setwise coprime\n";
  else
    cout << "not coprime\n";
  return 0;
}

Measured memory_bytes: 11300
#include <bits/stdc++.h>
#define ok cout<<"ok"<<endl
#define dbg(x) cout<<(#x)<<" is "<<x<<endl
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
using namespace std;
typedef long long ll;
const int N=2*1009;
vector<int> vec[N];
int level[N],vis[N],cnt[N];
void bfs(int n,int k)
{
   memset(vis,0,sizeof vis);
   memset(level,0,sizeof level);
   int u,v,i,j;
   queue<int> q;
   q.push(k);
   vis[k]=1;
   level[k]=0;
   while(!q.empty())
   {
   	 u=q.front();
   	 q.pop();
   	 for(i=0; i<vec[u].size(); i++)
   	 {
   	 	 v=vec[u][i];
   	 	 if(vis[v]==0)
   	 	 {
   	 	 	vis[v]=1;
   	 	 	level[v]=level[u]+1;
   	 	 	q.push(v);
   	 	 }
   	 }
   }
   for(i=1; i<=n; i++)
   {
   	 cnt[level[i]]++;
   }
}
int main()
{
	fastio;
	int n,x,y,mn,mx,i,r,j;
	cin>>n>>x>>y;
    for(i=1; i<n; i++)
    {
    	vec[i].push_back(i+1);
    	vec[i+1].push_back(i);
    }
    vec[x].push_back(y);
    vec[y].push_back(x);
    for(i=1; i<=n; i++)
    {
    	bfs(n,i);
    }
    
    for(i=1; i<n; i++)
    {
    	cout<<cnt[i]/2<<endl;
    }

  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#include <math.h>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 998244353;
const int INF = LLONG_MAX/3;
const int MAX = 510000;

/*-----Library-----*/

struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
    vector<int> sizeuf; //要素数
    UnionFind(int n = 1) {
        init(n);
    }
    
    void init(int n = 1) {
        par.resize(n); rank.resize(n); sizeuf.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
            sizeuf[i]=1;
        }
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        sizeuf[x]+=sizeuf[y];
        return true;
    }
    
    int size(int x){
        return sizeuf[root(x)];
    }
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}

long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

/*-----Library-----*/
int n,m;
signed main(){
    cin>>n>>m;
    pair<pair<int,int>,int> es[114514];
    int a[114514]={};
    for(int i=0;i<m;i++){
        int l,r,c;
        cin>>l>>r>>c;
        es[i].first.first=l-1;
        es[i].first.second=r-1;
        es[i].second=c;
        a[l-1]++;
        a[r-1]--;
    }
    for(int i=0;i<n-1;i++){
        if(i!=0)a[i]+=a[i-1];
        if(a[i]==0){
            cout<<-1<<endl;
            return 0;
        }
    }
    sort(es,es+m);
    int dis[114514];
    for(int i=0;i<n;i++)dis[i]=INF;
    dis[0]=0;
    for(int i=0;i<m;i++){
        es[i].second+=dis[es[i].first.first];
        int ite=upper_bound(dis,dis+es[i].first.second+1,es[i].second-1)-dis;
        if(ite>es[i].first.second||ite<0)continue;
        else{
            for(int j=ite;j<=es[i].first.second;j++)dis[j]=es[i].second;
        }
    }
    cout<<dis[n-1]<<endl;
    return 0;
}


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

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

Measured memory_bytes: 3636
n = gets.to_i

a, b, c = 3.times.map{ gets.split.map(&:to_i).sort }
c.reverse!

res = b.inject(0) do |r, bi|
  ai = a.bsearch_index{ |x| x >= bi }
  ci = c.bsearch_index{ |x| x <= bi }
  r + (ai || n)*(ci|| n)
end
 
puts res


Measured memory_bytes: 24288
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;
using Int = long long;
typedef pair<int,int> Pi; typedef pair<Int,Int> Pl;
constexpr int mod = 1e9+7;
constexpr int INF32 = numeric_limits<int>::max();
constexpr Int INF64 = numeric_limits<Int>::max();
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define Pr(t) priority_queue<t>
#define gPr(t) priority_queue<t,vector<t>,greater<t>>
#define V(t) vector<t>
#define rer(i,l,r) for(int i=(l); i<(r); ++i)
#define rep(i,n) rer(i,0,n)
#define gnr(i,l,r) for(int i=(r)-1; i>=(l); --i)
#define pri(a) cout<<(a)<<'\n'
#define pri2(a,n) {rep(i,n-1)cout<<a[i]<<' '; if(n)cout<<a[n-1]<<'\n';}
#define prip(p) cout<<(p).fi<<' '<<(p).se<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

Int n,m,_,x,y,q;
string s,sb;
bool ok;
char cf,cb;

int main(){
  cin.tie(nullptr); ios::sync_with_stdio(0);
  //cout<<fixed<<setprecision(20);

  cin>>n>>x>>y; Int h[n]; rep(i,n)cin>>h[i]; q=x-y;
  Int ng=0,ok=1e10;
  while(ok-ng>1){
    Int t=(ok+ng)/2;
    Int cnt=0;
    rep(i,n)cnt+=(max(0LL,(h[i]-t*y))+q-1)/q;
    if(cnt<=t)ok=t;
    else ng=t;
  }
  pri(ok);
}


Measured memory_bytes: 4408
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(int i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")


int main() {
	int N, M;
	cin >> N >> M;
	int kl, kr, gl, gr;
	kl = 1;
	kr = 2*((N+1) / 4);
	gl = kr + 1;
	gr = (N % 2 == 0) ? N - 1 : N;
	bool next_k = true;
	for (int i = 0; i < M; ++i) {
		if (next_k) {
			PRI(kl <<" "<< kr);
			++kl;
			--kr;
			next_k = false;
		}
		else {
			PRI(gl <<" "<< gr);
			++gl;
			--gr;
			next_k = true;
		}
	}
	return 0;
}




Measured memory_bytes: 3584
N = int(input())
CSF = [list(map(int,input().split())) for _ in range(N-1)]

for i in range(N):
  t = 0
  for j in range(i,N-1):
    if(t < CSF[j][1]):
      t = CSF[j][1]
    elif(t%CSF[j][2] == 0):
      pass
    else:
      t += CSF[j][2]-t%CSF[j][2]
    t += CSF[j][0]
  print(t)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

ll dp[22][2100000];

int main(){fastio
    ll n;cin>>n;
    ll a[n+1][n+1];rep(i,1,n)rep(j,1,n)cin>>a[i][j];
    ll pp=(1<<n);
    //ll dp[n+1][pp];
    dp[0][0]=1;
    ll sum=0;
    rep(i,1,n){
        rep(j,0,pp-1){
            dp[i][j]=0;
            sum=0;
            rep(k,0,n-1){
                if((j>>k)&1)sum++;
            }
            if(sum!=i)continue;
            rep(k,0,n-1){
                if(a[i][k+1]){
                    dp[i][j]=mod(dp[i][j]+dp[i-1][j&(pp-1-(1<<k))]);
                }
            }
        }
    }
    cout<<dp[n][pp-1]<<endl;
    
    return 0;
}



Measured memory_bytes: 344832
n = int(input())
x = [int(v) for v in input().split()]

x_sorted = sorted(x)
m1 = x_sorted[n//2 - 1]
m2 = x_sorted[n//2]

for v in x:
    if v <= m1:
        print(m2)
    else:
        print(m1)

Measured memory_bytes: 26772
// Math = ♥️

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set                            \
    tree<ll, null_type, less<ll>, rb_tree_tag, \
         tree_order_statistics_node_update>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, t;
    cin >> n >> t;

    vi arr(n);
    for (auto &it : arr) {
        cin >> it;
    }

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ans += min(t, arr[i] - arr[i - 1]);
    }
    ans += t;

    cout << ans << "\n";
}



Measured memory_bytes: 4732
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;

int main()
{
	int x,n,k = 1;
	scanf("%d",&n);
	for(int i = 1;i <= n;++i){
		scanf("%d",&x); 
		if(x == k){
			k++;
		}
	}
	k--;
	if(!k) printf("-1\n");
	else printf("%d\n",n-k);
	return 0;
}

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

const int N=55;
int x[N],y[N];
int n,k;
int val[N],c;

signed main()
{
	cin>>n>>k;
	for(register int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	
	long long ans=LLONG_MAX;
	for(register int a=1;a<=n;a++)
		for(register int b=1;b<=n;b++)
			for(register int c=1;c<=n;c++)
				for(register int d=1;d<=n;d++)
				{
					int x1=x[a],y1=y[b],x2=x[c],y2=y[d];
					if(x1>x2||y1>y2) continue;
					int cnt=0;
					for(register int i=1;i<=n&&cnt<k;i++)
						if(x1<=x[i]&&x[i]<=x2&&y1<=y[i]&&y[i]<=y2)
							cnt++;
					if(cnt==k) ans=min(ans,(x2-x1)*1ll*(y2-y1));
				}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int main()
{
	 ll n;
	 cin>>n;
	 cout<<3*n*n;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;
int main(){
  int m[10];
  for(int i = 0; i < 10; i++){
    cin >> m[i];
  }
   int i,j,p;
    for(int i = 0; i < 10; i++) {
    for(int j = 9; j > i; j--) {
      if(m[j] < m[j - 1]) {
        p = m[j];
        m[j] = m[j - 1];
        m[j - 1] = p;
      }
    }
    }
  cout << m[9] << endl;
  cout << m[8] << endl;
  cout << m[7] << endl;
}
  


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

  
int main(){
  int n;
  cin >> n ;
  vector<int> x(n);
 rep(i,n){
   cin >>x.at(i);
 }
  int sum=0;
  rep(i,n){
    sum+=x.at(i);
  }
  double px=sum*1.0000/n;
    int py=sum*1/n;
    int pr;
  if(px-py>=0.5)pr=py+1;
  else if(px-py<0.5) pr=py;
  int count=0;
  rep(i,n){
    count+=(x.at(i)-pr)*(x.at(i)-pr);
  }
  cout << count << endl;
}
  
 

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

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define whole(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

const int N = int(2e5) + 2;
const int LG = 20;
const ll mod = 998244353;
const int INF = (int)1e9 + 7;
const ll linf = 1e18;
const ld pi = acos(-1);
const int base = 10;
const ld EPS = 1e-9;

int n, a[N];
int main (){
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) scanf ("%d", a + i);
    int ans = 0;
    for (int i = 2; i < n; ++i){
        vector < int > kek;
        kek.pb(a[i]);
        kek.pb(a[i + 1]);
        kek.pb(a[i - 1]);
        sort (whole(kek));
        if (kek[1] == a[i]) ++ans;
    }
    return !printf ("%d\n", ans);
}


Measured memory_bytes: 256
package main

import "fmt"
import "sort"

func main() {
	var N int
	fmt.Scanf("%d", &N)

	dupes := map[string]int{}
	for i := 0; i < N; i++ {
		var s string
		fmt.Scanf("%s", &s)

		ns := make([]int, len(s))
		for i, b := range s[:] {
			ns[i] = int(b)
		}
		sort.Sort(sort.IntSlice(ns))

		bs := make([]byte, len(s))
		for i, r := range ns {
			bs[i] = byte(r)
		}

		e := string(bs)
		dupes[e] = dupes[e] + 1
	}

	var ans int64
	for _, c := range dupes {
		ans += int64(c) * int64(c-1)
	}
	fmt.Println(ans / 2)
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
int main(){
    int n,a,b,c,l[20],x[8],ans=1e9;
    cin>>n>>a>>b>>c;
    rep(i,n) cin>>l[i];
    rep(i,pow(4,n)){
        int p=i,A=0,B=0,C=0,m=0,d[3]={0};
        rep(j,n) x[j]=p%4,p=p/4;
        rep(j,n){
            if(x[j]==1){A+=l[j],d[0]++;if(d[0]>1) m+=10;}
            if(x[j]==2){B+=l[j],d[1]++;if(d[1]>1) m+=10;}
            if(x[j]==3){C+=l[j],d[2]++;if(d[2]>1) m+=10;}
        }
        if(A==0||B==0||C==0) continue;
        m+=abs(A-a)+abs(B-b)+abs(C-c);
        if(ans>m) ans=m;
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int a, b, c, i;
  i = 0;

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



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

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

//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 iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)

//repetition
//------------------------------------------
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)

//constant
//--------------------------------------------
const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

// output vector
// ------------------------------------------
namespace std {
    template<typename T> ostream & operator<<(ostream& os, vector<T> const& v){
        for(auto it=v.begin(); it!=v.end(); ++it){
            os << *it << (it+1==v.end() ? "" : ",");
        }
        return os;
    }
}

//clear memory
#define clr(a) memset((a), 0 ,sizeof(a))

int lcm(int a,int b){
   return a*b/__gcd(a,b);
}
 
vb pn((int)1e4+10); 
void prime_number(int n){
   fill(all(pn),true);
   pn[0]=false;pn[1]=false;
   loop(i,2,n/2+1){
      if(!pn[i]) continue;
      for(int j=2;i*j<=n;j++){
         pn[i*j]=false;
      }
   }
}

int main(){
   int n,c,ans;
   while(cin>>n){
      if(n==0)break;
      ans=0;
      rep(i,n/4){
         cin>> c;
         ans+=c;
      }
      cout << ans << endl;
   }
}

Measured memory_bytes: 1196
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as VU
import qualified Data.Map as MP
import Data.Char

make :: VU.Vector Int -> MP.Map Int Int
make vec = VU.foldl' step MP.empty vec
    where
        step :: MP.Map Int Int -> Int -> MP.Map Int Int
        step m v = 
            case MP.lookup v m of
                Just _ -> MP.adjust (+1) v m
                Nothing -> MP.insert v 1 m 

solve :: MP.Map Int Int -> Int -> Int
solve m acc
    | MP.null m = 0
    | v >= 4 && acc == 0 = k * k
    | v >= 2 && acc /= 0 = k * acc
    | v >= 2 && acc == 0 = solve m' k
    | otherwise = solve m' acc
        where
            ((k,v), m') = MP.deleteFindMax m

main = do
    n <- readLn :: IO Int 
    xs <- VU.unfoldrN n (B.readInt . B.dropWhile isSpace) <$> B.getLine
    print $ solve (make xs) 0

Measured memory_bytes: 17660
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  int H,W;
  cin>>H>>W;
  vector<char> vec(H*W);//vecは各頂点の白か黒かを保持
  vector<int> answer(H*W+1,H+W);//各黒点からの距離のうち小さいものを保持(随時更新)
  for(ll i=0;i<H*W;i++){
    cin>>vec.at(i);
  }
  using Graph=vector<vector<int>>;
  Graph G(H*W+1);//グラフのサイズはマス目のサイズ+最初の仮想の点分の1
  for (ll i=0;i<H*W;++i){//グラフの作成
    if(vec.at(i)=='#'){//仮想の点からの辺を定義
      G[H*W].push_back(i);
    }
    if(i%W!=W-1){//左右方向の辺の定義
      G[i].push_back(i+1);
      G[i+1].push_back(i);
    }
    if(i<W*(H-1)){//上下方向の辺の定義
      G[i].push_back(i+W);
      G[i+W].push_back(i);
    }
  }
  vector<int> dist(H*W+1,-2);//全頂点を「未訪問」に初期化(-2だったら未訪問と判断)
  queue<int> que;
  dist[H*W]=-1;//仮想の点をスタートにする
  que.push(H*W);
  while(!que.empty()){
    int v=que.front();//キューから先頭頂点を取り出す
    que.pop();
    for(int nv:G[v]){//vから辿れる頂点をすべて調べる
      if(dist[nv]!=-2){continue;}//すでに発見済みの頂点は探索しない
      dist[nv]=dist[v]+1;//新たな白色頂点nv について距離情報distを更新してキューに追加する
      answer.at(nv)=min(answer.at(nv),dist[nv]);//各黒点からの距離の最小値を必要に応じて更新
      que.push(nv);
    }
  }
  int rock=0;//rockは各白点の(各黒点からの距離の最小値の)最大値を保持(随時更新)
  for(ll i=0;i<H*W;i++){
    if(vec.at(i)=='.'){rock=max(answer.at(i),rock);}
  }
  cout<<rock<<endl;
}

Measured memory_bytes: 71916
#include <iostream>
                        #include<cmath>
                        #include<string>
                        using namespace std;
                        int main()
                        {
                          int a,b,c;
                          cin>>a>>b>>c;
                         if(a==b || b==c || a==c)
                         {
                            if(a==b && b==c)
                          {
                            cout<<"No";
                          }
                           else
                             cout<<"Yes";
                         }
                          else
                            cout<<"No";
                        }

Measured memory_bytes: 3596
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt(),m=sc.nextInt();
    Set<Integer> set = new HashSet<>();
    int[] a= new int[m],b=new int[m];
    for(int i=0;i<m;i++) {
    	a[i]=sc.nextInt();
    	b[i]=sc.nextInt();
    	if(a[i]==1)set.add(b[i]);
    }
    for(int i=0;i<m;i++) {
    	if(b[i]==n) {
    		if(!set.add(a[i])) {
    			 System.out.println("POSSIBLE");
    			 System.exit(0);
    		}
    	}
    }
    System.out.println("IMPOSSIBLE");
  }
}


Measured memory_bytes: 111256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

int c[10][1005] = {};

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int H,W,K; cin >>H>>W>>K;
    vector<string> S(H);
    REP(i,H) cin >> S[i];
    int ans = INF;
    for(int div = 0; div < (1 << (H-1)); div++){
        int g = 0;
        VI id(H);
        REP(i,H){
            id[i] = g;
            if((i != H-1) && (div >> i) & 1) g++;
        }
        g++;
        REP(i,g) REP(j,W) c[i][j] = 0;
        REP(i,H) REP(j,W) c[id[i]][j] += (S[i][j] - '0');

        int num = g-1;
        VI now(g);
        auto add = [&](int j){
            REP(i,g) now[i] += c[i][j];
            REP(i,g) if(now[i] > K) return false;
            return true;
        };
        REP(j,W){
            if(!add(j)){
                num++;
                now = VI(g);
                if(!add(j)){
                    num = INF;
                    break;
                }
            }
        }
        ans = min(ans,num);
    }
    cout << ans << endl;

}


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

#define int              long long 
#define FOR( i, m, n )   for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )      FOR( i, 0, n )
#define ALL( a )         (a).begin(), (a).end()
#define fi               first
#define se               second

typedef pair<int, int> P;

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

const int INF = 1e9;

signed main(){
  int n, m;
  while( cin >> n, n ){
    vector<P> gems( n );
    REP( i, n ) cin >> gems[i].fi >> gems[i].se;
    cin >> m;
    vector<pair<char, int> > com( m );
    REP( i, m ) cin >> com[i].fi >> com[i].se;

    vector<bool> ok( n );
    int sx = 10, sy = 10;
    REP( i, m ){
      int tx = sx, ty = sy;
      if( com[i].fi == 'N' ) sy += com[i].se;
      if( com[i].fi == 'S' ) sy -= com[i].se;
      if( com[i].fi == 'E' ) sx += com[i].se;
      if( com[i].fi == 'W' ) sx -= com[i].se;

      if( sx > tx ){
         REP( j, n ){
	   if( tx <= gems[j].fi && gems[j].fi <= sx && sy == gems[j].se ) ok[j] = true;
         }
      }else if( sx < tx ){
	REP( j, n ){
	   if( sx <= gems[j].fi && gems[j].fi <= tx && sy == gems[j].se ) ok[j] = true;
         }
      }else if( sy > ty ){
	REP( j, n ){
	   if( sx == gems[j].fi && ty <= gems[j].se && gems[j].se <= sy ) ok[j] = true;
         }
      }else if( sy < ty ){
        REP( j, n ){
	   if( sx == gems[j].fi && sy <= gems[j].se && gems[j].se <= ty ) ok[j] = true;
         }
      }

    }

    bool flag = true;
    REP( i, n ){
      if( !ok[i] ){
	flag = false;
	break;
      }
    }

    cout << ( flag ? "Yes" : "No" ) << endl;
  }
}



Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long h,n,s,sum=0;
  cin>>h>>n;
  while(n--)
  {
    cin>>s;
    sum+=s;
  }
  
  if(sum>=h)
    cout<<"Yes";
  else
    cout<<"No";
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,cc;
map<long long,int>mp;
set<int>g[100005];
queue<pair<int,int> >q;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<2*n-2;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		mp[(long long)u*n+v]++;mp[(long long)v*n+u]++;
		g[u].insert(v);g[v].insert(u);
		if(mp[(long long)u*n+v]==2)q.push(make_pair(u,v));
	}
	while(!q.empty())
	{
		int u=q.front().first,v=q.front().second;q.pop();
		if(mp[(long long)u*n+v]!=2)continue;
		cc++;
		if(g[u].size()<g[v].size())swap(u,v);
		while(g[v].size())
		{
			int w=*g[v].begin();
			mp[(long long)u*n+w]+=mp[(long long)v*n+w];
			mp[(long long)w*n+u]+=mp[(long long)w*n+v];
			mp[(long long)v*n+w]=mp[(long long)w*n+v]=0;
			g[u].insert(w);g[w].insert(u);g[v].erase(w);g[w].erase(v);
			if(mp[(long long)u*n+w]==2)q.push(make_pair(u,w));
		}
	}
	if(cc==n-1)puts("YES");else puts("NO");
	return 0;
} 

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

#define N 100000
#define INF 1e9
int a[N];
int dp[N];

int main () {
  int n;
  cin >> n;
  REP(i,n) cin >> a[i];

  fill(dp, dp+n, INF);
  for(int i = 0; i < n; i++){
    *lower_bound(dp, dp+n, a[i]) = a[i];
  }

  cout << (lower_bound(dp, dp+n, INF) - dp) << endl;

  return 0;
}

Measured memory_bytes: 3888
#include<iostream>

using namespace std;

int main() {
	int n,a[1000];

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

	for (int i = 0; i < n; i++) {
		int temp,j;
		temp = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > temp) {
			a[j + 1] = a[j];
			a[j] = temp;
			j--;
		}
		for (int k = 0; k < n; k++) {
			if (k < n - 1)cout << a[k] << " ";
			else cout << a[k] << endl;
		}
	}
	return 0;
}

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

int main() {
    int a, b;

    cin >> a >> b;

    if(a < b) {
        cout << "a < b" << endl;
    }
    else if(a > b) {
        cout << "a > b" << endl;
    }
    else {
        cout << "a == b" << endl;
    }

    return 0;
}


Measured memory_bytes: 3084
#include <iostream>
#define D(x) std::cout << __LINE__ << ' ' << #x << " = " << x << std::endl;

int main() {
#ifndef LOCAL_STJO
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif
	std::string s;
	std::cin >> s;
	int cnt = 0;
	for(auto c : s) cnt += (c == '1');
	std::cout << cnt << std::endl;
    return 0;
}



Measured memory_bytes: 764
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

int main(){
  int x;
  cin>>x;
  if(x>=30){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
}

Measured memory_bytes: 3672
///HELLO THERE~!
///CREATED BY MD SADMAN MEHEDI SIVAN [IUT CSE(SWE)-19]

#include<bits/stdc++.h>
using namespace std;

#define fastio          ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define read            freopen("blue.txt","r",stdin);
#define write           freopen("red.txt","w",stdout);

using ll=long long;
using ull=unsigned long long;
const double pi = 2*acos(0.0);


int  main()
{
    char c ;
    cin>>c;
    if(c>='A' && c<='Z')
    {
        cout<<"A";
    }
    else
        cout<<"a";



    return 0;


}


Measured memory_bytes: 3628
N, K = map(int, input().split())
box = [n for n in range(N+1)]
MOD = int(1e9) + 7
ans = 0

# 部分和
bubu = []
bubu.append(box[0])
for el in range(N+1):
    if el == 0:
        continue
    else:
        bubu.append(bubu[el - 1] + box[el])

rbubu = []
rbubu.append(box[-1])
for el in reversed(range(N+1)):
    if el == N:
        continue
    else:
        rbubu.append(rbubu[-1] + box[el])

for i in range(K, N+2):
    temp = (rbubu[i-1] - bubu[i-1] + 1) % MOD
    ans += temp
    ans = ans % MOD

print(ans)

Measured memory_bytes: 38336
/*****/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);
#include <stdexcept>

//#define int long long

using namespace std;
using ll = long long;
using ld = long double;
using vecll = vector<ll>;

#define nextline() (std::cerr << "\n")
#define debug(x) (#x " : " + (x))
#define debug_cout(x) (std::cerr << #x << " : " <<  (x) << "\n")
#define debug_tabcout(n, x) (std::cerr << strMulti("\t",n) << #x << " : " <<  (x) << "\n")
#define debug_headcout(h, x) (std::cerr << h << " : " <<  (x) << "\n")
#define debug_tabheadcout(n, h, x) (std::cerr << strMulti("\t",n) << h << " : " <<  (x) << "\n")

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(int i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(int i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(int i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair(a, b);
constexpr int INF = 2000000100;
constexpr ll DIV = 1000000007;	// 10e9+7
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> T divup(T a, T b) { if (a % b == 0) { return a / b; } return a / b + 1; }
#define diup(a, b) (a % b == 0 ? a / b : a / b + 1)
#define exist_in(list, value) (list.end() != std::find(all(list),value))
std::string strMulti(std::string t, int n) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; }
//template<class T> T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; }
//template<class T> T math_C(T m, T n) { T ret = mathP(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; }
//template<class T> bool compare_by_b(pair<T, T> a, pair<T, T> b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; }
//template<class T> T math_gcd(T a, T b) { a = abs(a); b = abs(b); if (a < b) { std::swap(a, b); } T tmp; while (b != 0) { tmp = b; b = a % b; a = tmp; } return a; }
//template<class T> T math_lcm(T a, T b) { a = abs(a); b = abs(b); if (a > b) { std::swap(a, b); } if (a == 1) { return b; } T i = a; while (i % b != 0) { i += a; } return i; }
//template<class T1, class T2> bool exist_in(const T1& list, const T2& v) { return (list.end() != std::find(list.begin(), list.end(), v)); }
//template<class T> bool exist_in(const T& c, const typename T::value_type& v) {	return (c.end() != std::find(c.begin(), c.end(), v));}

/*****/

void Main()
{
	int n, a, b;
	cin >> n >> a >> b;
	int min = INF;
	chmin(min, n * a);
	chmin(min, b);
	cout << min;
}

/*****/

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

	std::cout << std::fixed << std::setprecision(10);


	/*
	while (true)
	{
		Main();
		cout << endl;
	}
	//*/


	Main();

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

int count(int n) {
    int res = 0;
    while(n) {
        res += n & 1;
        n >>= 1;
    }
    return res;
}
int main() {
    // freopen("1.txt", "r", stdin);
    int N, mod = 1e9 + 7;
    cin >> N;
    int a = 1 << N;
    int C[N][N], dp[a];
    memset(dp, 0, sizeof(dp));

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            cin >> C[i][j];
    
    dp[0] = 1;
    for(int i = 1; i < a; ++i) {
        int ones = count(i);
        for(int j = 0; j < N; ++j) {
            if((i & (1 << j)) && C[ones - 1][j]) {
                dp[i] = (dp[i] + dp[i - (1 << j)]) % mod;
            }
        }
    }
    cout << dp[a - 1] << endl;
    
    return 0;
}


Measured memory_bytes: 8448
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>
typedef long long ll;
using namespace std;

int main()
{
	int n;
	cin >> n;
	int h[n];
	for (int i = 0; i < n; i++)	cin >> h[i];
	if (n == 1)
	{
		cout << "Yes" << endl;
		return (0);
	}
	else
	{
		for (int i = n - 1; i >= 1; i--)
		{
			if (h[i] < h[i - 1])
			{
				if (h[i] == h[i - 1] - 1)
				{
					h[i - 1] -= 1;
				}
				else
				{
					cout << "No" << endl;
					return (0);
				}
			}
		}
		cout << "Yes" << endl;
		return (0);
	}
}


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

int main() {
  string S;
  cin >> S;
  
  int longest = 0;
  int l = 0;
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == 'A' || S[i] == 'T' || S[i] == 'G' || S[i] == 'C') {
      l++;
      longest = max(longest, l);
    } else {
      l = 0;
    }
  }

  cout << longest << endl;
}

Measured memory_bytes: 256