akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

class Main {
    public static void main(String[] args) {
        //Scanner sc = new Scanner(System.in);
        FastScanner sc = new FastScanner();
        long N = sc.nextLong();

        long minops = 1000000000005l;
        for (long i = 1; i * i <= N; i++) {
            if (N % i == 0) {
                long div1 = N / i;

                long ops = div1 - 1 + i - 1;
                if (minops > ops) {
                    minops = ops;
                }
            }
        }
        System.out.println(minops);
    }

}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}

#define deb(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define END '\n'
#define inf 9e18
#define ff first
#define ss second
#define pb push_back

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((c >= a && c <= b) ? "Yes" : "No");
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0; i<(n); ++i)
#define REP(i, d, n) for(long long i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
int main() {//---------------------------------------------------------

 long double a,b; cin>>a>>b;
  ll ans=1; ans=a*b; ans=ans/1;
  cout<<ans<<endl;
 
return 0; }


Measured memory_bytes: 3732
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
    let k: usize = read();
    let mut v = Vec::new();
    for i in 1..10 {
      v.push(i);
    }
    for i in 1..10 {
      dfs(11, i, &mut v);
    }
    v.sort();
    println!("{}", v[k-1]);
}

fn dfs(depth: usize, now: i64, tot: &mut Vec<i64>) {
    if depth == 0 {
       return;
    }
    // if now % 10 == 0 {
    //   tot.push(now*10 + 0);
    //   tot.push(now*10 + 1);
    // } else {
    //   let x = now % 10;
    //   tot.push(now*10 + (now - 1));
    //   tot.push(now*10 + now);
    //   tot.push(now*10 + now + 1);
    // }

    for i in -1..2 {
      if now % 10 == 0 && i == -1 {
        continue;
      }
      if now % 10 == 9 && i == 1 {
        continue;
      }
      tot.push(10*now + now%10 + i);
      dfs(depth-1, 10*now + now%10 + i, tot);
    }
}


Measured memory_bytes: 23800
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
long long a,b,c,d;
using namespace std;
int main()
{
	cin>>a>>b>>c>>d;
	if(d%2==1) 
		{
			if(b-a>=1e18) cout<<"Unfair"<<endl;
			else cout<<b-a<<endl;
		}
	if(d%2==0)
		{
			if(a-b>=1e18) cout<<"Unfair"<<endl;
			else cout<<a-b<<endl;
		}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

ll dp[3001][3001][2];

int main(){	
	long long T;
	long long N;
	scanf("%lld",&N);
	vector<long long> B(N-1+1);
	vector<long long> A(N-1+1);
	scanf("%lld",&T);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
	}
	repn(i, N) {
		rep(j, T+1) {
			if (j-A[i-1] >= 0) dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-A[i-1]][0]+B[i-1]); else dp[i][j][0] = dp[i-1][j][0];
			if (j-A[i-1] >= 0) dp[i][j][1] = max(max(dp[i-1][j][1], dp[i-1][j-A[i-1]][1]+B[i-1]), dp[i-1][j][0]+B[i-1]); else dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+B[i-1]);
		}
	}

	ll res = 0;
	rep(i, T) {
		res = max(res, max(dp[N][i][0], dp[N][i][1]));
		// cout << i << " " << dp[N][i][0] << " " << dp[N][i][1] << endl;
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 141056
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
c = input()
cnt = Counter(c)
t = "R"*cnt["R"]+"W"*cnt["W"]

ans = 0
for x, y in zip(c, t):
    ans += (x != y)
print(0--ans//2)


Measured memory_bytes: 10584
#include<iostream>
#include<iomanip>

using namespace std;

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

	int* a = new int[n];

	int max = -1000000, min = 1000000;
	long long sum = 0;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
		if (a[i] > max) max = a[i];
		if (a[i] < min) min = a[i];
	}

	cout << min << " " << max << " " << sum << "\n";
}

Measured memory_bytes: 1228
//インクルード(アルファベット順)
#ifndef TEMPLATE
#define TEMPLATE
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<ctime>
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
//#include<unordered_map>//イテレータあるけど順序保持しないmap
//#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<valarray>//なんとなく追加
//メモ：表示桁数を大きくする　　cout << fixed << setprecision(20) << cm << endl;
using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PI acos(-1.0)
#define answer(ans) cout<<ans<<endl;
#define input(N) cin >> N ;

#endif // TEMPLATE
signed main() {
int ti = clock();
ll N,ans=0,tmp;
cin >> N;
vector<ll> a(N);
REP(i,N){
  cin >>a[i];
  ans +=a[i];
}

answer(ans-N);
return 0;
}

