akhauriyash/Code-Regression huggingface dataset:
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int s = Integer.parseInt(scanner.nextLine());

		HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();

		int preVal = 0;

		for (int i = 0; i < 1000000; i++) {
			if (i == 0) {
				map.put(s, true);
				preVal = s;

				continue;
			}

			int val = f(preVal);
			if (map.get(val) != null) {
				System.out.println(i + 1);
				return;
			} else {
				map.put(val, true);
				preVal = val;
			}
		}

	}

	private static int f(int n) {
		if (n % 2 == 0) {
			return n / 2;
		} else {
			return 3 * n + 1;
		}
	}

}


Measured memory_bytes: 23636
fun main(args: Array<String>) {
        val s = readLine()!!.toString()
        
        if (s != s.reversed()) {
            println("No")
            return
        }

        val a = s.substring(0, (s.length - 1) / 2)
        if (a != a.reversed()) {
            println("No")
            return
        }

        val b = s.substring(((s.length + 3) / 2) - 1, s.length)
        if (b != b.reversed()) {
            println("No")
            return
        }

        println("Yes")
    }


Measured memory_bytes: 33844
#include<bits/stdc++.h>
using namespace std;
int a,b;
bool c[110][110];
int h = 100,w = 100;
int main(){
	scanf("%d%d",&a,&b);
	int i,j,k;
	for(i = 1;i <= 50;++i) {
		for(j = 1;j <= 100;++j) c[i][j] = 1;
	}
	--a;
	--b;
	bool fg = 1;
	if(!a) fg = 0;
	for(i = 1;i <= 50;i += 2){
		for(j = 1;j <= 100;j += 2){
			if(!fg) break;
			c[i][j] = 0;
			--a;
			if(!a) fg = 0;
		}
		if(!fg) break;
	}
	fg = 1;
	if(!b) fg = 0;
	for(i = 52;i <= 100;i += 2){
		for(j = 1;j <= 100;j += 2){
			if(!fg) break;
			c[i][j] = 1;
			--b;
			if(!b) fg = 0;
		}
		if(!fg) break;
	}
	cout<<h<<" "<<w<<endl;
	for(i = 1;i <= h;++i){
		for(j = 1;j <= w;++j) putchar(c[i][j] ? '#' : '.');putchar('\n');
	}
	return 0;
} 

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

using ll = long long;

constexpr ll mod = 1e9+7;

void dfs(int v, vector<bool>& used, vector<vector<int>> const& g) {
    used[v] = true;
    for(auto to : g[v]) {
        if(!used[to]) {
            dfs(to, used, g);
        }
    }
}

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        vector<vector<int>> g(N);
        for(int i=0; i<M; ++i) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        int cnt = 0;
        vector<bool> used(N);
        for(int i=0; i<N; ++i) {
            if(!used[i]) {
                cnt++;
                dfs(i, used, g);
            }
        }
        ll res = 1;
        while(cnt-- > 0) {
            (res *= 2) %= mod;
        }
        cout << res + (M != 0) << endl;
    }
}


Measured memory_bytes: 9232
N, K = map(int, input().split())
ans = 0
lis = [0]*K
mod = 10**9 + 7

def modpow(a, n, mod):
    ans = 1
    while n > 0:
        if n&1:
            ans = ans * a % mod
        a = a * a % mod
        n = n >> 1
    return ans
