akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <iomanip>

int main(void) {
	// in
	int n;
	std::cin >> n;
	std::vector<long long> a(n), b(n);
	for(int i = 0; i < n; ++i) std::cin >> a[i] >> b[i];
	
	// pair
	std::vector<std::pair<long long, long long>> tasks(n);
	for(int i = 0; i < n; ++i) tasks[i] = std::make_pair(a[i], b[i]);

	// sort
	std::sort(tasks.begin(), tasks.end(), [](std::pair<long long, long long> &lhs, std::pair<long long, long long> &rhs) { return lhs.second > rhs.second; });
	
	long long t_limit = tasks[0].second;
	int n_task_left = n;
	for(int i = 0; i < n; ++i) {
		if(t_limit < 0) break;
		if(tasks[i].second < t_limit) t_limit = tasks[i].second - tasks[i].first;
		else t_limit = t_limit - tasks[i].first;
		--n_task_left;
	}
	
	bool is_possible = (n_task_left == 0 && t_limit >= 0 ? true : false);

	std::cout << (is_possible ? "Yes" : "No") << std::endl;

	return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL)
    x = x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL)
    x = x->right;
  return x;
}

Node treeSearch(Node u, int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    x = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
  if(y->left != NIL) x = y->left;
  else x = y->right;
  if(x != NIL) x->parent = y->parent;
  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
  if(y != z) z->key = y->key;
  }

void insert(int k){
  Node y = NIL;
  Node x = root;
  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 u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node u){ 
  if(u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  return 0;
}

Measured memory_bytes: 19364
def solve(H, W, Ss):
    d = [[-1 for __ in range(W)] for _ in range(H)]

    index = 0
    for (sh, sw) in [(h, w) for h in range(0, H) for w in range(0, W)]:
        if d[sh][sw] == -1:
            que = [(sh, sw)]
            index += 1
            d[sh][sw] = index

            while len(que):
                h, w = que.pop()
                for (hi, wi) in [(h + 1, w), (h - 1, w), (h, w - 1), (h, w + 1)]:
                    if 0 <= hi < H and 0 <= wi < W:
                        if Ss[hi][wi] != Ss[h][w] and d[hi][wi] == -1:
                            que.append((hi, wi))
                            d[hi][wi] = index
    c = [[0, 0] for _ in range(index + 1)]
    for h in range(0, H):
        for w in range(0, W):
            if Ss[h][w] == ".":
                c[d[h][w]][0] += 1
            elif Ss[h][w] == "#":
                c[d[h][w]][1] += 1
    ans = sum([b * w for (w, b) in c])
    return ans

if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    Ss = list([input() for l in range(H)])
    print(solve(H, W, Ss))


Measured memory_bytes: 25336
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N; cin >> N;
	vector<ll> a(N, 0LL);
	rep (i, N) cin >> a[i];

	ll res = 0LL;
	rep (i, N){
		res += (a[i] - 1LL);
	} // end rep

	cout << res << endl;

	return 0;
}

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

int main() {
				    // *constraint*
  int N,K;    	    // 1<=N<=100 N is the number of balls 
  					// 1<=K<=100 K is the x-coordinate of robot 
  					// 0 < xi < K
  				    // Enter an Integer
  
  int distance = 0;
  cin  >> N >> K;
  int x;
  int i = 1;
  while (i <= N) {
    cin >> x;
    if( x < K - x){
      distance += x * 2;
    }else{
      distance += (K-x) * 2;
    }
    i++;
  }
  cout << distance << endl;
}


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

prime = [2]
for i in range(3,1001):
    flag = 0
    for j in prime:
        if i % j == 0:
            flag = 1
    if flag == 0:
        prime.append(i)

prime_count = [0 for i in range(1001)]

for i in range(1, N+1):
    for j in prime:
        while i % j == 0:
            prime_count[j] += 1
            i = int(i/j)
ans = 1
for i in range(1001):
    ans *= (prime_count[i]+1)
    ans %= 1000000007
print(ans)


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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int tc; cin>>tc; while(tc--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();


    int n, s1= 0, s2=0;
    cin>> n;
    int a[n];

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


    for(int i=n-1, j=0; i>=j; )
    {
        if( s1< s2)
        {
            s1+= a[i];
            i--;
        }
        else
        {
            s2+= a[j];
            j++;
        }

    }



    cout << abs( s2-s1);

    return 0;
}




Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;

