akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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 C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    string T, S;
    cin >> S >> T;

    cout << T + S << endl;

    return 0;
}

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

struct triangle{
	int a, b, c;
	int jugde;
};

int main(){
	int n, i, c;
	struct triangle* dataset;

	scanf("%d", &n);

	dataset = (struct triangle*)malloc(sizeof(struct triangle) * n);

	for(i = 0; i < n; i++){
		scanf("%d %d %d", &((dataset+i)->a), &((dataset+i)->b), &((dataset+i)->c));
		if((dataset+i)->a < (dataset+i)->b){
			c = (dataset+i)->a;
			(dataset+i)->a = (dataset+i)->b;
			(dataset+i)->b = c;
		}
		if((dataset+i)->a < (dataset+i)->c){
			c = (dataset+i)->a;
			(dataset+i)->a = (dataset+i)->c;
			(dataset+i)->c = c;
		}
		if((dataset+i)->a*(dataset+i)->a == (dataset+i)->b*(dataset+i)->b + (dataset+i)->c*(dataset+i)->c) (dataset+i)->jugde = 1;
		else (dataset+i)->jugde = 0;
	}

	for(i = 0; i < n; i++){
		if((dataset+i)->jugde == 1) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 592
import numpy as np
N,K=map(int,input().split())
A=np.array(sorted(list(map(int,input().split()))))
F=np.array(sorted(list(map(int,input().split())), reverse=True))
s=A.sum()
l=-1
r=10**12+2
while l+1<r:
    m=(l+r)//2
    if s-np.minimum(A,m//F).sum()<=K:
        r=m
    else:
        l=m
print(r)

Measured memory_bytes: 37264
#include <bits/stdc++.h>
using namespace std;
#define rep(i,i1,n) for(int i=(int)(i1);i<(int)(n);i++)
#define ll long long
#define vi vector<int>
#define vll vector<long long>
using graph = vector<vector<int>>;

int main() {
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll ac,ad,bc,bd;
  ac=a*c;
  ad=a*d;
  bc=b*c;
  bd=b*d;
  cout<<max({ac,ad,bc,bd});
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
using lint = int64_t;

int main() {
    lint N, M;
    cin >> N >> M;
    vector<lint> A(N);
    rep(i, N) cin >> A[i];
    
    sort(A.begin(), A.end());
    M = N * N - M;
    lint left = -1, right = 20000000000;
    while (right - left > 1) {
        lint mid = (right + left) / 2;
        lint cnt = 0;
        rep(i, N) cnt += upper_bound(A.begin(), A.end(), mid - A[i]) - A.begin();
        if (cnt <= M) left = mid;
        else right = mid;
    }
    vector<lint> sum(N + 1, 0);
    rep(i, N) sum[i + 1] = sum[i] + A[i];
    lint ans = 0;
    rep(i, N) {
        int idx = upper_bound(A.begin(), A.end(), right - A[i]) - A.begin();
        ans += (sum[N] - sum[idx]) + A[i] * (N - idx);
    }
    M = N * N - M;
    lint used = 0;
    rep(i, N) used += A.end() - upper_bound(A.begin(), A.end(), right - A[i]);
    ans += right * (M - used);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1792
// https://atcoder.jp/contests/abc088/tasks/abc088_b

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{
  /* Magic word */
  // cin.tie(0);
  // ios::sync_with_stdio(false);
  /* ---------- */

  int n, ai, aT = 0, bT = 0;
  vector<int> a;

  cin >> n;
  while (n--)
  {
    cin >> ai;
    a.push_back(ai);
  }

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

  bool turn_a = true;
  for (auto &x : a)
  {
    if (turn_a)
      aT += x;
    else
      bT += x;
    turn_a = !turn_a;
  }

  cout << (aT - bT) << '\n';

  return 0;
}


Measured memory_bytes: 256
void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <limits.h>

using namespace std;
using namespace boost::multiprecision;

int N;
vector<int> v;
int dp[100001];

void solve() {
	cin >> N;
	v.push_back(1);
	int n = 6;
	while (n <= N) {
		v.push_back(n);
		n *= 6;
	}
	n = 9;
	while (n <= N) {
		v.push_back(n);
		n *= 9;
	}
	dp[0] = 0;
	for (int n = 1; n <= N; n++) {
		dp[n] = N;
		for (int c = 0; c < v.size(); c++) {
			if (n >= v[c])dp[n] = min(dp[n],dp[n-v[c]]+1);
		}
	}
	cout << dp[N] << endl;
	return;
}


Measured memory_bytes: 640
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    s = S()
    d = deque(s)
    ans = 0

    # print(d)

    while len(d) > 1:
        if d[0] == d[-1]:
            d.popleft()
            d.pop()
        elif d[0] == 'x':
            d.append('x')
            ans += 1
        elif d[-1] == 'x':
            d.appendleft('x')
            ans += 1
        else:
            print(-1)
            return

    print(ans)


if __name__ == '__main__':
    main()


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

int main(){

    //入力
    int N, K;
    int A[200010];

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

    //処理　バケツを用意種類を数える　多かったら小さい順に並び変えたりする

    int b[200010]; // b[i]にiがいくつあるかを格納している
    int ans=0;

    for(int i=0; i< 200005; i++){
        b[i]=0;
    }

    for(int i = 0; i < N; i++){
        b[ A[i] ] = b[ A[i] ]+1;
    }

    int frag; //今の種類
/*    
    for(int i = 0; i < 200005 ;i++){
        if(b[i] > 0){
            frag++;
        }
    }

    if (frag <= K){
        ans = 0;
    }
*/
/*
        sort(b,b+N);
        int k; // ゼロでないやつ
        k=1;
        while(b[k]==0){
            k++;
        }
        if ((N-k) <= K ){ans = 0;}
        else{
            for(int i=0; i< N-K-k+1;i++){
                ans = ans + b[k+i];
            }
        }
    cout << ans << endl;

*/

    sort(b,b+N, greater<int>());

    int sum=0;
    for(int i=0; i< K; i++){
        sum=sum+b[i];
    }
    
    cout << N-sum << endl;
}

Measured memory_bytes: 1920
import java.util.*
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val s = cin.next()
    val l = s.length
    
    var rec_all = -1

    for (i in 0..l-1) {
        val c = s[i]
        var count = 0
        var rec_max = 0

        for (j in 0..l-1) {
            val k = l - j - 1
            if (s[k] == c) {
                count = 0
            } else {
                count += 1
                if (count > rec_max) {
                    rec_max = count
                }
            }
        }

        if (0 > rec_all || rec_all > rec_max) {
            rec_all = rec_max
        }
    }

    println(rec_all)
}

Measured memory_bytes: 31512
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    long long temp = 0;
    long long ans = 0;
    for(int i = 0; i < N; i++){
        if(A[i] == 0){
            ans += temp / 2;
            temp = 0;
        }
        else temp += A[i];
    }
    ans += temp / 2;
    cout << ans << endl;
}

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

string S;

int main() {
    cin >> S;
    int N = (int) S.length();
    int ans = N;
    for (int i = 1; i < S.length(); i++) {
        if (S[i] != S[i - 1]) {
            ans = min(ans, max(i, N - i));
        }
    }
    cout << ans << endl;
}



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

int main() {
  string s;
  char c;
  int q, t, f = 0;
  cin >> s;
  cin >> q;
  bool is_front = true;
  vector<char> vf, vb;
  while (q--) {
    cin >> t;
    if (t == 1) {
      if (s.size() == 1 && f == 0) continue;
      is_front = !is_front;
    } else {
      cin >> f >> c;
      if (f == 1) {
        if (is_front) vf.push_back(c);
        else vb.push_back(c);
      } else {
        if (is_front) vb.push_back(c);
        else vf.push_back(c);
      }
    }
  }
  if (is_front) {
    for (auto it = vf.rbegin(); it != vf.rend(); ++it) cout << *it;
    cout << s;
    for (auto it = vb.begin(); it != vb.end(); ++it) cout << *it;
  } else {
    for (auto it = vb.rbegin(); it != vb.rend(); ++it) cout << *it;
    reverse(s.begin(), s.end());
    cout << s;
    for (auto it = vf.begin(); it != vf.end(); ++it) cout << *it;
  }
}

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

using lint = long long;

vector<vector<int>> edges;
vector<int> depth, mindepth, parent, was;
int timer;
void dfs(int v) {
	was[v] = timer;
	mindepth[v] = depth[v];
	for (int u : edges[v]) {
		if (u == parent[v]) continue;
		if (was[u] == timer) {
			mindepth[v] = min(mindepth[v], depth[u]);
			continue;
		}
		depth[u] = 1 + depth[v];
		parent[u] = v;
		dfs(u);
		mindepth[v] = min(mindepth[v], mindepth[u]);
	}
}

vector<int> cutpoints() {
	const int n = edges.size();
	vector<int> cut(n);
	vector<int> child(n);
	for (int i = 0; i < n; ++i) {
		// cout << mindepth[i] << ' ' << depth[parent[i]] << endl;
		if (parent[i] != -1 && mindepth[i] >= depth[parent[i]]) {
			cut[parent[i]] = true;
		}
		// if (parent[i] != -1) child[parent[i]]++;
	}
	// vector<int> child(n);
	for (int i = 0; i < n; ++i) {
		if (parent[i] != -1) child[parent[i]]++;
	}
	for (int i = 0; i < n; ++i) {
		if (parent[i] == -1 && child[i] < 2) cut[i] = false;
		// else if (cut[i]);//cout << i << '\n';
	}
	
	return cut;
}

vector<pair<int,int>> find_bridges() {
	vector<pair<int,int>> bridges;
	// cout << "aa" << endl;
	for (int i = 0; i < edges.size(); ++i) {
		// cout << mindepth[i] << ' ' << depth[i] << endl;
		if (parent[i] != -1 && mindepth[i] == depth[i]){
			bridges.push_back({parent[i], i});
			// cout << i << endl;
		}
	}
	return bridges;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    edges.resize(n);
    parent = mindepth = depth = was = vector<int>(n, -1);
    for (int i = 0; i < m; ++i) {
    	int u, v;
    	cin >> u >> v;
    	edges[u].push_back(v);
    	edges[v].push_back(u);
    }
    for (int i = 0; i < n; ++i) {
    	if (depth[i] == -1) {
    		depth[i] = 0; 
    		parent[i] = -1; 
    		++timer;
    		// cout << i << endl;
    		dfs(i);
    	}
    }
    // auto res = find_bridges();
    
    auto res = cutpoints();
    // for (int i = 0; i < n; ++i) 
    // 	if (cut[i]) cout << i << endl; 
    // for (auto u : res) {
    // 	cout << u.first << ' ' << u.second << '\n';
    // }
    for (int i = 0; i < n; ++i) 
    	if (res[i]) cout << i << '\n';
}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	double ave = (double)sum / (double)n, def = 100;
	int ans = -1;
	for (int i = 0; i < n; i++)
		if (abs(ave - a[i]) < def)
		{
			ans = i;
			def = abs(ave - a[i]);
		}
	cout << ans << endl;

	return 0;
}


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

int main() {
    int n;
    ll sum=0,x=0,y,ans=1LL<<60;
    cin>>n;
    vector<int> a(n);
    rep(i,n) {
        cin>>a[i];
        sum+=a[i];
    }
    for (int i=0; i<n-1; i++) {
        x+=a[i];
        y=sum-x;
        ans=min(ans,abs(x-y));
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  vector<int> v;
  int a;
  ll sum = 0;	
	REP(i,n){
    cin >> a;
		sum += a;
		v.push_back(a);
	}

  sort(all(v));  

  cout << v[0] << " " << v[n-1] << " " << sum << endl;
  /*
  int i;
	cin >> i;
	*/
   
	//cout << i/j << " " <<  i%j << " ";
	//cout << fixed << setprecision(5) << i/(double)j << endl;
}




Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
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; }

const int MOD = 1000000007;
const int INF = 1001001001;

const int mod = 1000000007;
const int inf = 1e9;
#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int n;
    cin >> n;
    vector<P> a(n);
    for(int i = 0; i < n; i++) {
        int x, l;
        cin >> x >> l;
        P p = make_pair(x+l, x-l);
        a[i] = p;
    }
    sort(a.begin(), a.end());
    int now = -INF;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(now > a[i].second) continue;
        now = a[i].first;
        ans++;
    }
    cout << ans << endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)