Measured memory_bytes: 3656
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    int w = sc.nextInt();
    if (s <= w){
      System.out.println("unsafe");
    }else {
      System.out.println("safe");
    }
  }
}

Measured memory_bytes: 35704
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> f(vector<int> v){
    vector<int> w;
    for(int i = 1; i < (int)v.size(); i += 1) w.push_back(abs(v[i] - v[i - 1]));
    return w;
}
int C(int N, int M){
    for(int i = 0; i < 20; i += 1) if((M >> i & 1) > (N >> i & 1)) return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    string s;
    cin >> s;
    vector<int> v;
    for(char c : s) v.push_back(c - '0');
    auto w =  f(v);
    if(count(w.begin(), w.end(), 1) == 0){
        int ans = 0;
        for(int i = 0; i < N; i += 1) ans += C(N - 1, i) * v[i] / 2;
        cout << ans % 2 * 2;
    }
    else{
        int ans = 0;
        for(int i = 0; i < N; i += 1) ans += C(N - 1, i) * v[i];
        cout << ans % 2;
    }
    return 0;
}

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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

void hawawa()
{
	int x = 0, n, ans = 0;
	cin >> n;
	string str;
	cin >> str;
	for (auto&& i : str) {
		switch (i)
		{
		case 'I':
			x++;
			ans = max(ans, x);
			break;
		default:
			x--;
		}
	}
	cout << ans << "\n";
}

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


Measured memory_bytes: 256
X,Y,Z = (int(x) for x in input().split())
temp1 = X
temp2 = Y
temp3 = Z
X = temp2
Y = temp1
X = temp3
Z = temp2
x = str(X)
y = str(Y)
z = str(Z)
print(x + ' ' + y + ' ' + z)

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception {
	Scanner scan = new Scanner(System.in);
	Integer x = scan.nextInt();
	Integer y = scan.nextInt();
	Integer z = scan.nextInt();	
	
	if(x>z){
		Integer tmp = x;
		x = z;
		z = tmp;
	}
	if(x>y){
		Integer tmp = x;
		x = y;
		y = tmp;
	}
	if(y>z){
		Integer tmp = z;
		z = y;
		y = tmp;
	}
	
	System.out.println(x+" "+y+" "+z);
	
	}
}

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

int main()
{
int x,y;
  cin>>x>>y;
  int values[3];
  values[0] = x+y;
  values[1] = x-y;
  values[2] = x*y;
  sort(values, values + 3, greater<int>());
  cout<<values[0];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define read cin >>
#define echo cout <<
#define fin << endl
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)