int main(){
    int n;cin>>n;int p[n],minp=n+1,cnt=0;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<n;i++){
        if(minp>=p[i]){
            minp=p[i];
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
 
int main() {
  int n;
  cin >> n;
  ll ans = 0;
  ll m = n-1;
  for (ll a = 1; a <= m; a++)
  {
    ll b = m / a;
    ans += b;
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ff first
#define ss second
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vs vector<string>
#define vss vector<vs>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, n) for (ll i = (a); i < (n); ++i)
#define repr(i, a, n) for (ll i = (n); i >= (a); --i)
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);
const int pi = 3.1415926536;
const int MOD = 1000000007;
const int MAX = 510000;

void Main() {
  string s, ans;
  rep(i, 0, 3) {
    cin >> s;
    ans.push_back(s[i]);
  }
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // CとC++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  Main();
}

Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef long long ull;
typedef pair<ll, ll> ii;

#define all(v)		((v).begin()), ((v).end())
#define sz(v)		((int)((v).size()))
#define endl		"\n"
#define fx(n)		fixed<<setprecision(n)
#define mk			make_pair	

void File()
{
#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
	/*freopen("output.txt", "w", stdout);
	freopen("commandos.in", "r", stdin);*/
#endif
}
void fast()
{
	ios::sync_with_stdio(NULL);
	cout.tie(NULL);
	cin.tie(NULL);
	//File();
}
const double pi = acos(-1.0);
const ll oo = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int nn = 2e5 + 15;
int dx[8] = { 1, 0, -1, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, -1, 1 };

int main()
{
	fast();
	ll x;
	cin >> x;
	x %= 10;
	if (x == 2 || x == 4 || x == 5 || x == 7 || x == 9)
		cout << "hon" << endl;
	else if (x == 3)
		cout << "bon" << endl;
	else
		cout << "pon" << endl;
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int)
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }

int main(){
    int n;cin >> n;
    long long int currMax = 0ll;
    for(int i = 0;i < n;i++){
        long long int t;cin >> t;
        if(t > currMax)currMax = t;
        else if(t < currMax - 1ll)return cout << "No", 0;
    }
    cout << "Yes";
}

Measured memory_bytes: 256
#include <cstdio>

int main() {
  int n;
  scanf("%d", &n);
  switch (n % 10) {
    case 0: printf("pon\n");break;
    case 1: printf("pon\n");break;
    case 2: printf("hon\n");break;
    case 3: printf("bon\n");break;
    case 4: printf("hon\n");break;
    case 5: printf("hon\n");break;
    case 6: printf("pon\n");break;
    case 7: printf("hon\n");break;
    case 8: printf("pon\n");break;
    case 9: printf("hon\n");break;
  }
  return 0;
}

Measured memory_bytes: 3180
using System;

namespace B___Comparison
{
    class Program
    {
        static void Main (string[] args)
        {
            var a = Console.ReadLine ();
            var b = Console.ReadLine ();
            if (a.Length != b.Length)
            {
                if (a.Length > b.Length)
                {
                    Console.WriteLine ("GREATER");
                }
                else
                {
                    Console.WriteLine ("LESS");
                }
            }
            else
            {
                for (var i = 0; i < a.Length; i++)
                {
                    if (a[i] > b[i])
                    {
                        Console.WriteLine ("GREATER");
                        return;
                    }
                    else if (a[i] < b[i])
                    {
                        Console.WriteLine ("LESS");
                        return;
                    }
                }
                Console.WriteLine ("EQUAL");
            }
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

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);
    }
}
#pragma endregion

const int MAX_N = 1e5 + 5;
int main()
{
    int n, m;
    cin >> n >> m;
    vint h(n);
    rep(i, n) cin >> h[i];
    vvint g(n, vint());
    bitset<MAX_N> good(n);
    rep(i, n) good[i] = true;
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if (h[a] > h[b])
        {
            good[b] = false;
        }
        else if (h[a] == h[b])
        {
            good[a] = false;
            good[b] = false;
        }
        else
        {
            good[a] = false;
        }
    }
    int ans = 0;
    rep(i, n)
    {
        if (good[i])
        {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5908
#include<stdio.h>

int main(void){
int a,b,c=0;
   scanf("%d %d %d",&a,&b,&c);
  while(a!=-1 || b!=-1 || c!=-1){
   if(a==-1||b==-1)
     printf("F\n");
   else if(a+b>=80)
     printf("A\n");
   else if(a+b>=65&&a+b<80) 
     printf("B\n");
   else if(a+b>=50&&a+b<65)
     printf("C\n");
   else if(a+b>=30&&a+b<50){
     if(c>=50)
       printf("C\n");
     else
       printf("D\n");
   }
   else
     printf("F\n");
     scanf("%d %d %d",&a,&b,&c);
 }
  return 0;
}    


Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  if(S.at(5)=='0'){
  if(S.at(6)=='1')
    cout<<"Heisei"<<endl;
  else if(S.at(6)=='2')
    cout<<"Heisei"<<endl;
  else if(S.at(6)=='3')
    cout<<"Heisei"<<endl;
  else if(S.at(6)=='4')
    cout<<"Heisei"<<endl;
  else
    cout<<"TBD"<<endl;
    }
  else
    cout<<"TBD"<<endl;
  }

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int input;
  while(scanf("%d",&input) != EOF){
    int count = 0;
    for(int a = 0;a < 10;a++){
      if(a > input)break;
      for(int b = 0;b < 10;b++){
        if(a + b > input)break;
        for(int c = 0;c < 10;c++){
          if(a + b + c > input)break;
          for(int d = 0;d < 10;d++){
            if(a + b + c + d > input)break;
            else if(a + b + c + d == input)count++;
          }
        }
      }
    }
    printf("%d\n",count);
  }

  return 0;
}

Measured memory_bytes: 1028
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>


typedef long long ll;

using namespace std;

int main() 
{ 
    ll n, k;
	cin >> n >> k;

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

	sort(h, h + n);

	ll res = 0;

	for (int i = n - k - 1; i >= 0; i--) res += h[i];

	cout << res << endl;

	return 0; 
} 


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

int main()
{
	ll A, B;
	cin >> A >> B;

	ll x = A * B;
	if (A < B)
	{
		ll tmp = A;
		A = B;
		B = tmp;
	}

	ll r = A % B;
	while (r != 0)
	{
		A = B;
		B = r;
		r = A % B;
	}
	cout << x / B << endl;
	return 0;
}

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

int main()
{
  int64_t N;
  cin >> N;
  map<string, int> mp;
  string s;
  for (int i = 0; i < N; i++)
  {
    cin >> s;
    if (mp.count(s))
    {
      mp.at(s)++;
    }
    else
    {
      mp[s] = 1;
    }
  }
  cout << mp.size() << endl;
}


Measured memory_bytes: 19204
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    int N;
    cin >> N;

    vector<ll> A(N+1);
    A[0] = 0;
    FOR(i, 1, N+1){
        cin >> A.at(i);
    }

    int next = A[1];
    FOR(i, 0, N){
        if(next==2){
            p(i+1);
            return 0;
        }else{
            next = A[next];
        }
    }

    p(-1);
    
    return 0;
}

Measured memory_bytes: 1024
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
k = 0
ss = sorted(a)
qq = ss[::-1]

if len(set(a)) == 1 or qq == a:
  print(1000)
  exit()
elif ss == a:
  k = 1000//a[0]
  print(k*a[-1]+1000-a[0]*k)
  exit()

m = 1000
if a[0] < a[1]:
  pp = 1000//a[0]
  m -= pp*a[0]
  k += pp

for i in range(n-2):
  if a[i] <= a[i+1] and a[i+1] > a[i+2]:
    m += k*a[i+1]
    k = 0
  if a[i] >= a[i+1] and a[i+1] < a[i+2]:
    pp = m//a[i+1]
    m -= pp*a[i+1]
    k += pp

m += k*a[-1]
print(m)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int a, b, h;
  cin >> a >> b >> h;
  cout << (a + b) * h / 2 << endl;
}