for x in range(K,0, -1):
    a = int((K // x) % mod)
    b = modpow(a, N, mod)
    for i in range(2, K//x +1):
        b = (b - lis[x*i-1]) %mod
        if b < 0:
            b += mod
    lis[x-1] = b
    ans = (ans + b*x%mod) % mod
print(int(ans))


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

int main(void)
{
	int f1, n, p, cnt;
	unsigned int k, sum, max;
	deque<int> J;

	while(cin >> n && n > 0)
	{	
		sum = 0;
		cnt = 1;
		for(f1 = 0; f1 < n; f1++)
		{
			cin >> p;
			sum += p;
		}
		for(f1 = 0; f1 < n-1; f1++)
		{
			cin >> p;
			sum += p;
			J.push_back(p);
		}

		max = sum;
		sort(J.begin(), J.end()); //平均O(nlogn)
		deque<int>::iterator t = J.begin();

		while(t != J.end())
		{
			sum -= *t;
			k = ++cnt * sum;
			
			if(k > max)
				max = k;
			t++;
		}
		J.clear();
		cout << max << endl;
	}

	return 0;
}

Measured memory_bytes: 1488
import collections

def main():
    n = int(input())
    p = [input() for i in range(n)]

    c = collections.Counter(p)
    m = c.most_common()
    most = m[0][1]

    answer = []

    answer.append(m[0][0])

    for i in range(len(m)-1):
        if m[i+1][1] == most:
            answer.append(m[i+1][0])
        else:
            break

    for output in sorted(answer):
        print(output)
    return


main()

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

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll =V<pll>;
using vst = V<str>;
using vch = V<char>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define ci(a) cin>>a
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define INF 1e16
#define mod 1e9+7


int main() {
  ll n,m;
  cin>>n>>m;
  vll v(m);
  vll ve(m);
  FOR(i,0,m){
    cin>>v[i]>>ve[i];
  }
  SORT(v);
  SORT(ve);
  ll ans;
  ans=ve[0]-v[m-1]+1;
  if(ans<0)ans=0;
  co(ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ll;
const int Mod = 1e9+7;

ll modexp(ll a, ll b, int mod)
{
    long long res=1;
    while(b>0)
    {
        if(b&1)
            res=res*a%mod;
        b=b>>1;
        a=a*a%mod;
    }
    return res;
}

int32_t main(){
    int x, y;
    cin>>x>>y;
    int cnt = (x+y)/3;
    if(x==0 && y==0){
        cout<<1;
        return 0;
    }
    if((x+y)%3 || x==0 || y==0){
        cout<<0;
        return 0;
    }
    int Y = y-cnt;
    int X = cnt-Y;
    Y = max(X, Y);
    int ans = 1;
    for(int i = cnt; i >= cnt-Y+1; i--){
        ans *= i;
        ans %= Mod;
    }
    int s = 1;
    for(int i = 1; i <= Y; i++){
        s*=i;
        s%=Mod;
    }
    cout<<(ans%Mod * modexp(s, Mod-2, Mod) % Mod)%Mod;
    return 0;
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
input=input.trim();
input=input.toLowerCase();
var abc='abcdefghijklmnopqrstuvwxyz'.split("");
var obj={};
for(var i=0;i<abc.length;i++)obj[abc[i]]=0;

input=input.replace(/[a-z]/g,function(str){
obj[str]++;
return str;
});

abc.forEach(function(v,i){
console.log(v+" : "+obj[v]);
});

Measured memory_bytes: 8436
##through permutations and combinations we can reduce ans to
##  Summation N-1CK(m-1)^(N-1-K)


import sys
sys.setrecursionlimit(100000000)
DP={}
mod=998244353
product={}
N = 1000001
  
# array to store inverse of 1 to N 
factorialNumInverse = [None] * (N + 1) 
  
# array to precompute inverse of 1! to N! 
naturalNumInverse = [None] * (N + 1) 
  
# array to store factorial of  
# first N numbers 
fact = [None] * (N + 1) 
  
# Function to precompute inverse of numbers 
def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] * 
                                   (p - int(p / i)) % p) 
  
# Function to precompute inverse  
# of factorials 
def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1
  
    # precompute inverse of natural numbers 
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                                  factorialNumInverse[i - 1]) % p 
  
# Function to calculate factorial of 1 to N 
def factorial(p): 
    fact[0] = 1
  
    # precompute factorials 
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 
  
# Function to return nCr % p in O(1) time 
def Binomial(N, R, p): 
      
    # n C r = n!*inverse(r!)*inverse((n-r)!) 
    ans = ((fact[N] * factorialNumInverse[R])% p * 
                      factorialNumInverse[N - R])% p 
    return ans 
def getproduct(M,n):
    #product=(M-1)^n
    global mod,product
    fact=1000
    if n-1 in product:
        product[n]=(M*product[n-1])%mod
        return (M*product[n-1])%mod
    if n<fact:
        return (M**n)%mod
    else:
        Q=int(n/fact)
        R=n%fact
        prev=1
        for q in range(Q):
            prev=(prev*((M**fact)%mod))%mod
        prev=prev*((M**R)%mod)
        product[n]=prev%mod
        return prev%mod
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 
  
def G(N,M,K):
    global mod
    res=0
    for k in range(K,-1,-1):
        res=(res+((Binomial(N-1,k,mod))%mod *(M*getproduct(M-1,N-k-1))%mod)%mod)%mod
    return res%mod

def F(curr,N,M,K):
    global DP
    if(curr,K) in DP:
        return DP[(curr,K)]
    if curr==N:
        return 1
    if curr==0:
        return M*F(curr+1,N,M,K)
    else:
        a=0
        if K>0:
            a=F(curr+1,N,M,K-1)
        b=(M-1)*F(curr+1,N,M,K)
        DP[(curr,K)]=a+b
        return a+b
N,M,K=map(int,input().strip().split())
InverseofNumber(mod) 
InverseofFactorial(mod) 
factorial(mod) 
#print(F(0,N,M,K)%mod)
print(G(N,M,K))

Measured memory_bytes: 77848
#include <stdio.h>
struct card{
  char mark;
  char  num;
};
void bubble (struct card [],int );
void  selection( struct card [] , int);
int judge (struct card [],struct card [],int );
void print (struct card [],int);

int main()
{
  struct card A[100],B[100];
  int n,i;
  
  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf(" %c",&A[i].mark);
      scanf("%c",&A[i].num);
      
    }
  for(i= 0; i<n; i++)
    {
     
      B[i]=A[i];
    }
  
  bubble(A,n);
  selection(B,n);
  print(A,n); 
  printf("\n");     
  printf("Stable\n");
  print(B,n);
  if(judge(A,B,n) )
    {
      printf("\n");
      printf("Stable\n");
    }
  else{
    printf("\n");
    printf("Not stable\n");
  }
  
  return 0;
}

void bubble (struct card A[],int n )
{
  int i,j;
  struct card tmp;
  for(i=0;i<n;i++)
    {
      for(j=n-1;j>=i+1;j--)
	{
	  if(A[j].num < A[j-1].num ){
	    tmp=A[j];
	    A[j]=A[j-1];
	    A[j-1]=tmp;
	  }
	}
    }
}

void  selection(struct card B[], int n){
  int i,j,minj;
  struct card tmp;
  for(i=0;i<n;i++)
    {
      minj=i;
      for(j=i;j<n;j++)
	{
	  if(B[j].num < B[minj].num) minj=j;
	}
      tmp =B[minj];
      B[minj] =B[i];
      B[i] =tmp;
    }
}
int judge (struct card A[],struct card B[],int n )
{
  int i,flag =1;
  for(i=0;i<n;i++)
    {
      if(A[i].mark !=B[i].mark || A[i].num != B[i].num) flag =0;

    }
  return  flag;
}
void print (struct card A[] ,int n){
  int i;
  for(i=0;i<n;i++)
    {
      if(i!=0)printf(" ");
      printf("%c%c",A[i].mark,A[i].num);
    }
}



Measured memory_bytes: 2124
#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

int main(){
	int h, w, q; cin >> h >> w >> q; std::vector<std::string> s(h);
	std::vector<std::vector<int>> A(h + 1, std::vector<int>(w + 1, 0));
	std::vector<std::vector<int>> B = A, C = B;
	for(int i = 0; i < h; i++){
		cin >> s[i];
		
		for(int j = 0; j < w; j++) A[i + 1][j + 1] = (s[i][j] == '1');
	}
	
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(j + 1 < w) B[i + 1][j + 1] = (s[i][j] == '1' and s[i][j + 1] == '1');
			if(i + 1 < h) C[i + 1][j + 1] = (s[i][j] == '1' and s[i + 1][j] == '1');
		}
	}
	
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
			B[i][j] += B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1];
			C[i][j] += C[i - 1][j] + C[i][j - 1] - C[i - 1][j - 1];
		}
	}
	
	for(int i = 0; i < q; i++){
		int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;
		sx--; sy--; gx--; gy--;
		
		int ret = A[gx + 1][gy + 1] - A[gx + 1][sy] - A[sx][gy + 1] + A[sx][sy];
			ret -= B[gx + 1][gy] - B[gx + 1][sy] - B[sx][gy] + B[sx][sy];
			ret -= C[gx][gy + 1] - C[gx][sy] - C[sx][gy + 1] + C[sx][sy];
	
		cout << ret << endl;
	}
	return 0;
}


