akhauriyash/Code-Regression huggingface dataset:
/*
    Created by Ezio112
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
//#define inf ll(10e16)
#define mod ll(10e8+7)
#define ff first
#define ss second
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    ll t;
    //cin>>t;
    t=1;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        vector<ll> vec(n+1);

        for(ll i=0;i<k;++i)
        {
            ll d,x;
            cin>>d;
            for(ll j=0;j<d;++j)
            {
                cin>>x;
                vec[x]=1;
            }
        }
        ll sum=0;
        for(ll i=1;i<=n;++i)
        if(vec[i]==0)
            ++sum;
        cout<<sum;
    }
    return 0;
}


Measured memory_bytes: 3640
from itertools import product
from math import ceil


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue

        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        tmp = ceil((g - sums) / indices[-1])
        if tmp < p[indices[-1] - 1]:
            ans = min(ans, counts + tmp)
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

struct Vector2D{
	double x;
	double y;
};

double gaiseki(Vector2D* a , Vector2D* b){
	return (a->x)*(b->y)-(a->y)*(b->x);
}

int main(){
	double xa,ya,xb,yb,xc,yc,xd,yd;
	char c;
	while(cin>>xa>>c>>ya>>c>>xb>>c>>yb>>c>>xc>>c>>yc>>c>>xd>>c>>yd){
		Vector2D ab ,ad , bc , ba , ca , cb , cd , ac , da , bd , dc , db;
		ab.x=xb-xa;
		ab.y=yb-ya;
		ad.x=xd-xa;
		ad.y=yd-ya;
		bc.x=xc-xb;
		bc.y=yc-yb;
		bd.x=xd-xb;
		bd.y=yd-yb;
		ba.x=xa-xb;
		ba.y=ya-yb;
		ca.x=xa-xc;
		ca.y=ya-yc;
		cb.x=xb-xc;
		cb.y=yb-yc;
		cd.x=xd-xc;
		cd.y=yd-yc;
		ac.x=xc-xa;
		ac.y=yc-ya;
		da.x=xa-xd;
		da.y=ya-yd;
		bd.x=xd-xb;
		bd.y=yd-yb;
		db.x=xb-xd;
		db.y=yb-yd;
		dc.x=xc-xd;
		dc.y=yc-yd;
		double abac , bdbc , dadc;
		double abad , bcbd , cacd;
		double bcba , cdca , dbda;
		double cdcb , dadb , acab;
		abac=gaiseki(&ab , &ac);
		bdbc=gaiseki(&bd , &bc);
		dadc=gaiseki(&da , &dc);
		abad=gaiseki(&ab , &ad);
		bcbd=gaiseki(&bc , &bd);
		cacd=gaiseki(&ca , &cd);
		bcba=gaiseki(&bc , &ba);
		cdca=gaiseki(&cd , &ca);
		dbda=gaiseki(&db , &da);
		cdcb=gaiseki(&cd , &cb);
		dadb=gaiseki(&da , &db);
		acab=gaiseki(&ac , &ab);
		if((abac<0 && bdbc<0 && dadc<0)||(abac>0 && bdbc>0 && dadc>0 )) cout << "NO" << endl;
		else if((abad<0 && bcbd<0 && cacd<0) || (abad>0 && bcbd>0 && cacd>0)) cout << "NO" << endl;
		else if((bcba<0 && cdca<0 && dbda<0) || (bcba>0 && cdca>0 && dbda>0)) cout << "NO" << endl;
		else if((cdcb<0 && dadb<0 && acab<0) || (cdcb>0 && dadb>0 && acab>0)) cout << "NO" << endl;
		else cout << "YES" << endl;
	}
	return 0; 
}

Measured memory_bytes: 1228
n=int(input())

score=[]
bsum=0

for _ in range(n):
    a,b=map(int,input().split())
    score.append(a+b)
    bsum-=b

score.sort(reverse=True)

for i,v in enumerate(score):
    if i%2==0:
        bsum+=v

print(bsum)

Measured memory_bytes: 80776
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;

typedef long long ll;


int main() {
	int n;
	cin >> n;
	
	vector<ll> sum(n + 1);

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

		sum[i + 1] = sum[i] + a;

		
		
	}

	
	ll min = 1000000000000000;
	ll sumAll = sum[n];

	
	for (int i = 1; i < n; i++) {
		ll dif = abs(sumAll - (2 * sum[i]));
		
		if (dif < min) {
			min = dif;
		}
	}
	
	cout << min << endl;
	

}

Measured memory_bytes: 1792
n=int(input())
a=list(map(int,input().strip().split()))[:n]
s=0;
b=[]
b.append(a[0])
for i in range(1,n):
  b.append(a[i]+b[i-1])
for i in range(0,n):
    s+=a[i]*(b[n-1]-b[i])
    s=s%1000000007
print(s)

Measured memory_bytes: 31664
#include<iostream>

using namespace std;
int main(){
  string a,b,c;
  cin >>a >>b >>c;
  if(a.back()==b.front() && b.back() == c.front()){
    cout << "YES" <<endl;
  }else{
    cout <<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int H,W;
    cin >> H >> W;

    vector<string> canvas(H);
    for (int i = 0; i < H; i++)
    {
        string s;
        cin >> s;
        canvas.at(i) = s;
    }
    
    vector<int> y = {-1,0,0,1};
    vector<int> x = {0,-1,1,0};
    int res = 1;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if(canvas.at(i).at(j)=='.'){
                continue;
            }else{
                int num = 0;
                for (int k = 0; k < 4; k++)
                {
                    int yy = i + y.at(k);
                    int xx = j + x.at(k);

                    if(yy<0||yy>=H){
                        continue;
                    }else if(xx<0||xx>=W){
                        continue;
                    }else{
                        if(canvas.at(yy).at(xx)=='#'){
                            num ++;
                        }
                    }
                }
                if(num == 0){
                    res = 0;
                }
            }
        }
        
    }
    if(res == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
from itertools import accumulate
import bisect

n, m, k = map(int, input().split())
A = [0] + list(accumulate(map(int, input().split())))
B = [0] + list(accumulate(map(int, input().split())))
ans = 0
for i, a in enumerate(A):
  if a > k:
    break
  temp = i + bisect.bisect_right(B, k-a)-1
  ans = max(ans, temp)
print(ans)

Measured memory_bytes: 119584
#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;
 
int main()
{
  long long W, H, x, y;
  cin >> W >> H >> x >> y;
  double S;
  S = (W * H) / 2.0;
  cout << fixed << setprecision(6) << S;
  cout << ' ';
  cout << ((x == (W / 2.0)) * (y == (H / 2.0)) * ((W % 2) == 0) * ((H % 2) == 0)) << endl;
}

Measured memory_bytes: 384
N = int(input())
s = [int(input()) for _ in range(N)]
s10 = [si for si in s if si % 10 != 0]
s10.sort()
result = sum(s)
if result % 10 != 0:
    print(result)
else:
    if len(s10) == 0:
        print(0)
    else:
        print(result - s10[0])




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

using namespace std;

int main() {
	int A, B, C, D, E;
	cin >> A >> B >> C >> D >> E;
	int N = 5;

	vector<int> tmp = { A,B,C,D,E };
	vector<int> now(N);

	for (int i = 0; i < N; i++) {
		if (tmp[i] % 10 == 0) {
			now[i] = tmp[i];
		}
		else {
			now[i] = tmp[i] - tmp[i] % 10 + 10;
		}
	}

	int ans = 99999999;

	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j < N; j++) {
			if (i == j) {
				sum += tmp[j];
			}
			else {
				sum += now[j];
			}
		}
		ans = min(ans, sum);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
// Aizu Vol-10 1060: No Story
// 2017.10.7 bal4u@uu

#include <stdio.h>
#include <math.h>

int power[100], sz;

int ptbl[] = {
         3,   5,   7,  11,  13,  17,  19,  23,  29,
   31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
   73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
  127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  947, 953, 967, 971, 977, 983, 991, 997, 0 };

void prime_factor(long long n)
{
    int i, b, sw;
    int *pp;

    sz = 0;
    if ((n & 1) == 0) {
        power[sz] = 0;
        do n >>= 1LL, power[sz]++;
        while ((n & 1) == 0);
        sz++;
    }
	if (n <= 1) return;
	for (pp = ptbl; n > 1 && *pp > 0; pp++) {
		if (n % *pp) continue;
		b = *pp, power[sz] = 0;
		do n /= b, power[sz]++;
	    while (n % b == 0);
		sz++;
	}
	if (n <= 1) return;
    b = (int)sqrt((double)n);
	for (i = 1009, sw = 0; n > 1; ) {
        if (i > b) { power[sz++] = 1; break; }
        if (n % i == 0) {
            power[sz] = 0;
            do n /= i, power[sz]++;
            while (n % i == 0);
            sz++;
        }
        if (sw) i += 2, sw = 0;
        else    i += 4, sw = 1;
    }
}

int main()
{
	long long n, ans;
	int i;

	while (scanf("%lld", &n) && n > 0) {
        prime_factor(n);
		for (ans = 1, i = 0; i < sz; i++) ans = ans * (1 + (power[i] << 1));
		ans = (ans + 1) / 2;
        printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1684
object Main extends App {
  val in = new StdinReader
  val N = in.nextInt
  val Ss = Array.fill(N)(in.next)
  val targets = Ss.groupBy(identity).mapValues(_.size)
  val max = targets.maxBy(_._2)._2
  println(targets.collect{case (s, `max`) => s}.toArray.sorted.mkString("\n"))
}

class StdinReader {
  val is = System.in
  val buffer = new Array[Byte](1024 * 1024)
  var size = 0
  var pos = 0

  private def readByte: Byte = {
    if (pos >= size) {
      pos = 0;
      size = is.read(buffer);
    }
    if (size < 0) -1
    else {
      val ret = buffer(pos)
      pos += 1
      ret
    }
  }

  // support single byte char only
  def next: String = {
    @scala.annotation.tailrec
    def r(sb: StringBuilder, reading: Boolean): String = {
      readByte match {
        case b if ('!' <= b && b <= '~') => r(sb.append(b.asInstanceOf[Char]), true)
        case _ => if (reading) sb.toString else r(sb, false)
      }
    }
    r(new StringBuilder, false)
  }

  def nextInt: Int = {
    @scala.annotation.tailrec
    def r(i: Int, reading: Boolean): Int = {
      readByte match {
        case '-' => r(i * -1, true)
        case b if '0' <= b && b <= '9' => r(i * 10 + (b - '0'), true)
        case _ => if (reading) i else r(i, false)
      }
    }
    r(0, false)
  }
}

Measured memory_bytes: 166296
#include<cstdio>
#include<iostream>
#include<string>
#include<list>
#include<iterator>
using namespace std;

int main(){
    string S;
    cin >> S;
    list<char> answer;
    for(const auto c : S) answer.push_back(c);
    unsigned Q;
    scanf("%u", &Q);
    unsigned manipulation;
    bool is_reversed = false;
    for (size_t i = 0; i < Q; i++){
        scanf("%u", &manipulation);
        if(manipulation == 1) is_reversed ^= true;
        else{
            unsigned f;
            char c;
            scanf("%u %c", &f, &c);
            if((f == 1)^is_reversed) answer.push_front(c);
            else answer.push_back(c);
        }
    }
    if(is_reversed){
        list<char>::const_reverse_iterator End = answer.rend();
        for (list<char>::const_reverse_iterator it = answer.rbegin(); it != End; it++){
            printf("%c", *it);
        }
    }else{
        list<char>::const_iterator End = answer.end();
        for (list<char>::const_iterator it = answer.begin(); it != End; it++){
            printf("%c", *it);
        }
    }
    printf("\n");
	return 0;
}

Measured memory_bytes: 9984
//
//  main.swift
//  Atcoder
//
//  Created by Louis Joe Shen on 2020/7/17.
//  Copyright © 2020 Louise Joe Shen. All rights reserved.
//

import Foundation

var input = readLine()!.split(separator: " ")

var H = Int(input[0])!
var W = Int(input[1])!
var A = Int(input[2])!
var B = Int(input[3])!

var MOD : Int = 1000000000 + 7
var fac = [Int]()
func exgcd(a : Int,b : Int) -> [Int]{
    var ans = [0,0,0]
    
    if b == 0{
        ans[0] = a
        ans[1] = 1
        ans[2] = 0
        return ans
    }
    let delta = exgcd(a: b, b: a % b)
    
    ans[0] = delta[0]
    ans[1] = delta[2]
    ans[2] = delta[1] - (a / b) * delta[2]
    
    return ans
}
   
func inv(a : Int) -> Int{
    let ans = exgcd(a: a, b: MOD)
    
    return (ans[1] % MOD + MOD) % MOD
}

func C(r : Int,k : Int) -> Int{
    return fac[r] % MOD * inv(a: fac[k]) % MOD * inv(a: fac[r - k]) % MOD
}

fac.append(1)
for i in 1 ... 200000 + 7{
    fac.append(i * fac[i - 1] % MOD)
}

var n = H - A
var ans = 0
for i in 1 ... n{
    ans += ((C(r: B + i - 2, k: i - 1) % MOD) * (C(r: W + H - B - i - 1, k: H - i) % MOD)) % MOD
    ans %= MOD
}

print(ans)


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

using namespace std;
typedef long long ll;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n; cin >> n;
  	vector<string> s(n);
  	map<string,int> m;
  	for (string &i : s) {
      	cin >> i; m[i]++;
    }
  	cout << "AC x " << m["AC"] << endl;
  	cout << "WA x " << m["WA"] << endl;
  	cout << "TLE x " << m["TLE"] << endl;
 	cout << "RE x " << m["RE"] << endl;
    return 0;
}


Measured memory_bytes: 6364
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb emplace_back
#define mp make_pair
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL))
int main()
{
    ll n;
    cin>>n;
    for(ll i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            if(i<10 && n/i<10)    return cout<<"Yes",0;
        }
    }
   cout<<"No";
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (in i = 0; i < (in)(n); i++)
#define REP(i,a,b) for(in i=(in)(a);i<(in)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const in inf=1e9+7;
using P=pair<in,in>;
vector<in> dx={0,1,-1,0};
vector<in> dy={1,0,0,-1};

//探索、更新にO(log n)
struct segment_tree{
    in init ; //　空いてる値はこれになる
    in n; //　n個のデータ
    vector<in> data; // データ置き場・n-1~2n-1に元データ

    //(個数、初期値)
    //初期化　nを2の累乗に直す  初期値は最も選ばれない値にする
    segment_tree(in a, in b) : init(b) {
        n = 1;
        while( n < a ) n *= 2;
        data.assign(n * 2 - 1,init);
    }

    //+とかにしてもいい、結合法則はいる
    //選ぶ方の決め方（ここでは小さい方）
    in which(in a, in b){
        // if(a > b) return b;
        // else return a;
        return a+b;
    }

    // k番目をaに更新
    void update(in k, in a){
        k += n-1;
        data[k] = a;

        //下から上に更新
        while( k > 0 ){
            k = (k - 1) / 2;
            data[k] = which( data[k*2+1] , data[k*2+2] );
        }
    }

    // [a, b)の最小値を求める
    // 後ろのほうの引数は、計算の簡単のための引数。
    // kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
    // したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
    in query( in a, in b, in k, in l, in r){

        // [a, b)と[l, r)が交差しなければ、MAX_in
        if(r <= a || b <= l) return init;

        // [a, b)が[l, r)を完全に含んでいれば、この節点の値
        if(a <= l && r <= b) return data[k];

        // そうでなければ、2つの子の最小値
        in vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        in vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return which( vl, vr );
    }

    // 外から呼ぶとき用
    // [a, b)の最小値を求める
    in query( in a, in b){
        return query( a, b, 0, 0, n);
    }

    // a番目のデータを見る
    // query(a,a+1)で良くね？
    in look(in a){
        return data[a+n-1];
    }
};

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    in n,q;
    cin>>n>>q;
    vector<in> a(n);
        rep(i,n) cin>>a.at(i);
    
    segment_tree sg(n,0);
    rep(i,n) sg.update(i,a[i]);
    in x,y,z;
    rep(i,q){
        cin>>x>>y>>z;
        if(x){
            cout<<sg.query(y,z)<<endl;
        }
        else{
            sg.update(y,sg.look(y)+z);
        }
    }
}/*
./problem.exe
*/