Measured memory_bytes: 256
// [Tag]
// #

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <deque>
#include <map>
using namespace std;

#define fi     	first    
#define se     	second  

/** Type Define **/
typedef long long int           ll;
typedef pair<ll, ll>            p_ll;
typedef vector<string>          vs;
typedef vector<bool>            vb;
typedef vector<int>             vi;
typedef vector<long long>		vl;
typedef vector<vi>              vvi;
typedef vector<vl>				vvl;
typedef vector<char>            vch;
typedef unsigned char           uchar;
typedef unsigned int            ui;
typedef unsigned long long int  ull;

constexpr int               inf = 2123456789;
constexpr long long 		INF = 9123456789123456789;
constexpr long long         MOD = 1000000007LL;

template<class T>
using MaxHeap = priority_queue<T>;
template<class T>
using MinHeap = priority_queue<T, vector<T>, greater<T> >;


template<class T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i];
        if (i + 1 < vec.size())os << ' ';
    }
    return os;
}
template<class T>
istream& operator >> (istream& is, vector<T>& vec) {
    for (int i = 0; i < vec.size(); i++)is >> vec[i];
    return is;
}


/*************************************************/
int N;
vi P;

void sol() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    /*INPUT*/
    cin >> N;
    P.resize(N);
    int ans(0), mn = inf;
    for (int i = 0; i < N; i++) {
        cin >> P[i];
        mn = min(mn, P[i]);
        if (P[i] <= mn)
            ans++;
    }
    cout << ans << endl;
    /*Get_Answer*/
    //sol();
    return 0;
}



