akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
# モジュールのインポート
from collections import defaultdict, deque


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, M = list(map(int, input().split()))
    G = defaultdict(set)
    for m in range(M):
        A_i, B_i = list(map(int, input().split()))
        G[A_i - 1].add(B_i - 1)
        G[B_i - 1].add(A_i - 1)

    return N, M, G


def main(N: int, M: int, G: dict) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 人数(2 <= N <= 2 * 10**5)
        M (int): 情報の数(0 <= M <= 2 * 10**5)
        G (dict): 情報
    """
    # 求解処理
    seen = [False for i in range(N)]

    ans = 0
    for i in range(N):
        if seen[i]:
            continue
        friends = 0
        que = deque()

        seen[i] = True
        que.append(i)
        friends += 1

        while len(que) > 0:
            v = que.popleft()
            for w in G[v]:
                if not seen[w]:
                    seen[w] = True
                    que.append(w)
                    friends += 1

        ans = max(ans, friends)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, G = get_input()

    # メイン処理
    main(N, M, G)


Measured memory_bytes: 88116
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const double PI = 3.141592653589793238463;
const ll N=2e5+9;
int main()
{
    FASTINOUT;
    int x;
    cin>>x;
    cout<<(x+1)/2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,cnt=0;
  double ans;
  cin >> n;
  for(int i=1;i<=n;i++){
    if(i%2==1) cnt ++;
  }
  ans = (double)cnt/n;
  printf("%.10f\n",ans);
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String str[] = br.readLine().split(" ");
        long sum = 0;
        int a = 0;
        int max = -1000000;
        int min = 1000000;
        for(int i = 0; i < n; i++){
            a = Integer.parseInt(str[i]);
            if(a > max) max = a;
            if(a < min) min = a;
            sum += a;
        }
        System.out.println(min+" "+max+" "+sum);
    }
}

Measured memory_bytes: 28596
package main

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

var stdin = initStdin()
 
func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func scanInt() int {
	stdin.Scan()
	i, _ := strconv.Atoi(stdin.Text())
	return i
}

func scanStr() string {
	stdin.Scan()
	return stdin.Text()
}

type ia []int

func (ia ia)Len() int {
	return len(ia)
}
func (ia ia)Swap(i, j int) {
	ia[i], ia[j] = ia[j], ia[i]
}
func (ia ia)Less(i, j int) bool {
	return ia[i] < ia[j]
}

func main() {
	n := scanInt()
	var sa ia
	s := 0
	for i := 0; i < n; i++ {
		in := scanInt()
		s += in
		sa = append(sa, s)
	}
	minDiff := s
	for i := 0; i < n; i++ {
		diff := s - 2 * sa[i]
		if diff < 0 {
			diff *= -1
		}
		if minDiff > diff {
			minDiff = diff
		}
	}
	fmt.Println(minDiff)
}

Measured memory_bytes: 640
n = int(input())
w = list(map(int, input().split()))
left, right = w[0], sum(w[1:])
ans = abs(left - right)
for i in range(1, n - 1):
    left += w[i]
    right -= w[i]
    ans = min(ans, abs(left - right))
print(ans)


Measured memory_bytes: 8924
s = input()
q = int(input())

top = ""
tail = ""

rev = 1
#プラスで順列

for i in range(q):
    query = input()
    if query == "1":
        rev *= -1
    elif query[2] == "1":
        if rev == 1:
            top += query[4]
        else:
            tail += query[4]
    else:
        if rev != 1:
            top += query[4]
        else:
            tail += query[4]

if rev == 1:
    print(top[::-1] + s + tail)
else:
    print(tail[::-1] + s[::-1] + top)


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

const int Maxn = 52;
const int Maxd = 4;
const int dy[Maxd] = {-1, 0, 1, 0};
const int dx[Maxd] = {0, -1, 0, 1};

int n, m;
char B[Maxn][Maxn];

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", B[i]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) if (B[i][j] == '#') {
			bool was = false;
			for (int d = 0; d < Maxd; d++) {
				int ni = i + dy[d], nj = j + dx[d];
				if (0 <= ni && ni < n && 0 <= nj && nj < m && B[ni][nj] == '#')
					was = true;
			}
			if (!was) { printf("No\n"); return 0; }
		}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////




int main() {

	ll A, B;
	cin >> A >> B;
	cout << (A - 1)*(B - 1);

	
	system("PAUSE");
}

Measured memory_bytes: 504
// std::set を用いた解
#include <iostream>
#include <functional>
using namespace std;

int main() {
  int W,H,N;
  int x,y,a;
  cin >> W >> H >> N;
  int p[4] = {0, W, 0, H};
  for(int i=0;i<N;i++){
    cin >> x >> y >> a;
    if(a==1) p[0] = max(p[0],x);
    if(a==2) p[1] = min(p[1],x);
    if(a==3) p[2] = max(p[2],y);
    if(a==4) p[3] = min(p[3],y);
  }
  if(p[1]-p[0] > 0 && p[3]-p[2] > 0){
    cout << (p[1]-p[0])*(p[3]-p[2]) << endl;
  }else{
    cout << 0 << endl;  
  }
}

Measured memory_bytes: 256
// ↓ Question Link ↓
// https://atcoder.jp/contests/abc099/tasks/abc099_a
import java.util.Scanner;

public class Main{
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    if(N >= 1000){
      System.out.println("ABD");
    }else{
      System.out.println("ABC");
    }

  }
}

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

int main()
{
    vector<string> days;
    days.push_back("SUN");
    days.push_back("MON");
    days.push_back("TUE");
    days.push_back("WED");
    days.push_back("THU");
    days.push_back("FRI");
    days.push_back("SAT");

    string in; cin >> in;

    int i = 0;
    while(days[i] != in) i++;
    int r = 0 ;
    while(days[i%7] != "SUN") i++, r++;
    if(r == 0) r+=7;
    cout << r << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int main() {
    LL X, Y;
    scanf("%lld %lld", &X, &Y);
    if (abs(X - Y) < 2) puts("Brown");
    else puts("Alice");
    return 0;
}


Measured memory_bytes: 256
<?php
$input = explode(' ', trim(fgets(STDIN)));

$n = (int)$input[0];
$k = (int)$input[1];

$sum = 0.0;
for ($i=1; $i <= $n ; $i++) { 
	$tmp = $i;
	if ($tmp >= $k) {
		$sum += 1 / $n;
	}else{
		$limit = $k / $tmp;
		$co = 1;
		while (pow(2, $co) < $limit) {
			$co += 1;
		}
		$sum += 1 / (pow(2, $co) * $n);
	}
}
echo $sum;

Measured memory_bytes: 4604
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#define ll long long
#define pai 3.1415926535897932384626433832795028841971693
long long min(long long a, long long b){
    if(a < b) return a;
    else return b;
}
long long max(long long a, long long b){
    if(a < b) return b;
    else return a;
}
int main(){
 int n,k,t;
scanf("%d %d %d",&n,&k,&t);
  if(n%k==0 && n/k<=t){
    printf("Yes");
  }
  else if(n%k!=0 && n/k +1 <=t){
    printf("Yes");
  }
  else{
    printf("No");
  }
  return 0;
}


Measured memory_bytes: 1732
n, A, B = map(int, input().split())
z = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 18

d = {(0, 0):0}
for a, b, cost in z:
    newd = []
    for (x, y), c in d.items():
        new = (a+x, b+y)
        if new not in d or d[new] > c + cost:
            newd.append((new, c+cost))
    for new, newc in newd:
        d[new] = newc

ans = inf
for i in range(1, 10 * n):
    t = (A * i, B * i)
    if t in d:
        ans = min(ans, d[t])
if ans == inf:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 7896
#include<bits/stdc++.h>
#include <iostream>
#include<cstdio>
#include <cmath>
#define endl '\n'
using namespace std;
int box[102];
int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	for(int i = 1; i<=m; i++)
	{
		int p;
		cin>>p;
		box[p] = 1;
	}
	//int R = 0, L = 0,toll = 0;
	int tollR = 0,tollL=0,posR =x,posL = x;
//	if(abs(n-x)<x)R=1;
//    else L=1;
	//cout<<R<<L;
	//abs(n-x)<=x?R=1:L=1;
	//if(R){
		while(posR!=n){
			if(box[posR+1]==1)tollR++,posR++;
			else if(!box[posR+1])posR++;
		}
	//}
	//else if(L){
		while(posL!=0){
			if(box[posL-1]==1)tollL++,posL--;
			else if(!box[posL-1])posL--;
		}
	//}
	cout<<min(tollR,tollL)<<endl;	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#include<cstdio>
#include<iomanip>
using namespace std;

int main(){
    double l,ans;
    cin >> l;
    ans = l*l*l;
    cout << setprecision(10) << ans / 27 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, n) for(int i=(a); i<(n); i++)
using namespace std;

int main(){
    string n;cin >> n;
    string ans = "ABC" + n;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
string s,an="";

cin>>s;
for(auto i: s)
{
    if(i=='B'&&an.size())an.pop_back();
    else if(i!='B')an.push_back(i);
}
cout<<an<<endl;
    
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define pll pair<ll,ll>
#define vll vector<ll>
#define forn(i,n) for(ll i=0; i<n; ++i)
#define pb push_back
#define MOD 1000000007
#define range(c) c.begin() , c.end()
#define dbvec(a) for(auto it : a)cout << (it) <<" ";cout << endl;
#define test ll t;cin >> (t);while(t--)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : ";cout << arg1 <<" ";}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {const char *comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : ";
cout << arg1 <<" ";cout << " | ";__f(comma + 1, args...);}
char local ='O';
#define db(...) if(local=='L') {__f(#__VA_ARGS__, __VA_ARGS__); cout<<endl;}
//////////////////////////////////////////////////////////////
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
    local = 'L';
#endif

    string s;
    cin >> s;
   int a = 0;
   for(int i=0;i<s.size();i++)
   {
       int ans = 0;
       while(s[i] == 'R')
    {
        ans++;i++;
    }
    a = max(a, ans);
   }
   cout << a << endl;
}

Measured memory_bytes: 3632
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  input.shift();
  input.splice(N,input.length);
  var a = input.map(i => parseInt(i));
  var ans = 0;
  var x =0;
  for(var i=0;i<N;i++){
    ans++;
    x = a[x]-1;
    if(x==1){
      break;
    }
    if(i==N-1){
      ans=-1;
    }
  }

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 30280
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<list>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {1, 1, 0, -1, -1, 0};
int dx[] = {1, 0, -1, -1, 0, 1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

bool comp(pair<pii, int> lhs, pair<pii, int> rhs) {
    if (lhs.first.first != rhs.first.first)
        return lhs.first.first > rhs.first.first;
    else if (lhs.first.second != rhs.first.second)
        return lhs.first.second < rhs.first.second;
    else return lhs.second < rhs.second;
    return lhs.first.first > rhs.first.first;
}
int solve() {
    int n, p, r;
    cin >> n >> p >> r;
    if (n == 0 && p == 0 && r == 0) return -1;
    int co[n], wr[p][n], pen[p][n];
    rep(i, n) co[i] = 0;
    rep(i, p) rep(j, n) wr[i][j] = pen[i][j] = 0;
    rep(i, r) {
        int tid, pid, time; string mes;
        //problem id
        cin >> tid >> pid >> time >> mes;
        tid--; pid--;
        if (mes == "WRONG") {
            wr[pid][tid]++;
        } else {
            co[tid]++;
            pen[pid][tid] = wr[pid][tid] * 1200 + time;
        }
    }
    int tmp[n];
    rep(i, n) tmp[i] = 0;
    rep(i, n) rep(j, p) tmp[i] += pen[j][i];
    //rep(i, n) cout << co[i] << " "; cout << endl;
    /*
    rep(i, p) {
        rep(j, n) cout << pen[i][j] << " "; cout << endl;
    }
     */
    
    vector<pair<pii, int> > v(n);
    rep(i, n) {
        v[i].first.first = co[i];
        v[i].first.second = tmp[i];
        v[i].second = i;
        
    }
    sort(v.begin(), v.end(), comp);
    rep(i, n) {
        cout << v[i].second + 1 << " " << v[i].first.first << " " << v[i].first.second << endl;
    }
    return 0;
}
int main() {
    while (solve() == 0) {
        
    }
}



Measured memory_bytes: 3176
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define SP << " " <<
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
bool ok = true;
vector<ll> X(5050);
vector<ll> other(5050);
struct edge{ll to;};
struct graph{
    ll N;
    vector<vector<edge> > G;

    graph(ll n): N(n), G(N) {}

    void ade(ll s, ll t){
        G[s].emplace_back((edge){t});
        //G[t].emplace_back((edge){s}); //無向ならON
    }

    void dfs(ll v=0){
        for(auto E : G[v]){
            dfs(E.to);
        }
        vector<ll> A(5050,INF2);
        A[0]=0;
        for(auto E : G[v]){
            repr(i,5020,0){
                if(A[i]==INF2) continue;
                ll buf=A[i];
                A[i]=INF2;
                // 同じ色として取る
                if(i+X[E.to]<=X[v]){
                    mini(A[i+X[E.to]],buf+other[E.to]);
                }
                // 別の色として取る
                if(i+other[E.to]<=X[v]){
                    mini(A[i+other[E.to]],buf+X[E.to]);
                }

            }
        }
        ll ans=INF2;
        rep(i,X[v]+1){
            mini(ans,A[i]);
        }
        if(ans==INF2) { ok=false;}
        other[v]=ans;
    }
};
//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    graph g(N);
    rep(i,N-1){
        ll p; cin>>p; --p;
        g.ade(p, i+1);
    }
    rep(i,N){
        cin>>X[i];
    }
    g.dfs(0);
    cout<< ( ok ? "POSSIBLE" : "IMPOSSIBLE" )<<"\n";
    // 自身の数, もう片方の色の最小値
}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 512
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;

int main(){

    int n,a,b;
    cin >> n >> a >> b;

    int sum = 0;
    for(int i=1;i<=n;i++){
        int tmp = i;
        bool end = 0;
        int num = 0;
        while(!end){
            if(tmp>0){
                num=num + tmp%10;
                tmp= tmp/10;
            }else{
                end = 1;
            }
        }
        if(num>=a && num<=b) sum+=i;
    }

    cout << sum << endl;

   return 0;
}

Measured memory_bytes: 256
//| #######################|
//|  ADARSH SINGH KUSHWAHA |
//| ###################### |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Bahut_tej_gand_faad ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define fr(i,a,b) for(ll i=a;i<b;i++)
#define frb(i, a, b) for(ll i = a - 1; i >= b; i--)
#define pb push_back
#define ff first
#define ss second
#define mp map<ll,ll>
#define mps map<char,ll>
#define v vector<ll>
#define srt(v) sort(v.begin(),v.end())
#define mod 1000000007
#define max 1000001
void solve() {
    ll n;
    cin >> n;
    ll sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        ans += (sum * a);
        ans = ans % mod;
        sum += a;
        sum = sum % mod;
    }
    cout << ans << endl;
}
int main() {
    Bahut_tej_gand_faad;

    //int t;
    //cin >> t;
    //while (t--) {
    solve();
    //}
    return 0;
}

Measured memory_bytes: 3640
// 関節点
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>

using namespace std;

#define MAX 100000

vector<int> G[MAX];
int N;
bool visited[MAX];
int prenum[MAX], parent[MAX], lowest[MAX], timer;

void dfs(int current, int prev)
{
    // --------------------------------
    // ノード current を訪問した直後の処理
    // --------------------------------
    prenum[current] = lowest[current] = timer;
    timer++;

    visited[current] = true;

    int next;

    for(int i = 0; i < G[current].size(); i++)
    {
        // 次に訪問する頂点の頂点No.
        next = G[current][i];

        if( !visited[next] )
        {
            // ----------------------------------------------
            // ノード current からノード next へ訪問する直前の処理
            // ----------------------------------------------

            // 次に訪問する頂点の親を設定しておく
            parent[next] = current;

            dfs(next, current);

            // ノード next の探索が終了した直後の処理
            // ここで、current は next の親になる
            lowest[current] = min(lowest[current], lowest[next]);
        }
        else if( next != prev )
        {
            // エッジ current --> next が Back-edge の場合の処理
            lowest[current] = min(lowest[current], prenum[next]);
        }
    }

    // -------------------------------------
    // ノード current の探索が終了した直後の処理
    // -------------------------------------
}

void art_points()
{
    for(int i = 0; i < N; i++)
    {
        visited[i] = false;
    }

    timer = 1;

    // lowest の計算
    dfs(0, -1); // 0 == root_num

    set<int> ap;
    int np = 0;

    for(int i = 1; i < N; i++)
    {
        int p = parent[i];

        if( p == 0 )
        {
            np++;
        }
        else if( prenum[p] <= lowest[i] )
        {
            ap.insert(p);
        }
    }

    if( np > 1 )
    {
        ap.insert(0);
    }

    for(set<int>::iterator it = ap.begin(); it != ap.end(); it++)
    {
        cout << *it << endl;
    }
}

int main(void)
{
    int m;

    cin >> N >> m;

    for(int i = 0; i < m; i++)
    {
        int s, t;
        cin >> s >> t;

        G[s].push_back(t);
        G[t].push_back(s);
    }

    art_points();

    return 0;
}



Measured memory_bytes: 6908
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B = get_ints

max = [A, B].max
min = [A, B].min

if max > min
  puts max * 2 - 1
else
  puts max * 2
end


Measured memory_bytes: 14400
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using vlli=vector<ll>::iterator;
void solve();
ll sum(ll,ll);

ll n;
vector<ll> a;
vector<ll> s;

int main(){
	solve();
	return 0;
}
void solve(){
	cin >>n;
	a.resize(n+1);
	s.resize(n+1);
	a[0]=0;
	s[0]=a[0];
	for(ll i=1;i<=n;i++){
		cin >>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	ll ans=1e18;
	for(ll i=1;i<n;i++){
		ans=min(ans,abs(sum(1,i)-sum(i+1,n)));
	}
	cout <<ans <<endl;
}

ll sum(ll l,ll r){
	return s[r]-s[l-1];
}

Measured memory_bytes: 3328
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double DB;
const int N=100005;
struct node
{
    DB x,y;
}a[N],O;
int n;
DB r;
inline DB power(DB x)
{
    return x*x;
}
inline DB dis(node a,node b)
{
    return sqrt(power(a.x-b.x)+power(a.y-b.y));
}
inline bool in_circle(node a)
{
    return dis(a,O)<=r?1:0;
}
inline int calc(DB a,DB b,DB c,DB d,DB e,DB f)
{
    O.x=(b*f-d*e)/(b*c-a*d);
    O.y=(c*e-a*f)/(b*c-a*d);
}
inline void min_cover_circle(void)
{
    register int i,j,k;
    random_shuffle(a+1,a+n+1);
    for (i=1;i<=n;++i)
    if (!in_circle(a[i]))
    {
        O=a[i]; r=0;
        for (j=1;j<i;++j)
        if (!in_circle(a[j]))
        {
            O.x=(a[i].x+a[j].x)/2.0; O.y=(a[i].y+a[j].y)/2.0; r=dis(a[i],O);
            for (k=1;k<j;++k)
            if (!in_circle(a[k])) calc(a[i].x-a[j].x,a[i].y-a[j].y,a[i].x-a[k].x,a[i].y-a[k].y,
            ((power(a[i].x)-power(a[j].x))-(power(a[j].y)-power(a[i].y)))/2.0,
            ((power(a[i].x)-power(a[k].x))-(power(a[k].y)-power(a[i].y)))/2.0),r=dis(a[i],O);
        }
    }
    printf("%.10lf\n",r);
}
int main()
{
    register int i; scanf("%d",&n);
    for (i=1;i<=n;++i)
    scanf("%lf%lf",&a[i].x,&a[i].y);
    min_cover_circle();
    return 0;
}


Measured memory_bytes: 128
n,q=gets.split.map(&:to_i)
l=[nil]*n
q.times do
  t,u,v=gets.split.map(&:to_i)
  if t==0
    s=[]
    while l[u]
      s << u
      u=l[u]
    end
    s << u
    while l[v]
      s << v
      v=l[v]
    end
    s << v
    u=[u,v].min
    s.each do |su|
      l[su]=u if su!=u
    end
  else
    s=[]
    while l[u]
      s << u
      u=l[u]
    end
    s.each do |su|
      l[su]=u
    end
    s=[]
    while l[v]
      s << v
      v=l[v]
    end
    s.each do |su|
      l[su]=v
    end
    if u==v
      puts 1
    else
      puts 0
    end
  end
end


Measured memory_bytes: 15776
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<int> m(n);
  rep(i, 0, n) cin >> m[i];
  int check = 0;
  int ans = 0;
  rep(i,0,n){
    if(m[i] >= check) {
      check = m[i];
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628
n=int(input())
a=sorted([int(i) for i in input().split()])
color=[0]*9
for i in a:
    if i<400:
        color[0]=1
    elif i<800:
        color[1]=1
    elif i<1200:
        color[2]=1
    elif i<1600:
        color[3]=1
    elif i<2000:
        color[4]=1
    elif i<2400:
        color[5]=1
    elif i<2800:
        color[6]=1
    elif i<3200:
        color[7]=1
    else:
        color[8]+=1
print("{} {}".format((sum(color[:8]) if sum(color[:8])>0 else 1),sum(color)))

Measured memory_bytes: 38384
#include <iostream>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define in(v) if (scanf("%d", &v)<1);

int main() {
  int N, M;
  in(N); in(M);

  int p = 2;
  rep(i, M-1)
    p*=2;
  int t = (N-M) * 100 + (M) * 1900;
  printf("%d\n", t*p);

  return 0;
}


Measured memory_bytes: 256
//ishan.nitj
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cout << #x << " =  " << x << endl;
#define dbg2(x, y) cout << #x << " =  " << x << " " << #y << " =  " << y << endl;
#define N 12345
#define MX 30
#define int long long
int arr[N];
int n;
vector<int> ans;

void solve(vector<int> v) {
    int sz = v.size();
    for(int i = n; i >= v[sz-1]+1; i--)
        ans.emplace_back(i);
    for(int i = sz - 1; i >= 1; i--) {
        int st = v[i] + v[i-1];
        st/=2;
        int en = v[i-1]+2;
        if(v[i-1] == v[i] - 2)
            continue;
        for(int i = st; i >= en; i--)
            ans.emplace_back(i);
    }
    v[0]--;
    while(v[0]--)
        ans.emplace_back(1);
    sz--;
    while(sz--)
        ans.emplace_back(2);
}

int check() {
    for(auto& it:ans)
        it--;

    vector<int>tmp;
    for(int i = 1; i <= n; i++)
        tmp.emplace_back(arr[i]);

    for(auto it:ans) {
        int sz  = tmp.size();
        if(it == sz-1 || it == 0)
            tmp.erase(tmp.begin() + it);
        else {
            int x = tmp[it-1];
            int y = tmp[it+1];
            tmp[it] = x+y;
            tmp.erase(tmp.begin() + it + 1);
            tmp.erase(tmp.begin() + it - 1);
        }
    }
    return tmp[0];
}
signed main() {
//    freopen("/home/ishan/Contest/IP.txt","r",stdin);
    cin >> n;
    bool allNegative = true;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        if(arr[i] >= 0)
            allNegative = false;
    }
    if(allNegative) {
        int mx = INT_MIN, idx;
        for(int i = 1; i <= n; i++){
            if(arr[i] > mx){
                idx = i;
                mx = arr[i];
            }
        }
        cout << mx << endl;
        for(int i = n; i >= idx + 1; i--) {
            ans.emplace_back(i);
        }
        idx--;
        while(idx--)
            ans.emplace_back(1);
        cout << ans.size() << endl;
        for(auto it:ans)
            cout << it << endl;
        return 0;
    }

    int oddSum = 0, evenSum = 0;
    vector<int> odd, even;
    for(int i = 1; i <= n; i++){
        if(i%2 == 1 && arr[i] >= 0) {
            oddSum+= arr[i];
            odd.emplace_back(i);
        }
        else if(i%2 == 0 && arr[i] >= 0) {
            evenSum += arr[i];
            even.emplace_back(i);
        }
    }
    if(oddSum > evenSum) {
        cout << oddSum << endl;
        solve(odd);
    }
    else{
        cout << evenSum << endl;
        solve(even);
    }

       assert(check() == max(evenSum, oddSum)); 
    cout << ans.size() <<endl;
    for(auto it:ans)
        cout << it + 1 << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long int
#define ld long double
#define pb push_back
#define pf push_front
#define ft first
#define sc second
#define all(v) v.begin(), v.end()
using namespace std;
const int maxn = 3011, mod = 998244353;
int dp[maxn][maxn];
signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, s;
    cin >> n >> s;
    vector<int> mas(n, 0);
    for (int d = 0; d < n; d++) {
        cin >> mas[d];
    }
    dp[0][0] = 1;
    for (int d = 1; d <= n; d++) {
        dp[d][0] = d + 1;
        dp[d][mas[d - 1]] = dp[d - 1][mas[d - 1]] + d;
        //cout << dp[d][0] << " ";
        for (int s1 = 1; s1 <= s; s1++) {
            if (s1 != mas[d - 1]) {
                dp[d][s1] = dp[d - 1][s1];
                if (s1 >= mas[d - 1]) {
                    dp[d][s1] += dp[d - 1][s1 - mas[d - 1]];
                }
             }
             dp[d][s1] %= mod;
             //cout << dp[d][s1] << " ";
        }
        //cout << "\n";
    }
    int ans = 0;
    int tk = 1;
    for (int d = n - 1; d >= 0; d--) {
        if (s >= mas[d]) {
            ans += tk * dp[d][s - mas[d]];
            ans %= mod;
        }
        tk++;
    }
    cout << ans;
}


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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int acc = 0;
    int s = 1;
    while(acc < N){
        acc += s;
        s++;
    }
    for(int i = 1; i < s; i++){
        if(acc - N != i) cout << i << endl;
    }
    return 0;
}

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

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  cout << (char)toupper(s1.at(0)) << (char)toupper(s2.at(0)) << (char)toupper(s3.at(0)) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5];
    int j=0;
    for(int i=0;i<5;i++){
    scanf("%d",&a[i]);
    if(a[i] == 0){
         j =i+1;
    }
    }
    printf("%d",j);
    return 0;
}

Measured memory_bytes: 3836
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
	public static void main (String[] args) {
		int[] arr = new int[5];
		Scanner sc = new Scanner (System.in);
		for (int i = 0; i<5; i++) {
			arr[i] = sc.nextInt();
			if (arr[i] == 0) 
				System.out.println(i+1);
		}
	}
}


Measured memory_bytes: 35632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main()
{
	ll n, k;
	cin >> n >> k;
 
	vector<ll> v(n, 0);
	for(ll i = 0; i < n; ++i) {
	cin >> v.at(i);
	--v[i];
	}
 
	set<int> s_used;
	vector<int> v_path;
 
	int now = 0;
 
	while(s_used.count(now) == 0) {
		v_path.push_back(now);
		s_used.insert(now);
		now = v[now];
	}
 
	// ???
	int s = find(v_path.begin(), v_path.end(), now) - v_path.begin();
	int r = (int)v_path.size() - s;
 
	//cout << s << " " << r << "\n";
 
	if(s >= k) cout << v_path[k] + 1 << "\n";
	else {
		cout << v_path[(k - s) % r + s] + 1 << "\n";
	}
 
	return 0;
}

Measured memory_bytes: 14628
def max(a,b):
	if(a>b):
		return a
	else:
		return b

def min(a,b):
	if(a<b):
		return a
	else:
		return b

list = []
def segitiga(a, b, c):

	a=int(a)
	b=int(b)
	c=int(c)

	if(a==b or b==c or a==c):
		return False;
	else:
		x=min(a,min(b,c))
		y=max(min(a,b), min(max(a,b),c))
		z=max(a,max(b,c))
		ans = (x+y >z)
		return ans




n=int(input())
sisi=input()
sisi=sisi.split()
cnt=0
for i in range(n):
	for j in range(i+1,n):
		for k in range(j+1,n):
			if(i!=j and i!=k and j!=k):
				if(segitiga(sisi[i], sisi[j], sisi[k])):
					cnt+=1
print(cnt)

Measured memory_bytes: 9136
# -*- coding: utf-8 -*-
a = [int(input()) for _ in range(5)]

time = 0

min_r = 10
for i in a:
    r = i % 10
    if r == 0:
        time += i
    else:
        time += i + 10 - r
        min_r = min(r, min_r)

if min_r != 10:
    time -= 10 - min_r 

print(time)


Measured memory_bytes: 2940
# -*- coding: utf-8 -*-
n = int(input())
# スペース区切りの整数の入力
a_list = list(input().split())

count = 10000000

for i in range(len(a_list)):
    a_tmp = int(a_list[i])
    count_tmp = 0
    while int(a_tmp) % 2 == 0:
        a_tmp /= 2
        count_tmp += 1
    if count > count_tmp:
        count = count_tmp
print(count)


Measured memory_bytes: 2940
# C - いっしょ / Be Together
N = int(input())
A = list(map(int, input().split()))
ans = 10**8

for X in range(-100,101):
    tmp = 0
    for i in range(N):
        tmp += (A[i]-X)**2
    if ans >= tmp:
        ans = tmp
    else:
        pass

print(ans)

Measured memory_bytes: 3060
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int month = 1;
	static int day = 1;
	static int Day_ex = 1;
	static int i = 0;
	public static void main(String[] args) {
		while(read());
		
		
	}

	static boolean read(){
		//if(!sc.hasNext())return false;
				
		month = sc.nextInt();
		day = sc.nextInt();
		if(month == 0 && day == 0){
			return false;
		}
		slove();
		return true;
	
	}
	
	static void slove(){
			
		if(1 == month){
			Day_ex = day;
		}else if(2 == month){
			Day_ex = 31 + day;
		}else if(3 == month){
			Day_ex = 60 + day;
		}else if(5 >= month){
			Day_ex = (month - 1) * 30 + day + 1;
		}else if(7 >= month){
			Day_ex = (month - 1) * 30 + day + 2;
		}else if(8 == month){
			Day_ex = (month - 1) * 30 + day + 3;
		}else if(10 >= month){
			Day_ex = (month - 1) * 30 + day + 4;
		}else{ //else(12 >= month)
			Day_ex = (month - 1) * 30 + day + 5;
		}
			//System.out.println("Day_ex = " + Day_ex);
		
		i = Day_ex%7;
		if(i == 1){
			System.out.println("Thursday");
		}else if(i == 2){
			System.out.println("Friday");
		}else if(i == 3){
			System.out.println("Saturday");
		}else if(i == 4){
			System.out.println("Sunday");
		}else if(i == 5){
			System.out.println("Monday");
		}else if(i == 6){
			System.out.println("Tuesday");
		}else{
			System.out.println("Wednesday");
		}
		
	}
}

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

using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n-1;i>=s;i--)
#define repe_r(i,s,n)for(int i = n;i>=s;i--)

ll a[200001] = {};
ll b[200001] = {};
ll ans[200001] = {};
int main() {
	ll n; cin >> n;
	repe(i, 1, n) cin >> a[i];

	repe_r(k, 1, n) {
		ll ball = 0;
		rep(s, 2, 200001) {
			if (k*s <= n) {
				ball += b[k*s];
			}
			else {
				break;
			}
		}

		b[k] = (ball % 2) ^ a[k];
		//if (ball % 2) {
		//	if (a[k]) {
		//		b[k] = 0;
		//	}
		//	else {
		//		b[k] = 1;
		//	}
		//}
		//else {
		//	if (a[k]) {
		//		b[k] = 1;
		//	}
		//	else {
		//		b[k] = 0;
		//	}
		//}
	}

	//ans;
	ll p = 0;
	repe(i, 1, n) {
		if (b[i]) {
			ans[p++] = i;
		}
	}

	cout << p << endl;
	rep(i, 0, p) {
		cout << ans[i];
		if (i != p - 1)cout << " ";
	}

	cout << endl;
	return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

//#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

//ostream& operator << (ostream &a, const vector<int> &b) {
//    for (auto k : b) cout << k << " ";
//    return a;
//}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 10;
//    const ld PI = 3.1415926535;
#else
    #define dbg(x)
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 179;
//    const ld PI = 3.1415926535;
#endif

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b;
    cin >> a >> b;
    int n1, n2;
    cin >> n1 >> n2;
    string s;
    cin >> s;
    if (s == a) n1--;
    else n2--;
    cout << n1 << " " << n2;
}
/*

*/


Measured memory_bytes: 888
import java.util.Scanner;

public class Main{
	
	static String change(String s, String type, int num) {
		String ans="";
		if(type.equals("L")) {
			if(num==0) {
				ans = s.toLowerCase();
			}
			else {
				ans=String.valueOf(s.charAt(0)).toUpperCase();
				for(int i=1; i<s.length(); i++) {
					ans+=String.valueOf(s.charAt(i)).toLowerCase();
				}
			}
		}
		else if(type.equals("U")) {
				ans=String.valueOf(s.charAt(0)).toUpperCase();
				for(int i=1; i<s.length(); i++) {
					ans+=String.valueOf(s.charAt(i)).toLowerCase();
				}
			
		}
		else {
			if(num==0) {
				ans = s.toLowerCase();
			}
			else {
				ans = "_"+s.toLowerCase();
			}
		}
		
		return ans;
	}
	
	public static void main(String[] args) {
		  try(Scanner sc = new Scanner(System.in)) {
			  while(sc.hasNext()) {
				  String str=sc.next();
				  String type=sc.next();
				  if(type.equals("X")) break;
				  int num=0;
				  String ans="";
				  if(str.contains("_")) {
					  String[] tokens=str.split("_");
					  num=0;
					  for(String t:tokens) {
						  ans+=change(t, type, num);
						  num++;
					  }
				  }
				  else {
					  int start=0,last=0;
					  num=0;
					  for(int i=0; i<str.length(); i++) {
						  if(Character.isUpperCase(str.charAt(i)) && last==i) {
							  int index=str.length()-1;
							  for(int j=i+1; j<str.length(); j++) {
								  if(Character.isUpperCase(str.charAt(j))) {
									  index=j;
									  last=index;
									  ans+=change(str.substring(start, index), type, num);
									  num++;
									  start=index;
									  break;
								  }
							  }
						  }
						  else if(Character.isUpperCase(str.charAt(i))&& start!=i) {
							  last=i;
							  ans+=change(str.substring(start, i), type, num);
							  if(i!=0)num++;
							  start=i;
						  }
					  }
					  if(last<str.length()) {
						  ans+=change(str.substring(last, str.length()), type, num);
					  }
				  }
				  System.out.println(ans);
			  }
		  }
	}
}


Measured memory_bytes: 25980
N, M = map(int,input().split())
X = sorted(list(map(int, input().split())))
if  M <= N:
    print(0)
else:
    L = []
    for i in range(M-1):
        L.append(X[i+1]-X[i])
    L = sorted(L)
    print(sum(L[:M-N]))

Measured memory_bytes: 13968
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+ 5;
const int M = 1e7 + 5;
const int INF=1e9+7;
const int mod=1e9+7;
const double eps=1e-9;
typedef long long ll;
typedef pair<int,int>pi;

vector <ll> solve(vector <ll> a){
    ll n = a.size();
    vector <ll> pref(n+2, 0);
    for(int i = 0; i < n; i++){
        int l = max(0LL,i-a[i]);
        int r = min(n-1LL, i+a[i]);
        pref[l]++;
        pref[r+1]--;
    }
    for(int i = 0; i < n; i++){
        if(i) pref[i] += pref[i-1];
        a[i] = pref[i];
    }
    return a;
}

int check(vector <ll> a){
    int n = a.size();
    for(int i = 0; i < n; i++){
        if(a[i] != n) return 0;
    }
    return 1;
}


int main() {
    vector <int> vec(6);
    int ans;
    for(int i = 1; i <= 5; i++){
        cin >> vec[i];
        if(!vec[i]) ans = i;
    }

    cout << ans;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
//const int MOD=1e9+7;
const int MOD=998244353;
const long long LINF=1e18;
#define int long long
//template
template<typename T>
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n_,T d):n(n_),bit(n_+1,d){}

  T sum(int i){
    T s=bit[0];
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }

  int lower_bound(int w){
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;
  }

  T sum0(int i){
    return sum(i+1);
  }
  void add0(int i,T a){
    add(i+1,a);
  }

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

  T query0(int l,int r){
    return sum(r)-sum(l);
  }
};
int pw(int n,int k){
  if(k<0)return pw(n,k+MOD-1);
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}
//main
signed main(){
  int N;cin>>N;
  std::vector<int> x(N),y(N);
  for(int i=0;i<N;i++)cin>>x[i]>>y[i];
  typedef pair<int,int> P;
  std::vector<P> v(N);
  for(int i=0;i<N;i++)v[i]=P(x[i],y[i]);
  sort(v.begin(),v.end());
  map<int,int> mx,my;//mxはデバッグする時にあると楽
  for(int i=0;i<N;i++)mx[x[i]]=my[y[i]]=0;
  int cnt=0;for(auto &p:my)p.second=++cnt;
  cnt=0;for(auto &p:mx)p.second=++cnt;
  BIT<int> b1(223456,0),b2(223456,0);
  std::vector<int> ru(N,0),rd(N,0),lu(N,0),ld(N,0);
  for(int i=0;i<N;i++){
    ld[i]=b1.sum(my[v[i].second]);
    lu[i]=i-ld[i];
    b1.add(my[v[i].second],1);
  }
  for(int i=N-1;i>=0;i--){
    rd[i]=b2.sum(my[v[i].second]);
    ru[i]=N-1-i-rd[i];
    b2.add(my[v[i].second],1);
  }
  int ans=0;
  for(int i=0;i<N;i++){
    int a=pw(2,lu[i]),b=pw(2,ru[i]),c=pw(2,ld[i]),d=pw(2,rd[i]);
    ans+=(((b-1)*(c-1)%MOD)*((a*d)%MOD))%MOD;ans%=MOD;
    ans+=((a-1)*(d-1))%MOD*(b+c-1)%MOD;ans%=MOD;
  }
  ans+=pw(2,N-1)*N%MOD;ans%=MOD;
  cout<<ans<<endl;
}

/*
解説AC
なんか幾何の知識使いそうな気がして見ちゃったけどこれは解けてもおかしくはないかな
問題文を言い換えて各点が何回含まれるかの方に着目するってのは典型なので覚えておく
BITのことをもう一度理解するためにtemplate<typename T>についてちょっとだけ学んだ
sortしてBITすることでluたちを数えられるのも典型知識として取り込みたいね
*/


Measured memory_bytes: 41216
import core.bitop;
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  foreach (i, c; readln.chomp) {
    if (i % 2 == 1) {
      continue;
    }
    c.write;
  }
  writeln;
}


Measured memory_bytes: 508
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
#include<map>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;i++)


int main()
{
	ll n, m;
	cin >> n >> m;
	ll ans = 0;
	ll a, b;
	vector<ll> x(m);
	vector<ll> y(m);
	
	for (ll i = 0; i < m; i++)
	{
		cin >> x[i] >> y[i];
	}
	int min = *min_element(y.begin(), y.end());
	int max = *max_element(x.begin(), x.end());
	if (max <= min)
	{
			ans = min - max + 1;
	}
	
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 4768
program main
    implicit none
    integer(8) N, i, ans, k, j
    integer(8) :: r = 0, b = 0, g = 0
    character S * 4000
    read(*, *) N, S
    do i = 1, N
        if (S(i:i) == "R") then
            r = r + 1
        else if (S(i:i) == "B") then
            b = b + 1
        else
            g = g + 1
        end if
    end do
    ans = r * b * g
    do i = 1, N - 2
        do j = i + 1, N - 1
            if (S(i:i) /= S(j:j)) then
                k = 2 * j - i
                if (k <= N .and. S(i:i) /= S(k:k) .and. S(j:j) /= S(k:k)) then
                    ans = ans - 1
                end if
            end if
        end do
    end do
    write(*, '(I0)') ans
    stop
contains
end program main

Measured memory_bytes: 2904
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
struct UnionFind {
private:
    ll N;
    vector<ll> parent;
    vector<ll> num;

public:
    UnionFind(ll n){
        N = n;
        rep(i,0,N) parent.push_back(i);
        rep(i,0,N) num.push_back(1);
    }
    ll root(ll x){
        if(x == parent[x]) return x;
        else return parent[x] = root(parent[x]);
    }
    void unite(ll a, ll b){
        a = root(a); b = root(b);
        if(a == b) return;
        parent[a] = b;
        ll sum = num[a] + num[b];
        num[a] = sum;
        num[b] = sum;
    }
    bool same(ll a, ll b){ return root(a) == root(b);}
    ll sz(ll x){ return num[x];}
};
ll X[100010], Y[100010], Z[100010];
UnionFind uf(100010);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    rep(i,0,M){
        cin >> X[i] >> Y[i] >> Z[i];
        Z[i] %= 2;
        X[i]--; Y[i]--;
    }
    ll ans = N;
    rep(i,0,M){
        if(not uf.same(X[i], Y[i])){
            uf.unite(X[i], Y[i]);
            ans--;
        }
    }
    print(ans);



}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
const int MAX_V = 10000;
typedef pair<int, int>P;
#define MOD (ll)1000000007
int main() {
  string K;
  int D;
  cin>>K>>D;
  ll dp[10010][D][2];
  rep(i,10010){
    rep(j,D){
      dp[i][j][0]=0ll;
      dp[i][j][1]=0ll;
    }
  }
  dp[0][0][0]=1ll;
  rep(i,K.size()){
    int x=K[i]-'0';
    rep(j,D){
      rep(k,10){
        if(j+k<D){dp[i+1][j+k][1]+=dp[i][j][1];dp[i+1][j+k][1]%=MOD;}
        else{dp[i+1][(j+k)%D][1]+=dp[i][j][1];dp[i+1][(j+k)%D][1]%=MOD;}
      }
      rep(k,x){
        if(j+k<D){dp[i+1][j+k][1]+=dp[i][j][0];dp[i+1][j+k][1]%=MOD;}
        else{dp[i+1][(j+k)%D][1]+=dp[i][j][0];dp[i+1][(j+k)%D][1]%=MOD;}
      }
        if(j+x<D){dp[i+1][j+x][0]+=dp[i][j][0];dp[i+1][j+x][0]%=MOD;}
        else{dp[i+1][(j+x)%D][0]+=dp[i][j][0];dp[i+1][(j+x)%D][0]%=MOD;}
    }
  }
  ll ans=dp[K.size()][0][0]+dp[K.size()][0][1]-1ll;
  ans%=MOD;
  ans+=MOD;
  ans%=MOD;
   cout<<ans;
}

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

using namespace std;

using ll = long long;

#define ALL(A) A.begin(),A.end()

class Node
{
    public:
    int number;
    set<int> next;
    int milestone = 0;
    bool seen = false;
};

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

    Node nodes[N];
    for(int i=0;i<N;i++)
    {
        nodes[i].number = i+1;
    }
    for(int i=0;i<M;i++)
    {
        int A,B;
        cin >> A >> B;
        A--;B--;

        nodes[A].next.insert(B);
        nodes[B].next.insert(A);
    }

    queue<Node> BFS;
    BFS.push(nodes[0]);

    while(!BFS.empty())
    {
        for(auto x : BFS.front().next)
        {
            if(!nodes[x].seen)
            {
                nodes[x].seen = true;
                nodes[x].milestone = BFS.front().number;
                BFS.push(nodes[x]);
            }
        }
        BFS.pop();
    }


    cout << "Yes" << endl;
    for(int i=1;i<N;i++)
    {
        cout << nodes[i].milestone << endl;
    }

    return 0;
}

Measured memory_bytes: 53608
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (n + 1)
for i in range(n):
    cnt[a[i]] += 1
conb1, conb2 = [], []
for i in range(n + 1):
    conb1.append(cnt[i] * (cnt[i] - 1) // 2)
    if cnt[i] == 0:
        conb2.append(0)
    else:
        conb2.append((cnt[i] - 2) * (cnt[i] - 1) // 2)
sumall = sum(conb1)
for i in range(n):
    ans = sumall - conb1[a[i]] + conb2[a[i]]
    print(ans)

Measured memory_bytes: 26140