// for debug macro
bool global_debug_flag = true;
#define DEBUG(val) \
  if (global_debug_flag) cout << #val << " = " << val << endl

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  REP(i, 1000) {
    string i_str = to_string(i);
    string tmp = string(3 - i_str.length(), '0') + i_str;
    int res = 0;
    for (int j = 0; j < n && res < 3; j++) {
      res += (s[j] == tmp[res]);
    }
    if (res == 3) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int N, M;
  int map[1000];
  int i;
  int in[1000];
  int p;
  while(1) {
    scanf("%d %d", &N, &M);
    if(N == 0 && M == 0) break;
    for(i = 0; i < N; i++) {
      scanf("%d", &map[i]);
    }
    p = 0;
    for(i = 0; i < M; i++) {
      scanf("%d", &in[i]);
    }
    for(i = 0; i < M; i++) {
      p += in[i];
      p += map[p];
      if(p+1 >= N) {
	printf("%d\n", i+1);
	break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <stdlib.h> 
int main() {
	int h; int w,mark;
	scanf("%d %d", &h,&w);
	while (h!=0&&w!=0){
		for(int i=0;i<h;i++){
			mark=i%2;
			for(int j=0;j<w;j++){
				if(!mark){
					printf("#");
				}else{
					printf(".");
				}
				mark=!mark;
			}
			puts("");
		}
		puts("");
		scanf("%d %d", &h,&w);
	}
	return 0;
}
 



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

double dp[3001][3001];

double solve(double arr[], int i, int x){
    if(x==0)return 1;
    if(i==0)return 0;
    if(dp[i][x] > -0.9) return dp[i][x];
    return dp[i][x] = arr[i] *solve(arr, i-1, x-1) + (1-arr[i])*solve(arr, i-1, x);
}
int main() {
	int n;
	cin>>n;
	double arr[n+1];
	for(int i=1;i<=n;i++){
	    cin>>arr[i];
	}
	for(int i=0;i<3001;i++){
	    for(int j=0;j<3001;j++){
	        dp[i][j] =-1;
	    }
	}
    cout<<fixed<<setprecision(10)<<solve(arr, n, (n+1)/2)<<endl;
	
	
	return 0;
}

Measured memory_bytes: 74380
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

n=IN()
a=LI()
p=1
if 0 in a:
    print(0)
    exit()
for i in a:
    p*=i
    if p>pow(10,18):
        print(-1)
        exit()
print(p)


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

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

#define INF 1e9

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i, N){
    cin >> A[i];
  }
  map<int, ll> mp;
  REP(i, N){
    mp[A[i]]++;
  }
  ll ans = 0;
  for(auto m : mp){
    ans += m.second * (m.second-1) / 2;
  }
  REP(i, N){
    cout << ans - (mp[A[i]]-1) << endl;
  }
  return 0;
}


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

using namespace std;
using ll = long long;

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((int)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back


int main()
{
    ll N;
    cin >> N;
    vector<ll> a(N-1), b(N-1);
    REP(i,0,N-1){
        cin >> a[i] >> b[i];
        --a[i];
        --b[i];
    }

    vector<vector<ll>> G(N);
    vector<ll> idx(N);
    REP(i,0,N-1){
        G[a[i]].pb(b[i]);
        G[b[i]].pb(a[i]);
        idx[b[i]] = i;
    }

    ll K = 0;
    REP(i,0,N){
        K = MAX(K,G[i].size());
    }

    vector<ll> dist(N, -1);
    queue<int> Q;

    dist[0] = 0;
    Q.push(0);

    vector<ll> c(N-1);
    ll prev_c = 0, d;
    c[0] = 0;
    while(!Q.empty()){
        ll v = Q.front();
        Q.pop();
        d = 1;
        prev_c = c[idx[v]];
        FORR(nv,G[v]){
            if(dist[nv] != -1) continue;
            if(prev_c == d) ++d;
            c[idx[nv]] = d;
            ++d;
            dist[nv] = dist[v] + 1;
            Q.push(nv);
        }
    }

    _PR(K);
    REP(i,0,N-1){
        _PR(c[i]);
    }


    return 0;
}

/*



*/

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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (int i = j; i < (n); i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1e9;

int main(){

  int n;cin>>n;
  int a[n+10];
  rep(i,0,n){
    cin>>a[i];
  }

  int mi=1e9;
  rep(i,-100,101){
    int sum=0;
    rep(j,0,n){
      sum+=(i-a[j])*(i-a[j]);
    }
    mi=min(mi,sum);
  }

  out(mi);


  return 0;
}


Measured memory_bytes: 256
// In the name of God //
 
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define pii pair <int, int>
using namespace std;
const int N = 1e6 + 5;
const int MAXN = 1e7 + 50;
const int mod = 1e9 + 7;


void solve() {
    ll n, m, k;
    cin >> n >> m >> k;
    ll ans = 0;
    vector<ll> pref(n + 1), b(m);
    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;
        pref[i + 1] = pref[i] + x;
        if (pref[i + 1] <= k) {
            ans = max (ans, i + 1);
        }
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    long long s = 0;
    for (ll i = 0; i < m; ++i) {
        s += b[i];
        if (s <= k) {
            ans = max (ans, i + 1);
        }
        ll lo = 1, hi = n;
        while (hi >= lo) {
            ll mid = (lo + hi)/2;
            if (pref[mid] + s <= k) {
                ans = max(ans, i + 1 + mid);
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    cout << ans;
}


int main()  {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    } 
}                                   

Measured memory_bytes: 6352
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n;
int a[N],du[N];
int head[N],ver[N],nxt[N],tot;
void add(int a,int b)
{
    tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
int f[N];
void dfs(int x,int fa)
{
    int sum=0,mx=0;
    bool flag=0;
    for(int i=head[x];i;i=nxt[i])
    {
        if(ver[i]==fa)continue;
        flag=1;
        dfs(ver[i],x);
        sum+=f[ver[i]];mx=max(mx,f[ver[i]]);
    }
    if(!flag){f[x]=a[x];return ;}
    int mn;
    if(mx<=(sum+1)/2)mn=sum/2+sum%2;
    else mn=mx;
    if(a[x]>sum||a[x]<mn)
    {
        puts("NO");
        exit(0);
    }
    f[x]=2*a[x]-sum;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int t1,t2;
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&t1,&t2);
        add(t1,t2);add(t2,t1);
        du[t1]++;du[t2]++;
    }
    if(n==2)
    {
        if(a[1]==a[2])puts("YES");
        else puts("NO");
        return 0;
    }
    int root;
    for(int i=1;i<=n;i++)if(du[i]>=2)root=i;
    dfs(root,-1);
    if(f[root]!=0)puts("NO");
    else puts("YES");
    return 0;
}


Measured memory_bytes: 12288
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc =  new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    long A = Long.parseLong(S[0]);
    long B = Long.parseLong(S[1]);
    long x = Long.parseLong(S[2]);
    
    long a = (A-1) / x;
    if(A == 0){
      a = -1;
    }
    long b = B / x;
    long ans = b - a;
    System.out.println(ans);
  }
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define fori(i, m, n) for(int i = m; i < (int)n; i++)
#define forl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define all(v) v.begin(), v.end()
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');
}
const string btos(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int n;cin>>n;
  int ans=(n+1)/2;
  cout<<ans<<endl;
  return 0;
}


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

#define PI 4*atan(1)
#define INF 1e8

typedef long long ll;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
  ll X, t;
  cin >> X >> t;
  if(X - t >= 0)cout << X - t << endl;
  else cout << 0 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int INF = 100100100;
using namespace std;

bool isSS(string str){
  int len=str.length();
  if(len%2==1) return false;
  rep(i,len/2){
    if(str[i]!=str[i+len/2]) return false;
  }
  return true;
}

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

  int res=0;
  int N=s.length();
  for(int i=1;i<=N-1;i++){
    string str=s.substr(0,N-i);
    if(isSS(str)) res=max(N-i,res);
  }

  cout << res << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i+=1)
#define reps(i,a,b) for(int i=a;i>=b;i-=1)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define in1(x) int x; cin>>x;
#define in2(x, y) int x, y; cin>>x>>y;
#define in3(x, y, z) int x, y, z; cin>>x>>y>>z;
#define in4(x, y, z, w) int x, y, z, w; cin>>x>>y>>z>>w;
#define mi unordered_map<int,int>
#define mem(x) memset(x, 0, sizeof(x))
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
using namespace std;
bool primes[1000001];vi prime; void seive(); int gcd(int a, int b); int power(int x, int y);

int32_t main(void){
	IOS;
	in1(n);
	int ans = ceil((n*1.00)/1000);
	cout<<ans*1000-n<<endl;
}

void seive(){memset(primes, true, sizeof(primes));primes[0] = primes[1] = false;for(int i = 2; i*i<=1000000;i += 1){
if(primes[i]){for(int j = i*i; j <= 1000000;j += i) primes[j] = false;}}rep(i, 2, 1000001){if(primes[i]) prime.pb(i);}}
int gcd(int a, int b){return b==0 ? a : gcd(b, a%b);}
int power(int x, int y){ int res = 1;x = x % mod; if (x == 0) return 0;
while (y > 0){ if(y & 1) res = (res*x) % mod; y = y>>1; x = (x*x) % mod;} return res;}


Measured memory_bytes: 3756
fun main(args: Array<String>) {
    val S = readInputLine().split("/").map{it.toInt()}
    
    if (S[0] < 2019 || (S[0] == 2019 && S[1] < 4) || (S[0] == 2019 && S[1] == 4 && S[2] <= 30)) {
        println("Heisei")
    } else {
        println("TBD")
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37732
from math import sqrt

_ = input()
x = [ float(i) for i in input().split() ]
y = [ float(i) for i in input().split() ]

def f1(x, y):
    return sum([ abs(t[0] - t[1]) for t in zip(x, y) ])

def f2(x, y):
    return sqrt(sum([ pow(t[0] - t[1], 2) for t in zip(x, y) ]))

def f3(x, y):
    return pow(sum([ pow(abs(t[0] - t[1]), 3) for t in zip(x, y) ]), 1.0 / 3.0)

def f4(x, y):
    return max([abs(t[0] - t[1]) for t in zip(x, y)])

print(f1(x, y))
print(f2(x, y))
print(f3(x, y))
print(f4(x, y))



Measured memory_bytes: 5712
#include <bits/stdc++.h>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
#define mod 1000000007

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}

int main(){
    ll n,total=0;
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n+1,0);
    rep(i,n) cin >> a[i];
    rep(i,n) b[a[i]]++;
    for(ll i=1;i<=n;i++){
        ll x;
        x=b[i];
        x=x*(x-1)/2;
        total+=x;
    }
    for(ll i=0;i<n;i++){
        ll ans=total;
        ans=ans-(b[a[i]]-1);
        cout << ans << endl;
    }
    

    return 0;
}





Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B;
  cin>>A>>B;
  if(A==0){
    if(B!=100)cout<<B<<endl;
    else cout<<101<<endl;
  }
  else if(A==1){
    if(B!=100)cout<<B*100<<endl;
    else cout<<10100<<endl;
  }
  else{
    if(B!=100)cout<<B*10000<<endl;
    else cout<<1010000<<endl;
  }
  return 0 ;
}


Measured memory_bytes: 256
/* AOJ 0058 Orthogonal */

#include <stdio.h>

int main()
{
    double xA,yA,xB,yB,xC,yC,xD,yD;

    while (scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &xA, &yA, &xB, &yB, &xC, &yC, &xD, &yD) != EOF) {
        if (fabs((yA - yB) * (yC - yD) + (xA - xB) * (xC - xD)) < 1e-10)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int f[N],n,m,ans,siz[N];
int find(int x){
  return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)f[i]=i;
  while(m--){
    int u,v;
    scanf("%d%d",&u,&v);
    f[find(u)]=find(v);
  }
  for(int i=1;i<=n;i++){
    int anc=find(i);
    ans=max(ans,++siz[anc]);
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 10652
#include <iostream>

using namespace std;

typedef long long ll;

int main () {
  ll n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;

  n--; // now the number of moves
  for (int i = 0; i <= n; i++) {
    // number of times we subtract;
    ll mn = a + c * (n - i) - d * i;
    ll mx = a + d * (n - i) - c * i;

    if (mn <= b && b <= mx) {
      cout << "YES" << endl;
      exit(0);
    }
  }

  cout << "NO" << endl;
}


Measured memory_bytes: 3616
#include <iostream>
            #include <string>
            #include <bits/stdc++.h>
             
            using namespace std;
             
            int main(){
              string  s;
              cin >> s;
              int a = 0;
              int z = 0;
              
              for(int i = 0; i < s.length(); i++) {
                if(s[i] == 'A'){
                  a = i;
                  break;
                }
              }
              
              for(int i = s.length()-1; i >= 0; i--) {
                if(s[i] == 'Z'){
                  z = i;
                  break;
                }
              }
              cout <<( z-a + 1 )<< endl;
            }

Measured memory_bytes: 640
// https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_f

#include "algorithm"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll t1, t2, a1, a2, b1, b2;

  cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;

  ll c1 = a1 - b1;
  ll c2 = a2 - b2;

  ll diff = c1 * t1 + c2 * t2;

  if (diff == 0) drop("infinity");
  if ((c1 > 0 && diff > 0) || (c1 < 0 && diff < 0)) drop(0);

  if (c1 < 0) {
    c1 *= -1;
    c2 *= -1;
    diff *= -1;
  }

  // c1 > 0 && c2 < 0 かつ diff < 0

  ll highest = c1 * t1;

  ll res = ((highest + abs(diff) - 1) / abs(diff)) * 2;

  if (highest % abs(diff) == 0) {
    // 最後に 1 回だけ触れる
    res++;
  }

  // 最初の 1 回除く
  res--;

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define int long long int
#define float double
#define pb push_back
#define FF first
#define SS second
#define N 201000
#define MOD 1000000007
#define fn(i,n) for(int i=0;i<n;i++)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pii pair<int,int>
#define INF 1000000000000000000
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

signed main() 
{
    speed;
    
    
    string s,t;
    cin>>s>>t;
    int m=s.length();
    int n=t.length();
    int dp[m+1][n+1];
    int i,j;
    for(i=0;i<=m;i++)
    {
    	for(j=0;j<=n;j++)
    	{
    		if(i==0 || j==0) dp[i][j]=0;
    		else if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
    		else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    	}
    }
    

    i=m;
    j=n;
    string ans="";
    while(i>0 && j>0)
    {
    	if(s[i-1]==t[j-1])
    	{
            ans+=s[i-1];
            i--;
            j--;
    	}
    	else if(dp[i-1][j]>=dp[i][j-1]) i--;
    	else j--;
    }
    
    int z=ans.length();
    for(int i=z-1;i>=0;i--)
    	cout<<ans[i];
}


Measured memory_bytes: 70656
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;

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

  cout << 6-A-B << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si size()
#define bk back()
#define popb pop_back()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define ump unordered_map
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define fore(i,a,n) for(int i=a;i<=n;i++)
#define len length()
const ll mod=1e9+7;
int main()
{
   string s;
   cin>>s;
   int d;
   cin>>d;
   vector<vector<ll>>dp(d,vector<ll>(2));
   int n=s.len;
   dp[0][0]=1;

   //dp[i][j]  j=0 number not small already  j=1 number already small
   forl(i,0,n)
   {
       vector<vector<ll>>newdp(d,vector<ll>(2));
       forl(j,0,d)
       {
           forl(k,0,2)
           {
               forl(digit,0,10)
               {
                   if(k==0 && digit>s[i]-'0') break;
                   if(k==1)newdp[(j+digit)%d][k]=(newdp[(j+digit)%d][k]+dp[j][k])%mod;
                   else 
                   {
                       if(digit<s[i]-'0')
                       {
                            newdp[(j+digit)%d][1]=(newdp[(j+digit)%d][1]+dp[j][k])%mod; 
                       }else{
                           newdp[(j+digit)%d][0]=(newdp[(j+digit)%d][0]+dp[j][k])%mod; 
                       }
                   }
               }
           }
       }
       dp=newdp;
   }    
   cout<<(dp[0][0]+dp[0][1]+mod-1)%mod<<endl;

}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  cin >> a;
   vector<int> vec;
  vec = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << vec.at(a-1) << endl;
}

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

typedef long long int ll;
typedef long double ld;

//****************************************************                
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll> 
#define vpll vector<pll>
#define all(X) X.begin(),X.end()
#define endl "\n" //comment it for interactive questions
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a,b) cerr << #a << ": " << a << " " << #b << ": " << b << endl;
#define trace3(a,b,c) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << endl;
#define trace4(a,b,c,d) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << #d << ": " << d << endl;
#define OC   
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
        //*******************************************************
//Some Functions

ll MOD = (ll)1e9+7; //change it for other mods

ll powmod(ll a,ll b)
{
   ll res = 1;
   while(b > 0) {
      if(b & 1) res = (res * a) % MOD;
      a = (a*a)%MOD;
      b = b >> 1; 
  }
  return res % MOD;
}

void solve(ll testnum)
{
    ll n;
    cin >> n;
    MOD = 9*n;
    for(ll i=1;i<=(ll)1e6;i++) {
    	ll res = powmod(10, i);
    	res = (MOD + res - 1)%MOD;
    	ll rt = (7 * res)%MOD;
    	if(rt == 0) {
    		cout << i << "\n";
    		return;
    	}
    }
    cout << "-1\n";
}

int main()
{
    FAST_IO;
    #ifdef STIO 
      freopen("input.txt" , "r", stdin);
      freopen("output.txt" , "w", stdout);
    #endif
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve(i);
    }
}