//string A, B;
//void sol() {
//
//}
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(); cout.tie();
//    /*INPUT*/
//    int a, b;
//    cin >> a >> b;
//    for (int i = 0; i < a; i++)
//        A += (b + '0');
//    for (int i = 0; i < b; i++)
//        B += (a + '0');
//    cout << min(A, B) << '\n';
//    /*Get_Answer*/
//    //sol();
//    return 0;
//}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    char a[1005];
    scanf("%s",a);
    int l=0,r=strlen(a)-1;
    int ans=0;
    while(l<r)
    {
        if(a[l]!=a[r])
            ans++;
        l++;
        r--;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long
 
int main(){
    priority_queue<ll> A;
    int n, m;
    cin >> n >> m;
    ll a;
    for(int i = 0; i < n; i++){
        cin >> a;
        A.push(a);
    }

    ll tmp = 0;
    for(int i = 0; i < m; i++){
        tmp = A.top();
        A.pop();
        A.push(tmp / 2);
    }

    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += A.top();
        A.pop();
    }

    cout << sum << endl;
}

Measured memory_bytes: 1400
# -*- coding: utf-8 -*-
"""
Created on Wed May  6 16:35:32 2020

@author: shinba
"""

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

A.append(A[0]+K)
B = []
for i in range(N):
    B.append(A[i+1]-A[i])

print(K-max(B))



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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

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


Measured memory_bytes: 256
from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n = int(input())
v = il()
a = dict()
b = dict()
for i in range(n):
    if i&1:
        if v[i] in a:
            a[v[i]] += 1
        else:
            a[v[i]] = 1
    else:
        if v[i] in b:
            b[v[i]] += 1
        else:
            b[v[i]] = 1
a = sorted(a.items(), key=lambda x:x[1])
b = sorted(b.items(), key=lambda x:x[1])

h = a[-1][0]
ans = n//2 - a[-1][1]
if b[-1][0] == h:
    if len(b) == 1:
        ans += n//2
    else:
        ans += n//2 - b[-2][1]
else:
    ans += n//2 - b[-1][1]

hoge = ans 

h = b[-1][0]
ans = n//2 - b[-1][1]
if a[-1][0] == h:
    if len(a) == 1:
        ans += n//2
    else:
        ans += n//2 - a[-2][1]
else:
    ans += n//2 - a[-1][1]

print(min(ans, hoge))

Measured memory_bytes: 17684
#include<stdio.h>
int main(void){
  char data[3];//文字
  char* result="";//文字列
  int flag=0;
  scanf("%s" , data);
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      if(!(i==j) && (data[i]==data[j])){
        flag+=1;
      }
    }
  }
  if(flag==4){
      result="Yes";
  }else{
      result="No";
  }
  printf("%s",result);
  return 0;
}

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

ans = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      ans[i][j] = '#'

dxy = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
for i in range(H):
  for j in range(W):
    if ans[i][j] == '#':
      continue
    temp = 0
    for dx, dy in dxy:
      ii = i+dx; jj = j + dy
      if 0<=ii<H and 0<=jj<W and S[ii][jj] == '#':
        temp += 1
    ans[i][j] = temp

for a in ans:
  print(*a, sep='')

Measured memory_bytes: 3444
def main():
	n = int(input())
	a = list(map(int,input().split()))
	q = int(input())
	m = list(map(int,input().split()))
	lst = set()
	for i in a:
		templ = list(lst)
		for j in templ:
			lst.add(i+j)
		lst.add(i)
	for i in m:
		if i in lst:
			print("yes")
		else:
			print("no")

main()


Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
map <int,int> mp;
vector<int> V;
#define debug(x) cerr << #x << ": " << x << "\n";
#define INF (1<<29) //53687091
#define INFLL (1ll<<58)
#define EPS (1e-10)
static const int MAX=(int) 1e5;
static const int MOD=(int) 1e9+7;
static const int NMAX=50;
static const int MMAX=50;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
bool XOR(int a,int b){ return !a != !b; }
ll N,A,B;