int main() {
	ll S, W;
	std::cin >> S >> W;

	if (S <= W) {
		std::cout << "unsafe" << endl;
	}
	else {
		std::cout << "safe" << endl;
	}
	return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
string s;
int k;
int ans,times;
int main() {
	cin>>n>>n;
	for(int i=1;i<=n;i++) {
		cin>>k>>s;
		if(s[0]=='W'&&a[k]!=-1) a[k]++;
		if(s[0]=='W'&&a[k]==-1) continue;
		if(s[0]=='A'&&a[k]!=-1) ans++,times+=a[k],a[k]=-1;
		if(s[0]=='A'&&a[k]==-1) continue; 
	}
	cout<<ans<<" "<<times;
	return 0;
}

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

using namespace std;

#define intt long long
const int MAXN = 100005;

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    cout << (n * (n + 1)) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
S = []
T = []
ans = 0
N = int(input())
for i in range(N) :
    s = input()
    S.append(s)
M = int(input())
for j in range(M) :
    t = input()
    T.append(t)
for k in range(N) :
    if ans < S.count(S[k]) - T.count(S[k]) :
        ans = S.count(S[k]) - T.count(S[k])
print(ans) 


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int x=1,res,m,n,a[200008],i,b[1000]= {0},cnt=0;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
        if(a[i]==x)
        {
            cnt++;
            x++;
        }
        //b[a[i]]++;
    }
    if(cnt!=0)
    cout<<n-cnt<<endl;
    else
        cout<<-1<<endl;

}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;