Measured memory_bytes: 3656
import heapq

k = int(input())
i=0
lunlun = [1,2,3,4,5,6,7,8,9]
heapq.heapify(lunlun)

while True:
    i += 1
    if i == k:
        break
    x = heapq.heappop(lunlun)
    if x % 10 != 0:
        heapq.heappush(lunlun,10 * x + (x % 10) -1)
    heapq.heappush(lunlun,10 * x + (x % 10))
    if x % 10 != 9:
        heapq.heappush(lunlun,10 * x + (x % 10) +1)

print(lunlun[0])

Measured memory_bytes: 11748
def task(n, m, h, a, b):
    roads = {}

    for i in range(1, n + 1):
        roads[i] = set()

    for i in range(0, m):
        roads[a[i]].add(b[i])
        roads[b[i]].add(a[i])

    total = 0
    for i in range(0, n):
        highest = True

        for road in roads[i + 1]:
            if h[road - 1] >= h[i]:
                highest = False
                break

        if highest:
            total += 1

    print(total)


n, m = map(int, input().split())
h = list(map(int, input().split()))
a = []
b = []
for i in range(0, m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

task(n, m, h, a, b)


Measured memory_bytes: 55516
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(int)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef long double ld;
typedef int ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
const int SIZE=2*1e5;
const int INF=1LL<<30;
const LL p=7+1e9;
LL n,m;
LL solve(){
	cin >> n >> m;
	if(n==1) return m+1;
	n--;
	m++;
	LL c=m/n;
	LL mods=m%n;
	c%=p;
	mods%=p;
	n%=p;
	return (mods*(2*c%p+1)%p+n*c%p*c%p)%p;
	//return (mods%p*(c+1)%p*(c+1)%p+(n-mods)%p*(c)%p*(c)%p)%p;
}
int main(){
	cout << solve()%p << endl;
	return 0;
}

Measured memory_bytes: 3088
n,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]