Measured memory_bytes: 16468
S = input()
if S == 'SUN':
  print(7)
if S == 'MON':
  print(6)
if S == 'TUE':
  print(5)
if S == 'WED':
  print(4)
if S == 'THU':
  print(3)
if S == 'FRI':
  print(2)
if S == 'SAT':
  print(1)
  

Measured memory_bytes: 3060
from sys import stdin
from collections import deque
q=deque()
K,N= list(map(int, (stdin.readline().strip().split())))
A=list(map(int, (stdin.readline().strip().split())))
max=A[1]-A[0]
home=0
home_B=0
place=0
kyori=0
for i in range(N-1):
    if max< A[i+1]-A[i]:
        max=A[i+1]-A[i]
        place=i
B=A[place]
C=A[place+1]-K
D=B-C
if A[-1]-A[0]>D:print(D)
else:print(A[-1]-A[0])

Measured memory_bytes: 25428
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#include<math.h>
#include<assert.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384
int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int nHr(int a,int b){return nCr(a+b-1,b);}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int dsum(int x){int r=0;while(x){r+=(x%10);x/=10;}return r;}
int dsumb(int x,int b){int r=0;while(x){r+=(x%b);x/=b;}return r;}
int sankaku(int x){return ((1+x)*x)/2;}
void swap(int *a,int *b){int c;c=(*a);(*a)=(*b);(*b)=c;}
//大きい順
int compareInt(const void* a, const void* b){int aNum = *(int*)a;int bNum = *(int*)b;return bNum - aNum;}