int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    cin >> N >> A >> B;
    if(N==1ll){
        if(A == B) cout << 1 <<"\n";
        else cout << 0 <<"\n";
    }else if(A > B) cout << 0 <<"\n";
    else{
        cout << (B - A)*(N-2) +1 <<"\n";
    }
    
        
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  
  if(a+b+c+d==21 && a*b*c*d==252){
	printf("YES");
  }else{
    printf("NO");
  }
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;

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

int main() {

    string S;
    cin  >> S;
    ll A = stoi(S)/100;
    ll B = stoi(S)%100;
    string out = "";
    if((A>0&&A<=12)&&(B>0&&B<=12)) out = "AMBIGUOUS";
    else if(A>0&&A<=12) out = "MMYY";
    else if(B>0&&B<=12) out = "YYMM";
    else out = "NA";
    cout << out << endl;
    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Combination{
	vector<ll> fac,finv,inv;
public:
	Combination(ll N){
		fac.resize(N+1);
		finv.resize(N+1);
		inv.resize(N+1);
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for(int i=2;i<=N;i++){
			fac[i] = fac[i-1] * i % atcoder_mod;
			inv[i] = atcoder_mod - inv[atcoder_mod%i] * (atcoder_mod/i) % atcoder_mod;
			finv[i] = finv[i-1] * inv[i] % atcoder_mod;
		}
	}
	ll Caluclation(ll n,ll r){
		if(n < r) return 0;
		if (n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n-r] % atcoder_mod) % atcoder_mod;
	}

};
ll BallBoxCombination4(ll n,ll k){
	Combination comb(n+k-1);
	return comb.Caluclation(n+k-1,n);
}

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

	ll N=in<ll>(),K=in<ll>();
	
	ll ans = BallBoxCombination4(N,K);
	out(ans);
	return 0;
}



Measured memory_bytes: 3228
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    x, y = map(int, readline().split())

    S = S.split('T')
    x0 = len(S[0])
    X = [len(s) for s in S[2::2]]
    Y = [len(s) for s in S[1::2]]

    def solve(vec, p0, p):
        s = {p0}
        for v in vec:
            s, s_prev = set(), s
            for w in s_prev:
                s.add(w + v)
                s.add(w - v)
        return p in s

    if solve(X, x0, x) and solve(Y, 0, y):
        print('Yes')
    else:
        print('No')

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9604
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double EPS = 1e-10;
const int INF = 2147483647;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

char g[55][55];
int h, w;