Measured memory_bytes: 52992
M = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}

try:
    while 1:
        l = input()

        stock = []
        res = 0
        for v in l:
            if len(stock) == 0 or stock[-1] >= M[v]:
                stock.append(M[v])
            else:
                stock[-1] = M[v] - stock[-1]
                res += sum(stock)
                stock = []

        res += sum(stock)

        print(res)
except:
    pass

Measured memory_bytes: 7352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class Program
	{
		//static int[] parent;
		static void Main(string[] args)
		{
			int[] input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			int N = input[0];
			int M = input[1];
			input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			List<int> cards = new List<int>(input);
			cards.Sort(); // 昇順に並び替え

			// カードの書き換え方法読み込み→書き換え後の数字が大きい順に並び替える
			Dictionary<int, int> bc = new Dictionary<int,int>();
			List<int> keys = new List<int>();
			for(int i=0; i<M; i++ )
			{
				input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
				if(bc.ContainsKey(input[1]))
				{
					bc[input[1]] += input[0];
				}
				else
				{
					bc.Add(input[1], input[0]);
					keys.Add(input[1]);
				}
			}
			keys.Sort((a,b)=>b-a); //降順に並び替え

			long sum = 0;
			int j = 0;
			for(int i=0; i<keys.Count; i++)
			{
				// カードの書き換え
				int C = keys[i]; /// 書き換え後の数
				int B = bc[C]; // 書き換えられる枚数

				for(int k=0; j<N && k<B; j++, k++)
				{
					if(cards[j] < C)
					{
						// 書き換える
						sum += (long)C;
					}
					else
					{
						break;
					}
				}
			}

			// 残りの書き換えなかったカードの数字を合計する
			for(int i=j; i<N; i++)
			{
				sum += (long)cards[i];
			}

			Console.WriteLine(sum + "") ;
		}
	}
}


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