int main(void){
    int N;
    scanf("%d",&N);
    int vl[N];
    for(int i=0;i<N;i++){
        scanf("%d",&vl[i]);
    }
    qsort(vl,N,sizeof(int),compareInt);
    int sum=0;
    for(int i=1;i<N;i++){
        sum+=vl[i];
    }
    printf("%d",(vl[0]/2)+sum);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

vector<vector<int>>g;
vector<int> ans;
vector<int> dp,a;
const auto inf = numeric_limits<int>::max();

void dfs(int v,int p){
	auto y = lower_bound(all(dp), a[v]);
	int val = *y;
	*y = a[v];
	ans[v] = lower_bound(all(dp),inf)-dp.begin();
	for (auto x : g[v])
	{
		if (ans[x] == -1)
		{
			dfs(x, v);
		}
	}
	*y = val;
}

void solve()
{
  int n;
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];
  g.resize(n);
  ans.resize(n,-1);
  dp.resize(n, inf);
  rep(i, n - 1)
  {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      g[u].eb(v);
      g[v].eb(u);
  }
  dfs(0, -1);
	rep(i,n){
		cout << ans[i]<< "\n";
	}
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    solve();
    return 0;
}



Measured memory_bytes: 24996
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int t = sc.nextInt();

    int i = 1;
    
    int total = 0;
    while (i * a < t + 0.5) {
      total += b;
      i++;
    }
    
    System.out.println(total);
  }
}