int main()
{
	cin >> h >> w;

	for (int i = 0;i < 55;i++) {
		for (int j = 0;j < 55;j++) {
			g[i][j] = '.';
		}
	}

	for (int i = 1;i <= h;i++) {
		for (int j = 1;j <= w;j++) {
			cin >> g[i][j];
		}
	}

	for (int i = 1;i <= h;i++) {
		for (int j = 1;j <= w;j++) {
			if (g[i][j] == '#') {
				if (g[i - 1][j] == '.' &&
					g[i + 1][j] == '.' &&
					g[i][j - 1] == '.' &&
					g[i][j + 1] == '.') {
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}

	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scan(&N)
	fmt.Println(f(N, 0, true, true, true))
}

func f(N int, n int, r7, r5, r3 bool) int {
	if n > N {
		return 0
	}
	ret := 0
	if !r7 && !r5 && !r3 {
		ret++
	}
	ret += f(N, n*10+7, false, r5, r3)
	ret += f(N, n*10+5, r7, false, r3)
	ret += f(N, n*10+3, r7, r5, false)
	return ret
}


Measured memory_bytes: 1768
N = int(input())
A = list(map(int, input().split()))
sum = 0
for i in range(N):
    if i == 0:
        continue
    else:
        if A[i-1] <= A[i]:
            ## 身長が後ろの方が高く補正がいらない時はそのまま
            continue
        else:
            height = A[i-1] - A[i]
            A[i] = A[i-1]
            sum += height
print(sum)

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

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    println!("{:.8}", ((n + 1) / 2) as f64 / n as f64);
}


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

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=3000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

int n,m;
vi a,b;
vi c,d;

int main(){
	Init();
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(w==0){
			a.push_back(u);
			b.push_back(v);
		}
		else{
			c.push_back(u);
			d.push_back(v);
		}
	}
	int sa=a.size(),sc=c.size();
	ll res=0;
	for(int i=0;i<1<<sc;i++){
		vi s=a,t=b,e;
		int tmp=0;
		for(int j=0;j<sc;j++) if(i&1<<j){
			s.push_back(c[j]);
			t.push_back(d[j]);
			tmp++;
		}
		m=s.size();
		for(int j=0;j<m;j++){
			e.push_back(s[j]);
			e.push_back(t[j]);
		}
		sort(e.begin(),e.end());
		e.erase(unique(e.begin(),e.end()),e.end());
		map<int,int> mp;
		int N=e.size();
		for(int j=0;j<N;j++) mp[e[j]]=j;
		vvi g(N);
		for(int j=0;j<m;j++){
			int u=mp[s[j]],v=mp[t[j]];
			g[u].push_back(v);
			g[v].push_back(u);
		}
		vi used(N);
		int x=3*n-N,y=0,z=0;
		bool B=0;
		for(int i=0;i<N;i++) if(!used[i]){
			int t=0;
			queue<int> q;
			q.push(i);
			used[i]++;
			int cnt=0;
			while(!q.empty()){
				int v=q.front();q.pop();
				cnt++;
				for(auto u:g[v]) if(!used[u]){
					used[u]++;
					q.push(u);
				}
			}
			if(cnt>3) B=1;
			if(cnt==2) y++;
			if(cnt==3) z++;
		}
		if(B||y>x) continue;
		ll ei=nCk(x,y)*F[y]%mod*Div(F[x-y],Pow(6,(x-y)/3)*F[(x-y)/3]%mod)%mod;
		if(tmp%2==1) (ei*=mod-1)%=mod;
		(res+=ei)%=mod;
	}
	cout<<res<<endl;
}


Measured memory_bytes: 26608
a = int(input())
 
if a<105:
    print(0)
elif 105<= a < 135:
    print(1)
elif 135<= a < 165:
    print(2)
elif 165<= a < 189:
    print(3)
elif 189<= a < 195:
    print(4)
else:
    print(5)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  string a,b;
  int n;
  
  cin >> s;
  a = s[0];
  n = s.size();
  b = s[n-1];
 
  cout << a << n-2 << b << endl;
  
}

Measured memory_bytes: 3596
N = int(input())
P = list(map(lambda x: int(x) - 1, input().split()))
i = 0
res = 0
while i < N:
    cnt = 0
    while i < N and i == P[i]:
        i += 1
        cnt += 1
    res += (cnt + 1) // 2
    while i < N and i != P[i]:
        i += 1
print(res)


Measured memory_bytes: 20648
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()

	//slist := make([]int, n)
	smap := map[string]int{}
	for i := 0; i < n; i++ {
		tmp := nextStr()
		tmp = SortString(tmp)

		smap[tmp]++
	}

	var ans int64 = 0

	for _, s := range smap {
		if s == 1 {
			continue
		}
		ans += int64((s * (s - 1)) / 2)
	}
	fmt.Println(ans)
}

type sortRunes []rune

func (s sortRunes) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
	return len(s)
}

// SortString sort
func SortString(s string) string {
	r := []rune(s)
	sort.Sort(sortRunes(r))
	return string(r)
}