int main(){
  ll n;cin >> n;
  vector<vector<ll>> dat(n, vector<ll>(2, 0));
  for(int i=0;i<n;i++) {
    scanf("%lld %lld", &dat[i][0], &dat[i][1]);
  }
  vector<ll> x(2*n), X(2*n);
  for(int i=0;i<n;i++) x[i] = dat[i][0], x[i+n] = dat[i][1];
  sort(x.begin(), x.end());
  for(int i=0;i<n;i++) X[i] = (i==0?0:X[i-1]) + x[i];

  bool f = false;
  for(int i=0;i<n;i++){
    ll p = dat[i][0], q = dat[i][1];
    ll idx1 = lower_bound(x.begin(), x.end(), p) - x.begin();
    ll idx2 = lower_bound(x.begin(), x.end(), q) - x.begin();
    if(idx1>=n||idx2>=n) continue;
    if(idx1==n-1&&idx2==n-1) continue;
    f = true;
  }
  ll A = 0, B = 0;
  for(int i=0;i<n;i++) A += dat[i][0], B += dat[i][1];
  if(f){
    ll ans = 0;
    for(int i=0;i<n;i++) ans += x[i];
    std::cout << min({A, B, ans}) << '\n';
    return 0;
  }

  ll ans = 1000000000000000000;
  for(int i=0;i<n;i++){
    ll tmp;
    ll p = dat[i][0], q = dat[i][1];
    ll idx1 = lower_bound(x.begin(), x.end(), p) - x.begin();
    ll idx2 = lower_bound(x.begin(), x.end(), q) - x.begin();
    if(idx1==n-1||idx2==n-1){
      tmp = (n==2?0:X[n-3]) + p + q;
    }else if(idx1<n-1){
      tmp = X[n-2] + q;
    }else if(idx2<n-1){
      tmp =  X[n-2] + p;
    }else{
      tmp = (n==2?0:X[n-3]) + p + q;
    }
    ans = min(ans, tmp);
  }
  std::cout << min({A, B, ans}) << '\n';
  return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, K; cin >> N >> K;
  vector<ll> X(N), Y(N);
  for (ll i = 0; i < N; i++) {
    ll x, y; cin >> x >> y;
    X.at(i) = x;
    Y.at(i) = y;
  }
  vector vx(X);
  vector vy(Y);
  sort(vx.begin(), vx.end());
  sort(vy.begin(), vy.end());
  ll ans = LLONG_MAX;
  for (ll x = 0; x < N; x++) {
    for (ll y = 0; y < N; y++) {
      for (ll xx = 1; xx < N; xx++) {
	for (ll yy = 1; yy < N; yy++) {
	  ll cnt = 0;
	  for (ll i = 0; i < N; i++) {
	    if (vx[x] <= X[i] && X[i] <= vx[xx]
		&& vy[y] <= Y[i] && Y[i] <= vy[yy]) cnt++;
	  }
	  if (cnt >= K) {
	    ans = min(ans, (vx[xx] - vx[x]) * (vy[yy] - vy[y]));
	  }
	}
      }
    }
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	cout << (s == "ABC" ? "ARC" : "ABC") << '\n';
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    vector<int> a(26);
    for(int i = 0; i < s.size(); i++)
        a[(s.at(i)- 'a')]++;
    for(int i = 0; i < 26; i++)
        if(a[i] > 1){
            cout << "no" << endl;
            return 0;
        }
    cout << "yes" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
        int abss(int a){
            int x = a ;
            if(x<0)x*=-1 ;
            return x;
        }
int main()
{
    int n ;cin>>n;int ar[n+1];
    for(int i = 1 ; i<=n ; i++)
        cin>>ar[i];
    int arr[n+1];
    arr[1]=0;
    arr[2]=abss(ar[2]-ar[1]);
    for(int i = 3 ;i <=n ; i++){
        arr[i] = min(arr[i-1]+abss(ar[i-1]-ar[i]) , arr[i-2]+abss(ar[i-2]-ar[i]));
    }
    cout<<arr[n];
   
    return 0;
}

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

#define M 500000
#define P 10
#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;

void insert(int);
void inorder(Node);
void preorder(Node);
int find(int,Node);


int main() {

  int m,k,i,f;
  char s[10];

  scanf("%d",&m);

  for (i=0 ; i<m ; i++){
    scanf("%s",s);

    if(s[0]=='i'){
      scanf("%d",&k);
      insert(k);
    }
    if(s[0]=='f'){
      scanf("%d",&k);
      f=find(k,root);
      if(f==0) printf("no\n");
      else printf("yes\n");
    }

    else if(s[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}

void insert(int k){
  Node x = root;
  Node y = NIL;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }

  z->parent=y;

  if(y==NIL) root=z;
  else if(z->key < y->key) y->left=z;
  else y->right=z;

}

void inorder(Node r){
  if(r->left!=NIL) inorder(r->left);
  printf(" %d",r->key);
  if(r->right!=NIL)inorder(r->right);
}


void preorder(Node r){
    printf(" %d",r->key);
    if(r->left!=NIL) preorder(r->left);
    if(r->right!=NIL)preorder(r->right);
}


int find(int k,Node r){

  int a=0;
  Node x=r;

  while(x!=NIL){
    if(k < x->key) x = x->left;
    else if (k > x->key) x = x->right;
    else {
      a=1;
      break;
    }
  }

  return a;
}

Measured memory_bytes: 19364
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        tmp = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

ans = 0
for i in range(1,N+1):
    ans = max(ans,distance(i))
print(ans)


Measured memory_bytes: 62036
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int a,b; cin>>a>>b;
  if(a<10 && b<10)  cout<< a*b  <<endl;
  else  cout<< -1  <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;


const long long int mod = 1000000007, INF = 100000000000000;

//階乗先に計算
long long int kaizyou[200005] = { 1 };
long long int kai(long long int a, long long int b, long long int mod) {
	long long int tmp = 1;
	for (long long int i = a; i <= b; i++) {
		tmp *= i;
		tmp %= mod;

		kaizyou[i] = tmp;
	}
	return tmp;
}


//累乗(繰り返し2乗法)　aのb乗(mod)を求める。
long long int rui(long long int a, long long int b, long long mod) {
	int memo[65] = {};
	long long int A[65] = {};
	long long int tmp = 1;
	for (int i = 0; i < 65; i++) {
		memo[i] = b % 2;
		b /= 2;
	}

	A[0] = a;
	A[0] %= mod;

	for (int i = 1; i < 65; i++) {
		A[i] = A[i - 1] * A[i - 1];
		A[i] %= mod;
	}
	for (int i = 0; i < 65; i++) {
		if (memo[i] == 1) {
			tmp *= A[i];
			tmp %= mod;
		}
	}
	tmp %= mod;
	return tmp;
}

//コンビネーション計算
long long int comb(long long int n, long long int r, long long int mod) {
	long long int tmp;

	tmp = (kaizyou[n] * rui(kaizyou[r], mod - 2, mod)) % mod;
	tmp *= rui(kaizyou[n - r], mod - 2, mod);
	tmp %= mod;
	if (tmp < 0) { tmp = (mod - tmp) % mod; }
	return tmp;
}



long long int n,c, p,q,r, res = 0, num[200050] = {}, sum[200003] = {}, dp[35][120000] = {};
int main() {
	cout << fixed << setprecision(10);
	kai(1, 200000, mod);
	cin >>n>>c;
	for (int i = 0; i < n; i++) {
		cin >> p >> q >> r;
		num[p] ++;
		num[q + 1] --;
		dp[r][p]++;
		dp[r][q]++;
	}
	res = num[0];
	for (int i = 1; i <=200000; i++) {
		num[i] += num[i - 1];
	}
	for (int i = 1; i <= c; i++) {
		for (int j = 0; j <= 110000; j++) {
			num[j] -= dp[i][j] / 2;
		}
	}
	for (int i = 1; i <= 110000; i++) {
		res = max(res, num[i]);
	}
	cout << res;
}


Measured memory_bytes: 33152
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
   
using namespace std;
   
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
   
static const double EPS = 1e-8;
   
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class Book {
private:
  string title;
  string author;
  string date;

  int date2sec(string date){
    vector<string> elements;
    string tmp = "";
    for(int i = 0; i < date.size(); i++){
      if(date[i] == '/'){
        elements.push_back(tmp);
        tmp = "";
        continue;
      }
      tmp += date[i];
    }
    elements.push_back(tmp);
    
    return 365 * (atoi(elements[0].c_str()) - 1970)
      + atoi(elements[1].c_str()) * 31
      + atoi(elements[2].c_str());
  }

public:
  Book(string title, string author, string date) {
    this->title = title;
    this->author = author;
    this->date = date;
  }

  bool match_title(string query){
    if(query == "*") return true;
    for(int i = 0; i + query.size() <= title.size(); i++){
      if(title.substr(i,query.size()) == query) return true;
    }
    return false;
  }

  bool match_author(string query){
    if(query == "*") return true;
    for(int i = 0; i + query.size() <= author.size(); i++){
      if(author.substr(i,query.size()) == query) return true;
    }
    return false;
  }

  bool match_date(string from,string to) {
    int my_sec = date2sec(date);
    if(from != "*" && my_sec < date2sec(from)) return false;
    if(to != "*" && my_sec > date2sec(to)) return false;
    return true;
  }

  string get_title() const {
    return title;
  }
};

int main(){
  int num_of_books;
  int num_of_queries;
  while(~scanf("%d",&num_of_books)){
    vector<Book> books;
    for(int book_i = 0; book_i < num_of_books; book_i++){
      string title,author,date;
      cin >> title >> author >> date;
      books.push_back(Book(title,author,date));
    }
    scanf("%d",&num_of_queries);
    for(int query_i = 0; query_i < num_of_queries; query_i++){
      string title,author,from,to;
      cin >> title >> author >> from >> to;
      for(int book_i = 0; book_i < num_of_books; book_i++){
        if(books[book_i].match_title(title)
           && books[book_i].match_author(author)
           && books[book_i].match_date(from,to)){
          cout << books[book_i].get_title() << endl;
        }
      }
      if(query_i != num_of_queries -1){
        cout << endl;
      }
    }
  }
}

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

#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);

int main() {
    fast_io;
    string s;
    int k;
    cin>>k>>s;

    if(s.size()<=k) {
        cout<<s<<endl;
    }
    else {
        cout<<s.substr(0,k)<<"..."<<endl;
    }
}




Measured memory_bytes: 3656
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>



using namespace std;

int main()
{
    int a, b, h, m;
    double ans, pi, zi, fun, kaku;
    pi = 3.141592653589793;
    cin >> a;
    cin >> b;
    cin >> h;
    cin >> m;
    zi = 30*h+0.5*m;
    fun = 6*m;
    kaku = abs(zi-fun);
    if(kaku > 180)kaku = 360-kaku;
    kaku /= 180;
    ans = sqrt(pow(a,2)+pow(b,2)-2*a*b*cos(pi*kaku));
    cout << setprecision(10)<< ans << endl;    
    return 0;
}


Measured memory_bytes: 4084
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1 << 30;

int c,d;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
LL lcm(int x,int y){return 1ll*x*y/gcd(x,y);}

LL sv(LL x){
	return x-(x/c+x/d-x/(lcm(c,d)));
}

int main(){
	char s[4];
	scanf("%s",s);
	if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3])puts("Bad");
	else puts("Good");
	return 0;
	
	LL a,b;
	scanf("%lld%lld%d%d",&a,&b,&c,&d);
	printf("%lld\n",sv(b)-sv(a-1));

	return 0;
}


Measured memory_bytes: 256
import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)


Measured memory_bytes: 69848
from itertools import product

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

x = set([])
for bit in product([0, 1], repeat=n):
    cnt = 0
    for i, v in enumerate(bit):
        if v == 1:
            cnt += a[i]
    x.add(cnt)

for i in m:
    if i in x:
        print("yes")
    else:
        print("no")


Measured memory_bytes: 5716
s = int(input())

def ABC_B(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3*n + 1

S = [s]
m = 2
i = ABC_B(s)
while(i not in S):
    m = m + 1
    S.append(i)
    i = ABC_B(i)
    
print(m)

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

int main(){
    int n;
    cin>>n;
    int c = 1;
    int res = 0;
    for(int i = 0; i < n; i++){
        int x;cin>>x;
        if(x!=c) res++;
        else c++;
    }
    if(res==n) cout<<-1;
    else cout<<res;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

ll n, m;


int main () 
{
	int a, b, c;

	cin >> a >> b >> c;

	if (a == b && b == c) cout << "Yes";
	else cout << "No";
}

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


#define ll long long int
#define vll vector<ll>tm#define vllv vector<vector<ll>> 
#define sz size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 

void solve()
{
	ll n;
	cin>>n;
	ll a[n];
	for(ll i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	if(a[0]==0)
	{
		cout<<0;
		return;
	}
	ll ans=1;
	
	ll tm = 1e18;
	
	for(ll i=0;i<n;i++)
	{
		if((tm/ans) >= a[i]) 
		{
			ans*=a[i];
		}
		else
		{
			cout<<-1;
			return;
		}
	}
	cout<< ans << endl;
}
	

int main()
{
	fast;
    ll q;
    q=1;
    // cin>>q;
    while(q--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4432
A,B,C,D,E,F = map(int,input().split())
ans = [0,0]
maxconc = -1
for i in range(31):
    for j in range(31):
        water = A*i + B*j
        if 100 * water > F:continue
        loopk = E*water // C + 1
        
        for k in range(loopk):
            loopl = (E*water-C*k)// D + 1
            for l in range(loopl):
                sugar = C*k + D*l
                if 100*water + sugar > F or 100*water + sugar == 0:continue
                if sugar <= water * E:
                    conc = (sugar)/(sugar+100*water)
                    if conc > maxconc:
                        ans = [100*water+sugar,sugar]
                        maxconc = conc
                    
print(*ans)
                        
                        
                        
                    

Measured memory_bytes: 3064
n = int(input())
P = [int(x) for x in input().split()]
mins = [P[0]]
for i in range(1,n):
    mins.append(min(mins[-1], P[i]))

cnt = 0
for i in range(n):
    if P[i] <= mins[i]:
        cnt +=1
print(cnt)

Measured memory_bytes: 25768
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;

using namespace std;

bool match[200000] = {};
ll a[200000] = {};
ll b[200000] = {};
priority_queue<pair<ll, ll>> q;
int n;

ll dfs(int i)
{
  ll left = b[(i - 1 + n) % n];
  ll right = b[(i + 1 + n) % n];
  if (left + right == 0)
  {
    return 0;
  }
  ll ans = (abs(b[i] - a[i]) / (left + right));
  if (ans == 0)
  {
    return 0;
  }
  b[i] = b[i] - (abs(b[i] - a[i]) / (left + right)) * (left + right);
  if (b[i] == 0)
  {
    return 0;
  }
  if (a[i] == b[i])
    match[i] = true;

  if (b[(i - 2 + n) % n] + b[i] < b[(i - 1 + n) % n] && !match[(i - 1 + n) % n])
  {
    if (b[(i - 2 + n) % n] + b[i] != 0)
    {
      q.push(make_pair(b[(i - 1 + n) % n] % (b[(i - 2 + n) % n] + b[i]), (i - 1 + n) % n));
    }
  }
  if (b[i] + b[(i + 2 + n) % n] < b[(i + 1 + n) % n] && !match[(i + 1 + n) % n])
  {
    if (b[i] + b[(i + 2 + n) % n] != 0)
    {
      q.push(make_pair(b[(i + 1 + n) % n] % (b[i] + b[(i + 2 + n) % n]), (i + 1 + n) % n));
    }
  }
  return ans;
}

int main()
{
  cin >> n;
  REP(i, n)
  {
    cin >> a[i];
  }
  REP(i, n)
  {
    cin >> b[i];
    if (a[i] == b[i])
    {
      match[i] = true;
    }
  }

  ll ans = 0;

  REP(i, n)
  {
    ll left = b[(i - 1 + n) % n];
    ll right = b[(i + 1 + n) % n];
    if (left + right < b[i] && !match[i])
    {
      q.push(make_pair(b[i] % (left + right), i));
    }
  }

  while (!q.empty())
  {
    auto top = q.top();
    q.pop();
    ans += dfs(top.second);
  }

  REP(i, n)
  {
    if (!match[i])
    {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 5748
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

class Bit {
private:
    vector<int> bit;
    int n;

public:
    Bit(int _n) {
        n = _n;
        bit.clear();
        bit.resize(n + 1, 0);
    }

    // get sum in [1, i]
    // sum{[i, j]} = sum{[1, j]} - sum{[1, i-1]}
    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    // add x to bit[i]
    void add(int i, int x) {
        while (i <= n) {
            bit[i] += x;
            i += i & -i;
        }
    }
};

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

    int n, q;
    cin >> n >> q;
    Bit bit(n);
    rep(i, q) {
        int a, x, y;
        cin >> a >> x >> y;
        if (a == 0) {
            bit.add(x, y);
        }
        else {
            cout << bit.sum(x, y) << endl;
        }
    }

}

Measured memory_bytes: 3544
def main():
    N, C = map(int, input().split())
    D = []
    for i in range(C):
        D.append(list(map(int, input().split())))
        
    c_init = []
    for i in range(N):
        c_init.append(list(map(int,input().split())))
    
    group0 = [0]*C
    group1 = [0]*C
    group2 = [0]*C
    
    
    #1. 各グループに何色がどれだけあるかチェック
    for i in range(N):
        for j in range(N):
            if (i+j+2)%3==0:
                group0[c_init[i][j] - 1] += 1
            elif (i+j+2)%3 == 1:
                group1[c_init[i][j] - 1] += 1
            else:
                group2[c_init[i][j] - 1] += 1
    
    #2. 違和感の大きさをチェック
    iwakan =[]
    for color0 in range(C):
        for color1 in range(C):
            if color1 == color0:
                continue
            
            for color2 in range(C):
                if color2==color0 or color2==color1:
                    continue
                
                iwakan_temp = 0
                for colorN in range(C):
                    iwakan_temp += group0[colorN]*D[colorN][color0]
                    iwakan_temp += group1[colorN]*D[colorN][color1]
                    iwakan_temp += group2[colorN]*D[colorN][color2]
                
                iwakan.append(iwakan_temp)
                
    print(min(iwakan))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 6552
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
	ll n;
	cin >> n;
	vector<vector<pair<ll,int>>> M(n);
	for(ll i = 0;i<n-1;i++)
	{
		ll a,b,c;
		cin >> a >> b >> c;
		a--;b--;
		M[a].emplace_back(b,c);
		M[b].emplace_back(a,c);
	}
	ll q,k;
	cin >> q >> k;
	vector<ll> d(n,-1);
	k--;
	d[k] = 0;
	queue<ll> Q;
	Q.push(k);
	while(!Q.empty())
	{
		ll now = Q.front();
		Q.pop();
		for(auto i:M[now])
		{
			if(d[i.first]==-1)
			{
				d[i.first] = d[now]+i.second;
				Q.push(i.first);
			}
		}
	}
	while(q--)
	{
		ll x,y;
		cin >> x >> y;
		x--,y--;
		cout<<d[x]+d[y]<<endl;
	}

	return 0;
}


Measured memory_bytes: 9984
a, b, c = map(int, input().split())
k = int(input())
for new_k in range(k + 1):
    for t in range(3 ** new_k):
        na = a
        nb = b
        nc = c
        nt = t
        for x in range(new_k):
            if nt % 3 == 0:
                na *= 2
            elif nt % 3 == 1:
                nb *= 2
            else:
                nc *= 2

            if na < nb < nc:
                print("Yes")
                quit(0)
            nt //= 3
print("No")


Measured memory_bytes: 67588
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define D(n, retu)                                                             \
  REP(i, n) { cin >> retu[i]; }
#define mod 1000000007
#define INF 93193111451418101
#define MIN -933111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
#define yo 100001
//------------------変数-----------------------//
ll n, maxmove = 0, movesize;
string str;
map<ll, vector<ll>> m;
ll xo = 0, dp[200001], xorhairetu[200001];
//-------------------関数----------------------//
int main() {
  ll n;
  cin >> n;
  ll cnt = 0, mae = INF, muki = 0;
  bool fir = true;
  REP(i, n) {
    ll hoge;
    cin >> hoge;
    if (fir) {
      fir = false;
      cnt++;
    } else if (hoge != mae) {
      if (hoge > mae) {
        if (muki == 2) {
          cnt++;
          // cout << i << endl;
          muki = 0;
        } else {
          muki = 1;
        }
      } else if (muki == 1) {
        cnt++;
        // cout << i << endl;
        muki = 0;
      } else {
        muki = 2;
      }
    }
    mae = hoge;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main()
{
  cin.tie(0);
  int a, b, t;
  cin >> a >> b >> t;
  cout << (t / a) * b << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	map<int, int> F;
	cin >> n;
	vector<array<ll, 2>> a(n);
	for(auto &i : a) cin >> i[0] >> i[1], F[(i[0]+i[1])&1]++;
	if(F.size() > 1) return cout << "-1\n", 0;
	vector<int> w;
	for(int i = 0; i < 31; i++) w.push_back(1<<i);
	if(F[0]) w.push_back(1);
	cout << w.size() << '\n';
	for(auto &i : w) cout << i << " "; cout << endl;
	for(auto [x, y] : a) {
		string ans = "";
		if((x+y+1)&1) x--, ans = "R";
		for(ll z = 1ll<<31; z>>=1;) {
			if(abs(x-z)+abs(y)<z) ans += "R", x -= z;
			else if(abs(x+z)+abs(y)<z) ans += "L", x += z;
			else if(abs(y+z)+abs(x)<z) ans += "D", y += z;
			else if(abs(y-z)+abs(x)<z) ans += "U", y -= z;
		}
		reverse(all(ans));
		cout << ans << '\n';
	}
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using Graph = vector<vector<int>>;
const int INF = 1000000007;
long long moda(long long val, long long m) {
  long long res = val % m;
  if (res < 0) res += m;
  return res;
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main(){
  ll n;
  cin >> n;
  ll ansa = 0,ansb = 0;
  vector<ll>v(n);
  rep(i,n)cin >> v[i];
  rep(i,n){
    ansa += v[i];
    ansa %= INF;
  }
  ansa = ansa * ansa;
  ansa %= INF;
  rep(i,n){
    ansb += v[i] * v[i];
    ansb %= INF;
  }
  ll ans = moda((ansa % INF - ansb % INF),INF);
  ans %= INF;
  ans = ans * modinv(2,INF) % INF;
  cout << ans << endl;

  return 0;
}


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

int main() {
  int n; cin >>n;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  map<int,int>mp;
  for(int x:a){
    if(mp.count(x)){
      mp.at(x)++;
    }else{
      mp[x]=1;
    }
  }
  int m;
  cin>>m;
  vector<int>b(m);
  for(int i=0;i<m;i++)cin>>b[i];
  for(int i=0;i<m;i++){
    if(mp.count(b[i])){
      mp.at(b[i])--;
      if(mp.at(b[i])<0){
        cout<<"NO"<<endl;
        return 0;
      }
    }else{
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
  return 0;
}


Measured memory_bytes: 11264
#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
int a[214514];
signed main(){
	int n;
	cin>>n;
	int memo=1;
	rep(0,i,n)cin>>a[i];
	rep(0,i,n)if(a[i]==memo)memo++;
	if(memo==1)c(-1)
	else c(n-memo+1)
}
	

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define maxn 205
#define ll long long
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
int mod;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef __int128_t i128;
typedef __uint128_t u128;

struct Mod32 {
	Mod32():n_(0) {}
	Mod32(u32 n):n_(init(n)) {}
	static u32 init(u32 w) { return reduce(u64(w) * r2); }
	static void set_mod(u32 m) {
		mod=m; assert(mod&1);
		inv=m; rep(i,0,4) inv*=2-inv*m;
		r2=-u64(m)%m;
	}
	static u32 reduce(u64 x) {
		u32 y=u32(x>>32)-u32((u64(u32(x)*inv)*mod)>>32);
		return i32(y)<0?y+mod:y;
	}
	Mod32& operator += (Mod32 rhs) { n_+=rhs.n_-mod; if (i32(n_)<0) n_+=mod; return *this; }
	Mod32 operator + (Mod32 rhs) const { return Mod32(*this)+=rhs; }
	Mod32& operator -= (Mod32 rhs) { n_-=rhs.n_; if (i32(n_)<0) n_+=mod; return *this; }
	Mod32 operator - (Mod32 rhs) const { return Mod32(*this)-=rhs; }
	Mod32& operator *= (Mod32 rhs) { n_=reduce(u64(n_)*rhs.n_); return *this; }
	Mod32 operator * (Mod32 rhs) const { return Mod32(*this)*=rhs; }
	u32 get() const { return reduce(n_); }
	static u32 mod,inv,r2;
	u32 n_;
};
u32 Mod32::mod,Mod32::inv,Mod32::r2;
Mod32 one,zero;
int n, m, c;
Mod32 nr[maxn][maxn], u[maxn][maxn];
Mod32 dp[maxn][maxn];
Mod32 pw[maxn][maxn];
Mod32 jc[maxn], bjc[maxn];
void calnx(int a, int b, int tp) {
	// a : 余下 b : 这些 
	for (int s = 0; s <= n + m; s++) {
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				u[i][j] = 0;
				if (i + j == s) u[i][j] = dp[i][j];
			}
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				if (i) 
					u[i][j] += u[i - 1][j] * pw[a][m - j] * pw[b][j];
				if (j)
					u[i][j] += u[i][j - 1] * pw[a][n - i] * pw[b][i];
			}
		for (int i = 0; i <= n; i++)
			for (int j = max(0, s - i); j <= m; j++) {
				Mod32 kk = u[i][j] * bjc[i + j - s];
				if (tp && (i + j - s) % 2 == 1) nr[i][j] -= kk;
				else nr[i][j] += kk;
				u[i][j] = 0;
			}
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			dp[i][j] = nr[i][j], 
			nr[i][j] = 0;
}
Mod32 ksm(Mod32 a, ll b) {
	if (!b) return one;
	Mod32 ns = ksm(a, b >> 1);
	ns = ns * ns;
	if (b & 1) ns *= a;
	return ns;
}
int main()
{
	cin >> n >> m >> c >> mod;
	Mod32::set_mod(mod); one=Mod32(1); zero=Mod32(0);
	jc[0] = bjc[0] = one;
	for (int i = 1; i < maxn; i++)
		jc[i] = jc[i - 1] * i, 
		bjc[i] = ksm(jc[i], mod - 2);
	for (int i = 0; i < maxn; i++) {
		pw[i][0] = 1;
		for (int j = 1; j < maxn; j++)
			pw[i][j] = pw[i][j - 1] * i;
	}
	for (int i = 0; i <= 2 * c + 1; i++) {
		int nr = (i + 1) / 2;
		if (i == 0) dp[0][0] = 1;
		else {
			if (i % 2 == 1) calnx(nr, c + 1 - nr, 0);
			else calnx(nr, c - nr, 1);
		}
	}
	dp[n][m] = dp[n][m] * jc[n] * jc[m];
	cout << dp[n][m].get() << endl; 
	return 0;
}
/*
100 100 100 998244353
*/

Measured memory_bytes: 896
#include<stdio.h>
int max(int a,int b){
  if(a>b) return a;
  return b;
}
int min(int a,int b){
  if(a>b) return b;
  return a;
}
int main(void){
  int n,k,s,t,i;
  scanf("%d %d",&n,&k);
  s = max(-1000000,k-n+1);
  t = min(1000000,k+n-1);
  for(i=s;i<=t;i++) printf("%d ",i);
  printf("\n");
  return 0;
}

Measured memory_bytes: 128