Measured memory_bytes: 21460
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    uf = UnionFind(N)
    for q in range(Q):
        com, x, y = il()
        if com == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)


if __name__ == '__main__':
    main()



Measured memory_bytes: 14380
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
ans=sum(a)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    ans+=(c-b)*cnt[b]
    ##print(cnt)#Counter({1: 1, 2: 1, 3: 1, 4: 1})
    cnt[c]+=cnt[b]
    ##print(cnt)#Counter({2: 2, 1: 1, 3: 1, 4: 1})
    cnt[b]=0
    ##print(cnt)#Counter({2: 2, 3: 1, 4: 1, 1: 0})
    print(ans)


Measured memory_bytes: 24104
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return (a % 1000000007);
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}



int main(){
  ll k,a,b; cin >> k >> a >> b;
  
  if(a+2 >= b) cout << k+1 << endl;
  else if(k <= a) cout << k+1 << endl;
  
  else {
    if((k-a+1) % 2 == 0){
      cout << (k-a+1)/2 * (b-a) + a << endl;
    }
    else{
      cout << (k-a)/2 * (b-a) + a + 1 << endl;
    }
    
  }
  
}

Measured memory_bytes: 256
/*

 Remember, Hope is a good thing... May be the best of things... and No Good thing ever Dies !!!

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(0); cout.tie(0);
#define endl "\n"
#define MOD 1000000007
const ll inf=(1LL<<60)-1;
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
void solve()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ll a,b,sum=0;
    cin>>a>>b;
    if(a>=13)
        cout<<b<<endl;
    else if(6<=a && a<=12)
        cout<<b/2<<endl;
    else
        cout<<0<<endl;

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


Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

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


int main()
{
    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    int max_diff = K-A[N-1]+A[0];
    REP(i, N-1) max_diff = max(max_diff, A[i+1]-A[i]);
    cout << K-max_diff << endl;

    return 0;
}

Measured memory_bytes: 1024
n = int(input())
arr = [ list(input().split()) for i in range(n)]
ans = 0
for x, u in arr:
    if u == 'JPY':
        ans += int(x)
    else:
        integer, double = x.split('.')
        ans += int(integer) * 380000
        for j, num in enumerate(double, start=1):
            ans += (10 ** -j * int(num)) * 380000
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
#define co2(i,j) cout << i << " " << j << endl;
#define co3(i) cout << i << " ";
#define po(i) cout << i.first << " " << i.second << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod, digitDP, treeDP//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vpll flag, D; vll path;
//***********//
ll binarySearch(vl V, ll key) {
	ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	ll right = V.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は V.size()
	while (right - left > 1) {
		ll mid = left + (right - left) / 2;
		if (V[mid] >= key) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
int main() {
	cin >> N >> M >> K;
	vl A(N), B(M);
	vl sum(N+1);
	sum[0] = 0;
	for (i = 0; i < N; i++) {
		cin >> A[i];
		sum[i + 1] = sum[i] + A[i];
	}
	vl sum2(M + 1);
	sum2[0] = 0;
	for (i = 0; i < M; i++) {
		cin >> B[i];
		sum2[i + 1] = sum2[i] + B[i];
	}
	for (i = 0; i <= M; i++) {
		ll time = K-sum2[i];
		ll pre = i;
		if (time == 0) {
			ans = max(pre, ans);
		}
		else if (time > 0) {
			ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
			ll right = N+1; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は V.size()
			while (right > left+1) {
				ll mid = left + (right - left) / 2;
				if (sum[mid] <= time) left = mid;
				else right = mid;
				//debug(right,left,mid);
			}
			/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
			pre += left;
			//debug(left);
			ans = max(pre, ans);
		}
	}
	cout << ans;
}

Measured memory_bytes: 9596
x, y = map(int, input().split())
if x in [1, 3, 5, 7, 8, 10, 12] and y in [1, 3, 5, 7, 8, 10, 12]:
    print('Yes')
elif x in [4, 6, 9, 11] and y in [4, 6, 9, 11]:
    print('Yes')
elif x == y == 2:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int a1 = Integer.parseInt(sc.next());
        int a2 = Integer.parseInt(sc.next());
        int a3 = Integer.parseInt(sc.next());
        
        int min = Math.abs(a2-a1) + Math.abs(a3-a2);
        if(Math.abs(a3-a1) + Math.abs(a2-a3) < min){
            min = Math.abs(a3-a1) + Math.abs(a2-a3);
        }
        if(Math.abs(a1-a2) + Math.abs(a3-a1) < min){
            min = Math.abs(a1-a2) + Math.abs(a3-a1);
        }
        if(Math.abs(a3-a2) + Math.abs(a1-a3) < min){
            min = Math.abs(a3-a2) + Math.abs(a1-a3);
        }
        if(Math.abs(a1-a3) + Math.abs(a2-a1) < min){
            min = Math.abs(a1-a3) + Math.abs(a2-a1);
        }
        if(Math.abs(a2-a3) + Math.abs(a1-a2) < min){
            min = Math.abs(a2-a3) + Math.abs(a1-a2);
        }
        
        System.out.println(min);
    }
}