for i in range(30):#要素数以上の2のベキを見つける
    if n<=1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[None for i in range(2*seg_el-1)]#Segment tree（遅延伝搬を用いるが、一本のセグ木でOK）

def lazy_update(k,x):#一つ下の子へ伝搬
    if 0<=k<seg_el-1:
        lazy_item,SEG[k]=SEG[k],None
        SEG[k*2+1]=SEG[k*2+2]=lazy_item


def update(a,b,x,k,l,r):
    if SEG[k]!=None:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        lazy_update(k,x)
        
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を更新.後にアクセスされたときに遅延評価する.
        SEG[k]=x#
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)

def getvalue(n):#値を得る
    i=n+seg_el-1
    ANS=SEG[i]
    i=(i-1)//2

    while i>=0:
        if SEG[i]!=None:
            ANS=SEG[i]#できるだけ親に近いノードから値を得るようにする.（そこが最後に更新されたものなので）
        i=(i-1)//2
    return ANS

for i in range(n):
    SEG[i+seg_el-1]=(1<<31)-1

for query in Q:
    if query[0]==0:
        update(query[1],query[2]+1,query[3],0,0,seg_el)
    else:
        print(getvalue(query[1]))



Measured memory_bytes: 26692
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

double v[64];
double cache[64][64];