#define int long long

signed main() {
  int m, l, r;
  while ( cin >> m >> l >> r, m ) {
    l--; r--;
    vector<int> P(m);
    for ( int i = 0; i < m; i++ ) cin >> P[i];
    int ans = 0;
    int gap = 0;
    for ( int i = l; i <= r; i++ ) {
      if ( P[i]-P[i+1] >= gap ) {
	ans = i;
	gap = P[i]-P[i+1];
      }
    }

    cout << ans+1 << endl;
  }

  return 0;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
using i64 = long long;

i64 gcd(i64 a, i64 b) { return b ? gcd(b, a % b) : a; }

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &el : a) std::cin >> el;
    std::deque<int> pre { 0 }, suf { 0 };
    for (int i = 0; i < n; i++) {
        pre.push_back(gcd(pre.back(), a[i]));
        suf.push_front(gcd(suf.front(), a[n - 1 - i]));
    }
    i64 ret = std::max(suf[1], pre[n - 1]);
    for (int i = 1; i < n - 1; i++) {
        ret = std::max(ret, gcd(pre[i], suf[i + 1]));
    }
    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        private const int MODULO = 1000000007;
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, string S)
        {
            int[] w = new int[N];
            int[] e = new int[N];
            for (int i = 1; i < N; ++i)
            {
                int j = N - 1 - i;
                w[i] = (S[i - 1] == 'W') ? w[i - 1] + 1 : w[i - 1];
                e[j] = (S[j + 1] == 'E') ? e[j + 1] + 1 : e[j + 1];
            }
            return Enumerable.Range(0, N).Min(i => w[i] + e[i]);
        }
        static void Main(string[] args)
        {
            int N = ReadInt();
            string S = Read();
            Console.WriteLine(Solve(N, S));
        }
    }
}


Measured memory_bytes: 14560
n, m = map(int, raw_input().split(' '))

x = [0 for i in range(n)]
y = [0 for i in range(n)]
z = [0 for i in range(n)]

for i in range(n):
	x[i], y[i], z[i] = map(int, raw_input().split(' '))

max_v = 0

for __counter_a in range(2):
	for __counter_b in range(2):
		for __counter_c in range(2):
			v = [0 for i in range(n)]
			for i in range(n):
				v[i] = x[i] + y[i] + z[i]
			v.sort(reverse=True)

			curr_v_sum = 0
			for i in range(m):
				curr_v_sum += v[i]

			max_v = max(max_v, curr_v_sum)
			
			for i in range(n):
				z[i] *= -1

		for i in range(n):
			y[i] *= -1

	for i in range(n):
		x[i] *= -1;

print max_v

Measured memory_bytes: 2940
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
use utils::*;


pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = CpReader::new(i);
    let n = i.read::<usize>();
    let a = i.read_vec::<isize>(n);
    writeln!(o, "{}", solve(&a)).unwrap();
}
fn solve(a: &[isize]) -> isize {
    let mut abs_sum = 0;
    let mut abs_min = isize::max_value();
    let mut negative_count = 0;
    for &a in a {
        let abs = if a < 0 {
            negative_count += 1;
            -a
        } else {
            a
        };
        abs_sum += abs;
        abs_min = min(abs_min, abs);
    }

    if negative_count % 2 != 0 {
        abs_sum -= abs_min * 2;
    }
    abs_sum
}

mod utils {
    use super::*;

    pub struct CpReader<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        { $f:ident($($t:ident),*) } => {
            #[allow(dead_code)]
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                ($(read_next::<$t,_>(i)),*)
            }
        };
    }

    impl<R: BufRead> CpReader<R> {
        pub fn new(r: R) -> Self {
            CpReader {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        pub fn read<T: FromStr>(&mut self) -> T {
            self.read_line().parse().ok().unwrap()
        }
        fn_read! { read2(T1, T2) }
        fn_read! { read3(T1, T2, T3) }
        fn_read! { read4(T1, T2, T3, T4) }
        fn_read! { read5(T1, T2, T3, T4, T5) }

        pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            self.read_line()
                .split(' ')
                .take(n)
                .map(|x| x.parse().ok().unwrap())
                .collect()
        }
    }
    fn read_next<'a, T: FromStr, I: Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }

}