Measured memory_bytes: 21716
using System;
 
namespace practice
{
    class programpractice
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var A = int.Parse(Console.ReadLine());
          
          if(N%500<=A)
          {
             Console.WriteLine("Yes");
 
          }
            else
            {
              Console.WriteLine("No");
            }
 
           
        }
    }
}

Measured memory_bytes: 11092
#include<stdio.h>

int main(){
  char s[4];
  int a=0,b=0;
  int i;
  scanf("%s",s);

  for(i=0;i<3;i++){
    if(s[i]=='A')
      a++;
    else
      b++;
  }
  if(a>0 && b>0)
    printf("Yes");
  else
    printf("No");
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int a, b, c;
    cin>>a>>b>>c;
    if(a >= b + c || b >= a + c || c >= a + b){
        cout<<"No\n";
        return 0;
    }
    if(a == b && a == c){
        cout<<"Yes\n";
    }
    else cout<<"No\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
    string N; cin >> N;
    int sum = 0;
    for(int i=0; i < N.size(); i++){
        sum += N[i] - '0';
    }
    int temp = stoi(N);
    if(temp % sum == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}
        

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a[100004],n,k,q,b[100004];
    scanf("%d%d%d",&n,&k,&q);
    for(int i=1;i<=n;i++)
    {
        a[i]=k;
    }
    for(int i=0;i<q;i++)
    {
        int p;
        scanf("%d",&p);
       /* for(int j=1;j<=n;j++)
        {
            if(j!=p)
                a[j]--;
        }*/
        b[p]++;

    }
    for(int j=1;j<=n;j++)
    {
            a[j]=a[j]-(q-b[j]);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	vector<int>vec(3);
	rep(i, 3)cin >> vec[i];
	SORT(vec);
	int ans = vec[2] - vec[1];
	vec[0] += ans;
	ans += (vec[2] - vec[0]) / 2;
	if ((vec[2] - vec[0]) % 2 == 1)ans += 2;
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

int N, M;
vector< int > cg[1000], rg[1000], g[1000];
bool v[1000];
vector< int > order;
int cmp[1000];
bool connect[1000][1000];
bool in[1000];

void dfs(int idx)
{
  for(int to : cg[idx]) if(!v[to]++) dfs(to);
  order.push_back(idx);
}
void rdfs(int idx, int k)
{
  cmp[idx] = k;
  for(int to : rg[idx]) if(cmp[to] == -1) rdfs(to, k);
}
int scc()
{
  int k = 0;
  for(int i = 0; i < N; i++) if(!v[i]) dfs(i);
  memset(cmp, -1, sizeof(cmp));
  reverse(order.begin(), order.end());
  for(int i : order) if(cmp[i] == -1) rdfs(i, k++);
  return(k);
}

long long rec(int idx)
{
  long long ret = 1;
  for(int to : g[idx]) (ret *= rec(to)) %= mod;
  return((ret + 1) % mod);
}

int main()
{
  cin >> N >> M;
  
  while(M--) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    cg[B].push_back(A);
    rg[A].push_back(B);
  }
  int c = scc();
  for(int i = 0; i < N; i++) {
    for(int to : cg[i]) {
      if(cmp[i] == cmp[to]) continue;
      if(connect[cmp[i]][cmp[to]]++) continue;
      g[cmp[i]].push_back(cmp[to]);
      in[cmp[to]] = true;
    }
  }
  long long ret = 1;
  for(int i = 0; i < c; i++) {
    if(!in[i]) (ret *= rec(i)) %= mod;
  }
  cout << ret << endl;
}

Measured memory_bytes: 4208
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cout << (a) << endl
#define PRT2(a,b) cout << (a) << " " << (b) << endl
#define PRT3(a,b,c) cout << (a) << " " << (b) << " " << (c) << endl

typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> P;

int isWin(vector<int> num, int played) {
	if(num.size() == 1) return false;
	bool res = false;
	vector<int> next = num;
	int a = next.back(); next.pop_back();
	int b = next.back(); next.pop_back();
	if(a + b >= 10) {
		next.push_back(1);
		next.push_back((a + b) % 10);
	} else {
		next.push_back(a + b);
	}
	if(!isWin(next, played+1)) res = true;

	return res;
}

void coding() {
	int n;
	string num;
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		cin >> num;
		vector<int> v;
		for(int k=0; k<num.size(); k++) {
			v.push_back(num[k] - '0');
		}
		if(isWin(v, 0)) {
			printf("Fabre wins.\n");
		} else {
			printf("Audrey wins.\n");
		}
	}
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
	clock_t startTime = clock();
	freopen("a.in", "r", stdin);
#endif

	coding();

#ifdef _LOCAL_TEST
	clock_t elapsedTime = clock() - startTime;
	cout << endl;
	cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
	cout << "This is local test" << endl;
	cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define endl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define senky_bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=(res*a);
        a=(a*a);
        b/=2;
    }
    return res;
}
signed main()
{   
      senky_bansal
      IIIT_ALLAHABAD
      
     ll a,b,c,d;
     cin>>a>>b>>c>>d;
     ll ans=b-a+1;
    ll ans1 = b/c - (a-1)/c;
    ll ans2 = b/d-(a-1)/d;
    ll p3 = (c*d)/__gcd(c,d);
    ll ans3 =  b/p3-(a-1)/p3;
    cout<<ans-max(ans1,0LL)-max(ans2,0LL)+max(ans3,0LL)<<endl;
    
    
    
}







Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int N, cnt, ans;
    cin >> N;

    cnt = 0;
    rep(i, N){
        int a;
        cin >> a;
        if(cnt + 1 == a){
            cnt++;
        }
    }
    ans = -1;
    if(cnt != 0){
        ans = N - cnt;
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1005,INF=1<<30;

int main(){
    
    double R,C;int N;cin>>R>>C>>N;
    vector<pair<double,int>> P;
    for(int i=0;i<N;i++){
        double a,b,c,d;cin>>a>>b>>c>>d;
        if((a!=0&&a!=R&&b!=0&&b!=C)||(c!=0&&c!=R&&d!=0&&d!=C)) continue;
        P.push_back({atan2(a-R/2.0,b-C/2.0),i});
        P.push_back({atan2(c-R/2.0,d-C/2.0),i});
    }
    
    bool ok=true;
    
    sort(all(P));
    stack<int> ST;
    vector<int> used(N,0);
    for(int i=0;i<P.size();i++){
        int a=P[i].second;
        if(used[a]){
            if(ST.top()==a){
                ST.pop();
                used[a]=0;
            }else ok=false;
        }else{
            ST.push(a);
            used[a]=1;
        }
    }
    
    cout<<((ok) ? "YES" : "NO")<<endl;
}


Measured memory_bytes: 6512
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10,MOD=1e9+7;
int F[200];
int main ()
{
    string A;cin>>A;
    F[A[0]]++;F[A[1]]++;F[A[2]]++;F[A[3]]++;
    int c=0;
    for(int i=0;i<A.size();i++){
        if(F[A[i]]==2)c++;
    }
    if(c>=4)cout<<"Yes";
    else cout<<"No";
    return 0;
}
/*

*/

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	string s;
	cin >> s;
	if (s.size() != 26) {
		map<char, int>mp;
		rep(i, s.size()) {
			mp[s[i]]++;
		}
		for (char c = 'a'; c <= 'z'; c++) {
			if (mp[c] == 0) {
				print(s + c);
				return 0;
			}
		}
	}
	else if (s == "zyxwvutsrqponmlkjihgfedcba") {
		cout << -1 << endl;
		return 0;
	}
	else {
		int ansindex = 0;
		map<char, int>mp2;
		rrep(i, 25) {
			if (s[i] < s[i + 1]) {
				ansindex = i+1;
				break;
			}
		}
		string ans;
		rep(i, ansindex) {
			mp2[s[i]]++;
			ans += s[i];
		}
		//println(ans);
		for (char c = 'a'; c <= 'z'; c++) {
			if (mp2[c] == 0 && ans[ansindex-1]<c) {
				ans[ansindex-1]=c;
				println(ans);
				return 0;
			}
		}
	}
}

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