// ---- readfunc
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 14364
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    ll a[n];
    for (int i = 0; i < n-1; i++) {
        scanf("%lld", a+i);
    }
    a[n-1] = 0;

    ll b[5050][220];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%lld", &(b[i][j]));
        }
    }

    ll mp[5050][5050] = {};

    for (int num = 0; num < m; num++) {
        using P = pair<ll, int>;
        vector<P> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = P(b[i][num], i);
        }
        sort(begin(v), end(v), greater<P>());
        set<int> s; s.insert(-1); s.insert(n);
        set<int, greater<int>> rs; rs.insert(-1); rs.insert(n);
        for (auto x: v) {
            int i = x.second;
            ll d = x.first;
            int lw = *rs.lower_bound(i) + 1;
            int up = *s.lower_bound(i) - 1;
            s.insert(i); rs.insert(i);
            mp[lw][i] += d;
            mp[lw][up+1] -= d;
            mp[i+1][i] -= d;
            mp[i+1][up+1] += d;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            mp[i][j] += mp[i][j-1];
        }
    }
    for (int j = 0; j < n; j++) {
        for (int i = 1; i < n; i++) {
            mp[i][j] += mp[i-1][j];
        }
    }
    ll ans = -TEN(18);
    for (int l = 0; l < n; l++) {
        ll dist = 0;
        for (int r = l; r < n; r++) {
            ans = max(ans, mp[l][r] - dist);
            dist += a[r];
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 208832
// D - String Formation
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define irp(i,s,e) for(int i=(s);i>(e);--i)

int main(){
	string S; int Q; cin>>S>>Q;
	int st = Q, ed = st + S.size(), odd = 0;
	S = string(Q,'-') + S + string(Q,'-');
	while(Q--){
		int t; cin>>t; t--;
		if(t){//type2
			int f; char c; cin>>f>>c; f--;
			S[odd ^ f? ed++: --st] = c;
		}
		else odd ^= 1;//type1
	}
	string ans = "";
	if(odd) irp(i, ed-1, st-1) ans += S[i];//odd
	else rp(i, st, ed) ans += S[i];//even
	cout<<ans<<endl;
}

Measured memory_bytes: 1872
#include<bits/stdc++.h>
#define REP(i,x) for(int i=0,i##_len=(x);i<i##_len;++i)
#define rep(i,a,b) for(int i=(a),i##_len(b);i<i##_len;++i)
#define All(x) begin(x),end(x)
#define rAll(x) rbegin(x),rend(x)
using namespace std;
using ll = long long;

int main(){
    int N;cin>>N;
    vector<int> d(N);
    REP(i,N) cin>>d[i];
    sort(All(d));
    cout<<d[N/2]-d[N/2-1]<<endl;
}


Measured memory_bytes: 768
from functools import reduce
import math

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]
    S = []
    S.append(int(input().rstrip()))
    S.append(int(input().rstrip()))
    S.append(int(input().rstrip()))
    S.append(int(input().rstrip()))
    S.append(int(input().rstrip()))
    ans = 0
    min = S[0]
    min_i = 0
    sum = 0
    for i in range(len(S)):
        if min%10 > S[i]%10 and S[i]%10 != 0:
            min = S[i]%10
            min_i = i
    for i in range(len(S)):
        if i != min_i:
            sum += math.ceil(S[i]/10) * 10
        else:
            sum += S[i]
    print(sum)
if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll INF = 5e15;
const ll MOD = 1e9 + 7;

ll N;

struct Cost {
    ll cost;
    ll idx;
    bool A;
    Cost(ll c, ll i, bool A) : cost(c), idx(i), A(A) {}
};

bool valid(const set<ll> &SA, const set<ll> &SB){
    if(SA.empty() || SB.empty()) return true;
    set<ll> tmp;
    for(ll e : SA) tmp.insert(e);
    for(ll e : SB) tmp.insert(e);
    return tmp.size() != N;
}

int main(){
    cin >> N;
    vector<Cost> v;
    for(ll i = 0; i < N; i++){
        ll a, b;
        cin >> a >> b;
        v.push_back(Cost(a, i, true));
        v.push_back(Cost(b, i, false));
    }
    sort(v.begin(), v.end(), [](const auto &a, const auto &b){ return a.cost < b.cost; });
    set<ll> SA, SB;
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        (v[i].A ? SA : SB).insert(v[i].idx);
        ans += v[i].cost;
    }
    if(!valid(SA, SB)){
        if(v[N - 1].idx != v[N].idx){
            ans -= v[N - 1].cost;
            ans += v[N].cost;
        }else{
            ll v1 = v[N].cost - v[N - 2].cost;
            ll v2 = v[N + 1].cost - v[N - 1].cost;
            ans += min(v1, v2);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 15596
use std::io::*; //Not mine.
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut sum = 0;
    let mut a: Vec<Vec<i32>> = vec![vec![0; 3]; 3];
    for i in 0..3 {
        for j in 0..3 {
            let k: i32 = read();
            sum += k;
            a[i as usize][j as usize] = k;
        }
    }
    if(sum % 3 == 0 && sum / 3 == a[0][0] + a[1][1] + a[2][2]){
        println!("Yes");
    }
    else {
        println!("No");
    }
}


Measured memory_bytes: 4352
/*
        _            _                  _            _       _     _         _   _          _          _             _        
       / /\         / /\               / /\         / /\    / /\  /\ \      /\_\/\_\ _     /\ \       /\ \     _    /\ \      
      / /  \       / /  \             / /  \       / / /   / / /  \ \ \    / / / / //\_\   \ \ \     /  \ \   /\_\ /  \ \     
     / / /\ \__   / / /\ \           / / /\ \__   / /_/   / / /   /\ \_\  /\ \/ \ \/ / /   /\ \_\   / /\ \ \_/ / // /\ \_\    
    / / /\ \___\ / / /\ \ \         / / /\ \___\ / /\ \__/ / /   / /\/_/ /  \____\__/ /   / /\/_/  / / /\ \___/ // / /\/_/    
    \ \ \ \/___// / /  \ \ \        \ \ \ \/___// /\ \___\/ /   / / /   / /\/________/   / / /    / / /  \/____// / / ______  
     \ \ \     / / /___/ /\ \        \ \ \     / / /\/___/ /   / / /   / / /\/_// / /   / / /    / / /    / / // / / /\_____\ 
 _    \ \ \   / / /_____/ /\ \   _    \ \ \   / / /   / / /   / / /   / / /    / / /   / / /    / / /    / / // / /  \/____ / 
/_/\__/ / /  / /_________/\ \ \ /_/\__/ / /  / / /   / / /___/ / /__ / / /    / / /___/ / /__  / / /    / / // / /_____/ / /  
\ \/___/ /  / / /_       __\ \_\\ \/___/ /  / / /   / / //\__\/_/___\\/_/    / / //\__\/_/___\/ / /    / / // / /______\/ /   
 \_____\/   \_\___\     /____/_/ \_____\/   \/_/    \/_/ \/_________/        \/_/ \/_________/\/_/     \/_/ \/___________/    
                                                                                                                              
*/
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 2000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(10)

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};
const long long MOD = 998244353;

// typedef long long ll;
#define int long long

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

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

  int n, a[100000]; cin >> n;
  REP(i, n) cin >> a[i];
  int ans = 0;
  REP(i, n){
    if(a[a[i]-1] == i+1) ans++;
  }
  cout << ans/2 << endl;

  return 0;
}