Measured memory_bytes: 8444
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(int, N, K);
    vector<pair<int, int>> sushi(N);
    rep(i, 0, N) {
        var(int, t, d);
        --t;
        sushi[i] = {d, t};
    }

    sort(all(sushi), greater<>());

    i64 ans = 0;
    vector<int> cnt(N);
    i64 sum = 0;

    auto itr = sushi.begin();
    rep(i, 0, K) {
        ++cnt[itr->second];
        sum += itr->first;
        ++itr;
    }

    i64 t = count_if(all(cnt), [](auto n) { return n > 0; });
    chmax(ans, sum + t * t);

    dump(sushi);

    auto d = itr - 1;
    for (; itr != sushi.end(); ++itr) {
        if (t >= K) break;
        if (cnt[itr->second]) continue;
        for (; cnt[d->second] == 1; --d)
            ;
        dump(*itr, *d, t, sum, ans);
        --cnt[d->second];
        sum -= d->first;
        ++cnt[itr->second];
        sum += itr->first;
        ++t;
        --d;

        chmax(ans, sum + t * t);
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;
using namespace std;

int main(){
    string s;
    ll k;
    cin >> s >> k;
    int ans;
    rep(i, s.size()){
        ans = s[i] - '0';
        if(s[i] != '1' || i == k - 1){
            break;
        }
    }

    cout << ans << endl;


    return 0;
}


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

#define int long long
#define endl '\n'

int get(int n) {
    int bits = __builtin_popcount(n);
    if (bits == 0)
        return 0;
    return 1 + get(n % bits);
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n; cin >> n;
    string s; cin >> s;
    vector<int> p2(n + 1, 1), p3(n + 1, 1);
    int m1 = count(s.begin(), s.end(), '1'), m2 = m1 + 1, m3 = m1 - 1;
    for (int i = 1; i <= n; i++) {
        p2[i] = p2[i - 1] * 2 % m2;
        if (m3 != 0)
            p3[i] = p3[i - 1] * 2 % m3;
    }
    int in2 = 0, in3 = 0;
    for (auto &i: s) {
        i -= '0';
        in2 = in2 * 2 + i;
        in3 = in3 * 2 + i;
        in2 %= m2; 
        if (m3 != 0)
            in3 %= m3;
        else
            in3 = 0;
    }
    for (int i = 0; i < n; i++) {
        if (s[i]) {
            int temp = (in3 - p3[n - i - 1] + m3) % m3;
            cout << (m1 == 1 ? 0 : 1 + get(temp)) << endl;
        } else {
            int temp = (in2 + p2[n - i - 1]) % m2;
            cout << 1 + get(temp) << endl;
        }
    }
}           


Measured memory_bytes: 6744
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 2000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

inline int k(int x)
{
	int cnt=0;
	while(x) {cnt+=x%10; x/=10;} return cnt;
}

int main()
{
	int n,ans=inf; cin>>n; rep(i,1,n-1) ans=min(ans,k(i)+k(n-i)); cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3612
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        List<Character> slist = new ArrayList<Character>();
        for(char c:s.toCharArray())slist.add(c);
        Collections.sort(slist);
        StringBuffer as = new StringBuffer();
        for(char c:slist)as.append(c);
        String t = sc.next();
        List<Character> tlist = new ArrayList<Character>();
        for(char c:t.toCharArray())tlist.add(c);
        Collections.sort(tlist,Comparator.reverseOrder());
        StringBuffer at = new StringBuffer();
        for(char c:tlist)at.append(c);
        System.err.println(as);
        System.err.println(at);
        System.out.println(as.toString().compareTo(at.toString())<0?"Yes":"No");
    }

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 21844
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
if n%2==0:
    print(n*(n-2)//2)
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                print("{} {}".format(i,j))
if n%2==1:
    print((n-1)*(n-1)//2)
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                print("{} {}".format(i,j))


Measured memory_bytes: 43096
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef long long ll;
typedef pair<ll,ll> PP;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

signed main(void){
    int K,A,B;
    cin >> K >> A >> B;
    int now = (A/K)*K;
    while(1){
        if(A<=now){
            if(now<=B){
                cout << "OK" << endl;
            }else{
                cout << "NG" << endl;
            }
            break;
        }
        
        now+=K;
    }
    
    return 0;
}




Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main (void)
{
    int a, b;

    cin >> a >> b;
    if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
n=int(input())
slist=[]
for i in range(n):
    slist.append(input())

slist=sorted(slist)
if n==1:
    print(1)
else:
    answer=1
    for sl in range(len(slist)-1):
        if slist[sl]!=slist[sl+1]:
            answer+=1
    print(answer)

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

void solve(int TestCase) {
    int n;
    cin >> n;
    
    cout << fixed;
    cout.precision(15);
    double x = (double) n / 3;
    auto ret = x * x * x;
    cout << ret << endl;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    //cin >> t;
    for(auto i = 1; i <= t; ++i) {
        //cout << "Case #"<< i << ": ";
        solve(i);
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  
  int i;
  int n;
  long long a[100000];
  long long ans = 1;
  
  scanf("%d",&n);
  
  for(i = 0; i < n; i++){
    scanf("%lld",&a[i]);
    if(a[i] == 0){
      printf("0\n");
      return 0;
    }
  }
  
  for(i = 0; i < n; i++){
      
    //printf("a = %lld ans = %lld\n",a[i] ,ans);
    if(a[i] <= 1000000000000000000/ans){
      ans *= a[i];
    }else{
      printf("-1\n");
      return 0;
    }
    
  }
    
  printf("%lld\n",ans);
    
  return 0;
        
}

Measured memory_bytes: 2516
S = int(input())

# (X1, Y1) は原点
# (X2, Y2) = (10 ** 9, 1)
# S = 10 ** 9 * Y3 - X3

Y3 = (S + 10 ** 9 - 1) // (10 ** 9)
X3 = Y3 * (10 ** 9) - S

print(0, 0, 10 ** 9, 1, X3, Y3)

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

alphabet = [chr(97+i) for i in range(min(N,26))]
# print(alphabet)

dp = [[None]*N for _ in range(N)]
dp[0][0] = [alphabet[0]]
for i in range(1,N):
	dp[0][i] = []
# print(dp)


for n in range(1,N):
	for k in range(N):
		# dp[n][k] = dp[n-1][k]*k + dp[n-1][k-1]
		dp[n][k] = []
		for s in dp[n-1][k]:
			# print([s + alphabet[i] for i in range(k+1)])
			dp[n][k] += [s + alphabet[i] for i in range(k+1)]
		for s in dp[n-1][k-1]:
			dp[n][k] += [s + alphabet[k]]

# print(dp)
ans = []
for k in range(N):
	ans += dp[N-1][k]
ans = sorted(ans)

for s in ans:
	if len(s)!=0:
		print(s)
		

Measured memory_bytes: 15532
#include <stdio.h>

int	main(void)
{
  	long long	n;
  	long long	k;
  	int num;
  	long long	t;
  
  
  	num = scanf("%lld %lld", &n, &k);
  	if (num != 2)
      	return (0);
  
  	t = n % k;
  	if (t < k - t)
    {
      	printf("%lld", t);
    }
  	else
      	printf("%lld", k - t);
  	return (0);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define gr vector<vpii>
#define str string
#define mask vector<bool>
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define GAME_OVER return 0
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vi a(n);
    for (int& i : a)
        cin >> i;
    sort(rall(a));
    int s = accumulate(all(a), 0), cnt = 0;
    ld d = s / (4. * m);
    for (int i = 0; i < n; i++)
        cnt += ((ld)a[i] >= d);
    if (cnt >= m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    GAME_OVER;
}

Measured memory_bytes: 256
def solve():
    N = int(input())
    W = list(map(int,input().split()))
    S = sum(W)
    a = 0
    inf = 1 << 60
    ans = inf
    for i in range(N):
        a += W[i]
        ans = min(ans, abs(a - (S - a)))

    print(ans)

solve()


Measured memory_bytes: 3060
#include <stdio.h>
 
int
main (
  int   argc,
  char *argv[ ]
  )
{
  for ( ; ; )
  {
    int  a, b;
    char op;
 
    scanf ( "%d %c %d", &a, &op, &b );
    if ( op == '?' ) break ;
 
    switch ( op )
    {
      case '+': printf ( "%d\n", a + b ); break ;
      case '-': printf ( "%d\n", a - b ); break ;
      case '*': printf ( "%d\n", a * b ); break ;
      case '/': printf ( "%d\n", a / b ); break ;
    }
  }
 
  return ( 0 );
}

Measured memory_bytes: 600
from collections import Counter

N = int(input())
S = input()
MOD = 10**9 + 7

cnt = Counter(S)

slist = "abcdefghijklmnopqrstuvwxyz"
ans = 1
for s in slist:
    ans *= cnt[s] + 1

ans -= 1

ans = ans % MOD

print(ans)

Measured memory_bytes: 3444
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

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

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

#define MP make_pair
#define MT make_tuple
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()

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

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

	int N;
	cin >> N;

	VI A(N);
	map<int, int> M;
	REP(i, N){
		cin >> A[i];
		M[A[i]] = i;
	}

	SORT(A);
	int ret = 0;
	REP(i, N){
		if(i % 2 != M[A[i]] % 2) ret++;
	}

	cout << (ret + 1) / 2 << endl;

	return 0;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  vector<int> A(N);
  int least = INF, most = -INF;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
    least = min(least, A[i]);
    most = max(most, A[i]);
  }
  int ans = INF;
  for (int i = least; i <= most; ++i) {
    int sum = 0;
    for (int j = 0; j < N; ++j) {
      sum += (A[j] - i) * (A[j] - i);
    }
    ans = min(ans, sum);
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using p = pair<int, int>;
 
int main() {
  int n;
  cin >> n;
  map<string, int> mp;
  rep(i, n) {
    string s;
    cin >> s;
    mp[s]++;
  }
  
  int mx = 0;
  for (auto p: mp) mx = max(mx, p.second);
  for (auto p: mp) {
    if (p.second != mx) continue;
    cout << p.first << endl;
  }
  return 0;
}


Measured memory_bytes: 25216
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=input.split("\n");
Arr.shift();
var shcd="SHCD".split("");
var str="";
for(var i=0;i<4;i++){
    for(var j=1;j<=13;j++){
        var card=shcd[i]+" "+j;
        if(Arr.indexOf(card)===-1)str+=card+"\n";
    }
}
if(str!=="")console.log(str.trim());

Measured memory_bytes: 7644
#include <stdio.h>

#define mod 1000000007;

long long nikou(int n, int r);

long long c[2001][2001];
int done[2001][2001]={};

int main(void){
  int i, j;
  int n,k;
  long long b_wake;
  long long r_wake;
  long long ans;

  scanf("%d %d", &n,&k);

  for(i=1; i<=k; i++){
    ans=0;
    b_wake=0;
    r_wake=0;
    if(i==1){
      ans=(n-k+1)%mod;
    }else{
      if(k-i<0){
        ans=0;
      }else{
        //bの分け方 k-1Ci-1
        b_wake=nikou(k-1,i-1)%mod;
        //rの分け方
        for(j=i-1; j<=i+1; j++){
          //j=i-1 赤が両端にない
          //j=i 赤が右端のみまたは左端のみにある
          //j=i+1 赤が両端にある
          if(n-k<j) break;
          if(j==i){
            r_wake+=2*nikou(n-k-1,j-1)%mod
          }else{
            r_wake+=nikou(n-k-1,j-1)%mod;
          }
        }
        ans=(b_wake*r_wake)%mod;
      }
    }
    printf("%lld\n", ans);
  }

  return 0;
}

long long nikou(int n, int r){
  // printf("nikou(%d,%d)\n", n,r);
  if(done[n][r]==1) return c[n][r];

  if(n==0||r==0){
    done[n][r]=1;
    return c[n][r]=1;
  }
  if(r==n){
    done[n][r]=1;
    return c[n][r]=1;
  }

  c[n][r]=(nikou(n-1,r)+nikou(n-1,r-1))%mod;
  done[n][r]=1;
  return c[n][r];
}


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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pop pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define bb begin()
#define ee end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;





int arr[g_size];
char s[102][102];


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	//string s1,s2;

	//char s[100000];

	int ara[n_size],ara2[n_size];

    cin>>n>>m;



    f(i,1,n){
        f(j,1,m){
            cin>>s[i][j];
        }
    }

	f(i,0,m+1){
        s[0][i]='#';
        s[n+1][i]='#';
	}

	f(i,0,n+1){
        s[i][0]='#';
        s[i][m+1]='#';
	}

	f(i,0,n+1){
        f(j,0,m+1){
            cout<<s[i][j];
        }
        cout<<endl;
	}

}


Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

csum = [0]
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        csum.append(csum[-1]+1)
    else:
        csum.append(csum[-1])
for l, r in lr:
    print(csum[r-1]-csum[l-1])

Measured memory_bytes: 29764
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> v(m, 0);
    REP(i, n){
        int k;
        cin >> k;
        REP(j, k){
            int a;
            cin >> a;
            v[a-1]++;
        }
    }
    int ans = 0;
    REP(i, m){
        if(v[i] == n){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
using namespace std;

const int hell = 1e9+7;
int dp[1001][1001];

void add(int a,int& b){
	b += a;
	if(b >= hell) b = b%hell;
}

int main(){
	ios_base::sync_with_stdio(false);

	int n,m;
	cin >> n >> m;

	string grid[n];
	for(auto& i : grid) cin >> i;

	dp[0][0] = 1;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if( grid[i][j] == '#' ){
				dp[i][j] = 0;
				continue;
			}
			if(i > 0) add(dp[i-1][j],dp[i][j]);
			if(j > 0) add(dp[i][j-1],dp[i][j]);
		}
	}

	cout << dp[n-1][m-1] << endl ;

	return 0;
}


Measured memory_bytes: 8608
n, m = map(int, input().split())

max_left = 1
min_right = n

for i in range(m):
    left, right = map(int, input().split())
    max_left = max(max_left, left)
    min_right = min(min_right, right)

print(max(min_right - max_left + 1, 0))

Measured memory_bytes: 3060
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    if n == 1: return a[0]

    d = dict(zip(sorted(set(a)), range(len(a))))

    def check(num):
        a1 = [0]*(n+1)
        a2 = [0]*(n+1)
        for i, ai in enumerate(a):
            if ai < num:
                a1[i+1] = a1[i]+1
                a2[i+1] = a2[i]
            else:
                a1[i+1] = a1[i]
                a2[i+1] = a2[i]+1
        ad = [a2[i]-a1[i]+10**5+1 for i in xrange(n+1)]

        bit = BinaryIndexedTree(2*10**5+1)
        cnt = 0
        for i in xrange(n+1):
            cnt += bit.sum(ad[i])
            bit.add(ad[i], 1)
        # print num, cnt

        return n*(n+1)/2 - cnt <= cnt

    mi = 0
    ma = 10**9+1

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            mi = mid
        else:
            ma = mid

    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

    def sum(self, i):
        """sum 1 to i"""
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """add x to bit[i]"""
        while i <= self.size:
            self.bit[i] += x
            i += i & -i


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


Measured memory_bytes: 139508
def main():
    import sys
    import time
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    mod = N
    ans = 0
    c = 1
    while True:
        if N // mod == N % mod:
            ans += mod
            c += 1
            mod = N // c
            continue
        mod -= 1
        if not mod:
            break
        if N % mod > c:
            c += 1
            mod = N // c
            continue
        if N // mod == N // c:
            c += 1

    print(ans)

if __name__ == '__main__':
    main()

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  for(int i=1;i<=50000;++i) {
    if(i * 108 / 100 == n) {
      cout << i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
}


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

int main(){
	long long n;
	cin>>n;
	long long a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	long long p[n+1];
	for(int i=1;i<=n;i++){
		p[i]=0;
	}
	p[n]=a[n];
	long long s=0;
	for(int i=n-1;i>=1;i--){
		p[i]=p[i+1]+a[i];
		p[i]%=1000000007;
		s+=(p[i+1]*a[i])%1000000007;
		s%=1000000007;
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 6744
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, c) for(long long i=0; i<(long long)c; i++)
const ll INF=1000000000000001;
int main() {
	int n;
	int ans=0;
	cin >>n;
	if (n==0)ans=1;
	cout <<ans<<endl;
	return 0;
}


Measured memory_bytes: 3592
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k,c = LI()
s = input()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(1)
    else:
        t.append(0)

cnt = 0
i = n-1
d = defaultdict(int)
while i >= 0:
    if t[i] == 1:
        cnt += 1
        d[i] = 1
        i -= c+1
        continue
    i -= 1
i = 0
f = defaultdict(int)
while i < n:
    if t[i] == 1:
        f[i] = 1
        i += c+1
        continue
    i += 1
        
if cnt > k:
    print('')
    quit()

for i,j in sorted(f.items()):
    if j == 1 and d[i] == 1:
        print(i+1)


     



Measured memory_bytes: 81396
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
using P = pair<int,int>;
using ll = long long;
using namespace std;
int main(void){
    // Your code here!
    ll x; cin >> x;
    ll yokin = 100;
    
    rep(i, x){
        yokin += yokin / 100;
        if(yokin >= x){cout << i+1 << endl; return 0;}
    }
}


Measured memory_bytes: 3612
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<bool> > adj(n, vector<bool>(n, false));
    vector<int> v(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a][b] = adj[b][a] = true;
    }

    for (int i = 0; i < n; i++) { v[i] = i; }

    int ans = 0;
    do {
        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (!adj[v[i - 1]][v[i]]) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
    } while (next_permutation(++v.begin(), v.end()));

    cout << ans << endl;
}

Measured memory_bytes: 256