using namespace std;

#define pb push_back
#define eps 1e-9
#define PI acos(-1.0)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
const int INF = 1e9 + 5;

bool prime(ll x)
{
    if(x == 2)
        return true;
    for(int i = 2 ; i * i <= x ; i++)
        if(x % i == 0)
            return false;
    return true;
}

bool cmp(int a, int b)
{
    return a > b;
}
int a[int(1e5 + 5)];
int main()
{


    int n, k;
    cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    std::vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        for(int j = i + 1; j <= i + k; j++)
        {
            if(j < n)
                dp[j] = min(dp[j], dp[i] + abs(a[i] - a[j]));
        }
    }
    cout << dp[n - 1];
}


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


#define int long long 


const int mod = 1e9 + 7;


int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, ans = 0, sum = 0;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x; cin >> x; x %= mod;
		ans += sum * x % mod;
		ans %= mod;
		sum += x;
		sum %= mod;
	}

	cout << ans << endl;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define all(v) v.begin(), v.end()

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

void primeFactor(ll val, map<ll,ll> &primeList){
  if(val<1){
    return;
  }
  for(int i=2;i*i<val;i++){
    while(val%i==0){
      primeList[i]++;
      val/=i;
    }
  }
  if(val!=1){
    primeList[val]=1;
  }
  return;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  string s,t;cin>>s>>t;
  int ss=s.size();
  int st=t.size();
  int ans=INT_MAX;
  for(int i=0;i<ss-st+1;i++){
    int cnt=0;
    for(int j=0;j<st;j++){
      if(s[i+j]!=t[j]){
        cnt++;
      }
    }
    ans=min(ans,cnt);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    if(x-r>=0 && x+r <= W && y-r>= 0 && y+r <=H){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3092
def calc(n, w, v)
  a, r = 0.01, [0] * 100
  v.each do |e|
    r[e / w] += 1
  end
  (v.max / w).times do |i|
    a += r[i].to_f / r.max * (v.max / w - i) / (v.max / w)
  end
  a
end
loop do
  n, w = gets.split.map(&:to_i)
  break if n == 0
  v = []
  n.times do |i|
    v[i] = gets.to_i
  end
  puts calc(n, w, v)
end

Measured memory_bytes: 8816
from sys import stdin

def ExhaustiveSearch(A :list,n : int,M :list,ANS :list):
	A = [0 for _ in range(n)]
	rec(0,A,n,M,ANS)

def rec(i : int, A : list, n : int,M :list,ANS : list):

	if i == n:
		sm = 0
		for j,k in enumerate(A):
			if k == 1:
				sm += int(M[j])
		ANS.append(sm)
		return

	A[i] = 0
	rec(i+1,A,n,M,ANS)

	A[i] = 1
	rec(i+1,A,n,M,ANS)


if __name__ == '__main__':

	A = []
	ANS = []

	n = int(input())
	inlist = stdin.readline().strip().split()

	input()
	outlist = list(map(int,stdin.readline().strip().split()))

	ExhaustiveSearch(A,len(inlist),inlist,ANS)
	ANS.sort()
	for i in outlist:
		if i in ANS:
			print("yes")
		else:
			print("no")


Measured memory_bytes: 46996
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  long long int n;
  while(cin>>n,n){
    long long int co=0;
    while(n!=1){
      co++;
      if(n%2)n=3*n+1;
      else n/=2;
    }
    cout<<co<<endl;
  }
}

Measured memory_bytes: 1156
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int X = sc.nextInt();
		int t = sc.nextInt();
		
		if(X >= t) {
			System.out.println(X - t);
		} else {
			System.out.println(0);
		}
	}

}


Measured memory_bytes: 21972
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a = 0, w = 0, t = 0, r = 0;

    for (int i = 0; i < n; i++) {
      String s = sc.next();
      switch (s) {
      case "AC":
        a++;
        break;

      case "WA":
        w++;
        break;

      case "TLE":
        t++;
        break;

      case "RE":
        r++;
        break;
      }
    }

    System.out.println("AC x " + a);
    System.out.println("WA x " + w);
    System.out.println("TLE x " + t);
    System.out.println("RE x " + r);

  }
}

Measured memory_bytes: 58124