Measured memory_bytes: 1024
import std;

auto input()
{
    return readln().chomp();
}

alias sread = () => readln.chomp();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    long N, M;
    scan(N, M);
    // writeln(M);
    auto AB = new long[][](N);
    // writeln(AB);
    foreach (i; 0 .. N)
    {
        AB[i] = aryread();
    }
    // writeln(AB);
    auto ABのソート = sort(AB);
    // writeln(ABのソート);
    long cost;
    long あと何本買うか = M;
    foreach (i; 0 .. N)
    {
        if (ABのソート[i][1] <= あと何本買うか)
        {
            cost += ABのソート[i][0] * ABのソート[i][1];
            あと何本買うか -= ABのソート[i][1];
            // writeln("co1:", cost);
            // writeln("あと何本買うか:", あと何本買うか);
        }
        else if (ABのソート[i][1] >= あと何本買うか)
        {

            cost += ABのソート[i][0] * あと何本買うか;
            // writeln(AB[i][0]);
            あと何本買うか = 0;
            // writeln("co2:", cost);
            // writeln("あと何本買うか:", あと何本買うか);

        }

    }
    writeln(cost);
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


Measured memory_bytes: 17700
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int main() {
  ll n, m, now=0, ans=0;
  priority_queue<int> que;
  cin >> n >> m;
  vector<P> a(n);
  rep(i, n)  cin >> a[i].first >> a[i].second;
  sort(all(a));
  for(int i = 1; i <= m; i++) {
    while(now < n && a[now].first <= i) {
      que.push(a[now].second);
      now++;
    }
    if(!que.empty()) {
      ans += que.top();
      que.pop();
    }
  }
  cout << ans;
}

Measured memory_bytes: 1660
#include<bits/stdc++.h>
#include<atcoder/dsu>
using namespace std;
using namespace atcoder;
int main(){
  int n, q;
  cin >> n >> q;
  dsu uf(n);
  while(q--){
    int t, x, y;
    cin >> t >> x >> y;
    if(t ==0) uf.merge(x, y);
    else cout << uf.same(x, y) << endl;
  }
}

Measured memory_bytes: 3996
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { -1, 0, 0, 1 };
const ll dy[4] = { 0, -1, 1, 0 };
const ll INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
struct Accelerate_Cin {
	Accelerate_Cin() {
		cin.tie(0);
		ios::sync_with_stdio(0);
		cout << fixed << setprecision(20);
	};
};
///////////////////////////////////////


int main() {
	int N; cin >> N;
	vector<pii>ans;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		ans.push_back({ a,i + 1 });
	}
	sort(ans.begin(), ans.end());
	REP(i, N) {
		cout << ans[i].second << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 1780