double Solve(int a, int b) {
  if (cache[a][b] > 0) return cache[a][b];
  if (a == b) {
    return v[a];
  }
  double ans = 0;
  for (int k = a; k < b; ++k) {
    double t = (Solve(a, k) + Solve(k+1, b)) / 2;
    if (t > ans) ans = t;
  }
  return cache[a][b] = ans;
}

int main() {
  int N;
  while (cin >> N) {
    memset(cache, 0, sizeof(cache));
    for (int i = 0; i < N; ++i) {
      cin >> v[i];
    }
    sort(v, v+N);
    printf("%0.8f\n", Solve(0, N-1));
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <utility>
using namespace std;

int main() {
  int N;
  cin>>N;
   
  vector<int> p(N);
  for(int i=0;i<N;++i){
    cin>>p[i];
  }
  
  int count=0;
  
  for(int i=0;i<N;++i){
    if(p[i]!=i+1)
      ++count;
  }
  
  if(count==0 || count==2)
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

vector<vector<string>> vs;

int main() {

  int H, W; cin >> H >> W;
  vs.resize(H);
  rep(i, H) vs[i].resize(W);
  rep(i, H) rep(j, W) {
    cin >> vs[i][j];
    if(vs[i][j] == "snuke") {
      cout << char(j + 'A') << i + 1 << endl;
      return 0;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int k,a,b,c=0;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
    	if(i%k==0)
    	{
    		c++;
		}
	}
	if(c!=0)
	{
		cout<<"OK"<<endl;
	}
	else
	{
		cout<<"NG"<<endl;
	}
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
  string a;
  int k;
  cin>>a>>k;
  int cn[30]={};
  map<string,int> s;
  vector<string> v;
  for(int i=0;i<a.size();i++){
    string t;
    for(int j=0;j<k;j++){
      if(i+j==a.size())break;
      t+=a[i+j];
      if(s[t])continue;
      s[t]++;
      v.push_back(t);
    }
  }
  sort(v.begin(),v.end());
  //for(int i=0;i<v.size();i++)cout<<v[i]<<endl;
  cout<<v[k-1]<<endl;
  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main()
{
  int n;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++)
    cin >> a[i];
   int ans=1000;
  for(int i=0;i<n-1;i++)
  {
    if(a[i]<a[i+1])
    {
     int cnt=ans/a[i];
      ans+=((cnt)*(a[i+1]-a[i]));
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3636
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
string a;
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    string b=a;
    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();++i)
    {
        if(a[i]=='b') a[i]='d';
        else if(a[i]=='d') a[i]='b';
        else if(a[i]=='p') a[i]='q';
        else if(a[i]=='q') a[i]='p';
    }
    if(a==b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 512
from collections import deque

h, w = [int(_) for _ in input().split()]
G = [list(input()) for _ in range(h)]

que = deque()
for i in range(h):
    for j in range(w):
        if G[i][j] == '#':
            que.append((i, j, 0))
cnt = 0
while que:
    i, j, c = que.popleft()

    for ni, nj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if i + ni < 0 or j + nj < 0: continue
        if i + ni >= h or j + nj >= w: continue

        if G[i + ni][j + nj] == '.':
            G[i + ni][j + nj] = '#'
            que.append((i + ni, j + nj, c + 1))
            cnt = max(cnt, c + 1)
print(cnt)


Measured memory_bytes: 161628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int n,m;
    cin >> n >> m;
    int s = 0;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
        s += a[i];
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    double x = (1.0*s)/(4*m);
    rep(i,m){
        if(a[i]<x){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

int main(){
    int w, h, n;
    cin >> w >> h >> n;
    vector<int> A;
    int l = 0, r = w, u = h, d = 0;
    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        if(a == 1) l = max(l, x);
        else if(a == 2) r = min(r, x);
        else if(a == 3) d = max(d, y);
        else u = min(u, y);
    }
    if(r-l<=0 || u-d<=0){
        cout << 0 << endl;
        return 0;
    }
    else{
        cout << (r-l) * (u-d) << endl;
        return 0;
    }
}


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

typedef struct Node
{
	int num;
	struct Node *next;
} Node;

int main()
{
	int n = 8, k = 5, m = 3;
	while (scanf("%d %d %d", &n, &k, &m) && n)
	{
		Node *entry = malloc(sizeof(Node));
		Node *tmpNode = entry;
		for (int i = 1; i < n; i++)
		{
			tmpNode->num = i;
			tmpNode->next = malloc(sizeof(Node));
			tmpNode = tmpNode->next;
		}
		tmpNode->next = entry;
		tmpNode->num = n;
		int countDown = (m - 1) % n;
		Node *prevNode = tmpNode;
		tmpNode = tmpNode->next;
		while (tmpNode->next != tmpNode)
		{
			if (countDown == 0)
			{
				prevNode->next = tmpNode->next;
				free(tmpNode);
				tmpNode = prevNode->next;
				n--;
				countDown = (k - 1) % n;
			}
			else
			{
				prevNode = tmpNode;
				tmpNode = tmpNode->next;
				countDown--;
			}
		}
		printf("%d\n", tmpNode->num);
	}
	return 0;
}


Measured memory_bytes: 2092
#include <iostream>

using namespace std;

int poker(int x)
{
	return x == 1 ? 14 : x;
}

int main()
{
	int A, B;
	cin >> A >> B;
	
	A = poker(A);
	B = poker(B);
	if (A > B) {
		cout << "Alice" << endl;
	}
	else if (B > A) {
		cout << "Bob" << endl;
	}
	else {
		cout << "Draw" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,k;
	cin>>a>>b>>c>>d>>k;
	
	int t1=c-a;
	int t2=d-b;
	int t=t1*60+t2;
	t=t-k;
	cout<<t;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n, s;

		n = sc.nextInt();
		s = sc.nextInt();
		while (n + s != 0) {
			System.out.println(f(n, s, -1, 1));

			n = sc.nextInt();
			s = sc.nextInt();
		}
	}

	public static int f(int n, int s, int pre, int cnt) {
		if (n == cnt) {
			if (0 < s - pre && s <= 9) {
				return 1;
			} else {
				return 0;
			}
		}
		int count = 0;
		for (int i = pre + 1; i <= 9; i++) {
			count += f(n, s - i, i, cnt + 1);
		}
		return count;
	}
}

Measured memory_bytes: 12000
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

		
	

		// ??\?????????
		InputStreamReader is = new InputStreamReader(System.in);
		
		// ??\??????Buffer???????´?
		BufferedReader br = new BufferedReader(is);
		
		// String?????§1?????????????????????
		String str = br.readLine();
		
		// split??§?????????????????????????´?
		String[] a = str.split(" ", 0);
		
		// int???????????£?¨?
		int[] b = new int[2];
		
		// b???0?????????a???0?????????int????????????????´?
		b[0] = Integer.parseInt(a[0]);
		
		// b???1?????????a???1?????????int????????????????´?
		b[1] = Integer.parseInt(a[1]);

		//??¢?????¨??¨????????????????????§????????£?????????
		System.out.println((b[0] * b[1]) +" " + (b[0]*2 + b[1]*2));
	}
}

Measured memory_bytes: 24208
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int d = scan.nextInt();
        int m = scan.nextInt();
        for (int i = 0; i < m; i++) {
            int x = scan.nextInt();
            d-=x;
        }
        System.out.println(d < 0 ? -1 : d);
    }
}


Measured memory_bytes: 46344