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

class Graph {
	private int totalVertex;
	private LinkedList<LinkedList<Integer>> adjList;
	//adjacency list of edges
	public Graph() { totalVertex = 0; }
	public void loadAdjList() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjList = new LinkedList<LinkedList<Integer>>();
		for(int i = 0; i < totalVertex; i ++) {
			LinkedList<Integer> tmp = new LinkedList<Integer>();
			int idx1 = in.nextInt() - 1;
			int degree = in.nextInt();
			//System.out.println("mark idx1 = " + idx1 + " degree = " + degree);
			for(int j = 0; j < degree; j ++) {
				int idx2 = in.nextInt() - 1;
				tmp.add(idx2);
			}	
			adjList.add(tmp);
		}
		in.close();
	}
	public void printAdjMatrix(){
		Integer[][] adjMatrix = new Integer[totalVertex][totalVertex];
		for (int i = 0; i < totalVertex; i++) {
			for (int j = 0; j < totalVertex; j++) { 
				adjMatrix[i][j] = 0;
			}
		}
		Iterator<LinkedList<Integer>> it = adjList.iterator();
		int n = 0;
		while (it.hasNext()) {
			LinkedList<Integer> Lk = it.next();
			Iterator<Integer> itt = Lk.iterator();
			while (itt.hasNext()) {
				adjMatrix[n][itt.next()] = 1;
			}
		    n++;
		}
		for (int k = 0; k < totalVertex; k++) {
			for (int l = 0; l < totalVertex -1; l++) {
				System.out.print(adjMatrix[k][l] + " ");
			}
			System.out.println(adjMatrix[k][totalVertex-1]);
		}
		//complete the following
		
	}
}

//change class name GraphRepresentation to Main() for submission to AIZU
public class Main {
	public static void main(String argv[]) {
		Graph g = new Graph();
		g.loadAdjList();
		g.printAdjMatrix();
	}
}


Measured memory_bytes: 32512
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin>>n;
    
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    
    int ans=0;
    while(1){
        int count=0;
        for(int i=0;i<n;i++){
            if(a[i]%2==0)count++;
        }
        if(count==n){
            for(int i=0;i<n;i++){
                a[i]/=2;
            }
            ans++;
        }else{
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
#define ll long long

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> P(N);
	int a=0, b=0, c=0;
	for(int i=0; i<N; i++) {
	   cin >> P[i];
	   if(P[i] <= A) a++;
	   else if(P[i] <= B) { b++; }
	   else { c++; }
	}
	cout << min(a, min(b, c)) << endl;
	return 0;
}

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

int p[250001], n;
int g[500][500];
int visited[250000];

int main() {
  int ans = 0;
  queue<pair<int, int> > q;
  cin >> n;
  for (int i = 0; i < n * n; i++) {
    cin >> p[i];
    p[i]--;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      g[i][j] = 1000;
      g[i][j] = min(g[i][j], i);
      g[i][j] = min(g[i][j], j);
      g[i][j] = min(g[i][j], n - 1 - i);
      g[i][j] = min(g[i][j], n - 1 - j);
    }
  }
  for (int i = 0; i < n * n; i++) {
    int x = p[i] / n;
    int y = p[i] % n;
    visited[p[i]] = 1;
    if (x != 0) {
      g[x][y] = min(g[x][y], g[x - 1][y] + 1 - visited[x * n + y - n]);
    }
    if (x != n - 1) {
      g[x][y] = min(g[x][y], g[x + 1][y] + 1 - visited[x * n + y + n]);
    }
    if (y != 0) {
      g[x][y] = min(g[x][y], g[x][y - 1] + 1 - visited[x * n + y - 1]);
    }
    if (y != n - 1) {
      g[x][y] = min(g[x][y], g[x][y + 1] + 1 - visited[x * n + y + 1]);
    }
    ans += g[x][y];
    if (x != 0 && g[x - 1][y] > g[x][y]) {
      g[x - 1][y] = g[x][y];
      q.push({x - 1, y});
    }
    if (x != n - 1 && g[x + 1][y] > g[x][y]) {
      g[x + 1][y] = g[x][y];
      q.push({x + 1, y});
    }
    if (y != 0 && g[x][y - 1] > g[x][y]) {
      g[x][y - 1] = g[x][y];
      q.push({x, y - 1});
    }
    if (y != n - 1 && g[x][y + 1] > g[x][y]) {
      g[x][y + 1] = g[x][y];
      q.push({x, y + 1});
    }
    while (!q.empty()) {
      x = q.front().first;
      y = q.front().second;
      q.pop();
      if (x != 0 && g[x - 1][y] > g[x][y] + 1 - visited[x * n + y]) {
        g[x - 1][y] = g[x][y] + 1 - visited[x * n + y];
        q.push({x - 1, y});
      }
      if (x != n - 1 && g[x + 1][y] > g[x][y] + 1 - visited[x * n + y]) {
        g[x + 1][y] = g[x][y] + 1 - visited[x * n + y];
        q.push({x + 1, y});
      }
      if (y != 0 && g[x][y - 1] > g[x][y] + 1 - visited[x * n + y]) {
        g[x][y - 1] = g[x][y] + 1 - visited[x * n + y];
        q.push({x, y - 1});
      }
      if (y != n - 1 && g[x][y + 1] > g[x][y] + 1 - visited[x * n + y]) {
        g[x][y + 1] = g[x][y] + 1 - visited[x * n + y];
        q.push({x, y + 1});
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 6536
#include <iostream>

int main() {
    int a[5], k;
    std::cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
    std::cin >> k;
    bool flag = true;

    for(int i = 1; i < 5; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i] - a[j] > k) {
                flag = false;
            }
        }
    }

    if(flag) {
        std::cout << "Yay!" << std::endl;
    } else {
        std::cout << ":(" << std::endl;
    }
}


Measured memory_bytes: 256
def findSumDigits(n: int)->int:
    sum_digits = 0
    while n > 0: 
        sum_digits += n % 10
        n //= 10
    return sum_digits
  
N = int(input())
f_x = findSumDigits(N)
if N % f_x == 0: 
	print("Yes")
else:
	print("No")

Measured memory_bytes: 2940
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 1
    for ai in a:
        ans *= ai
        if ans == 0:
            print(0)
            exit()
        elif ans > 10 ** 18:
            print(-1)
            exit()
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 85832
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n;

	scanf("%d", &n);
	
	printf("%.8lf", (double)(n / 2 + n % 2) / (double)n);

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;

int N, Q, query;
string S;
vector<set<int>> st(26);

int main() {
    cin >> N;
    cin >> S;
    cin >> Q;


    for (int i = 0; i < N; i++) {
        char c = S[i];
        st[c-'a'].insert(i);
    }


    for (int i = 0; i < Q; ++i) {
        cin >> query;

        if (query == 1) {
            int cidx;
            char c;
            cin >> cidx >> c;
            cidx--;
            for (int i = 0; i < 26; ++i) {
                st[i].erase(cidx);
            }
            st[c-'a'].insert(cidx);
        }

        else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            int count = 0;
            for (int i = 0; i < 26; ++i) {
                auto itr=st[i].lower_bound(l);
                if (itr != st[i].end() && *itr <= r) count++;
            }
            cout << count << endl;
        }
    }
}

Measured memory_bytes: 26244
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=1 ; i<=(n) ; ++i)
typedef long long ll;
using namespace std;
const ll MAX = 2500LL;
typedef pair <ll, ll> P;

int main(){
  int k;
  string s;
  cin >> k >> s;
  if(s.size()<=k) cout << s << endl;
  else cout << s.substr(0,k) << "..." << endl;
  return 0;
}


Measured memory_bytes: 3588
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << endl; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "tmp.cpp"

int anc(int u, int deg, const vector<vi> &doubling) {
  int cur = u;
  int cnt = 0;
  while (deg > 0) {
    if (cur == -1)
      break;
    if (deg % 2 == 1) {
      cur = doubling[cnt][cur];
    }
    cnt++;
    deg /= 2;
  }
  return cur;
}

int length(int n, int u, const vector<vi> &doubling) {
  int ok = 0;
  int ng = n;
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (anc(u, mid, doubling) != -1) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  return ok;
}

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

  int n;
  cin >> n;
  int log_n = ceil(log2(n) + 1);
  vector<vi> doubling(log_n, vi(n, 0));
  doubling[0][0] = -1;
  REP(i, n) {
    int k;
    cin >> k;
    REP(j, k) {
      int c;
      cin >> c;
      doubling[0][c] = i;
    }
  }

  REP(k, log_n - 1) {
    REP(i, n) {
      if (doubling[k][i] == -1) {
        doubling[k + 1][i] = -1;
      } else {
        doubling[k + 1][i] = doubling[k][doubling[k][i]];
      }
    }
  }

  int q;
  cin >> q;
  REP(i, q) {
    int u, v;
    cin >> u >> v;
    int lu = length(n, u, doubling), lv = length(n, v, doubling);
    if (lu > lv) {
      u = anc(u, lu - lv, doubling);
    } else {
      v = anc(v, lv - lu, doubling);
    }

    int ok = n;
    int ng = -1;
    while (abs(ok - ng) > 1) {
      int mid = (ok + ng) / 2;
      // cout << u MM mid MM anc(u, mid, doubling) << endl;
      // cout << v MM mid MM anc(v, mid, doubling) << endl;
      if (anc(u, mid, doubling) == anc(v, mid, doubling)) {
        ok = mid;
      } else {
        ng = mid;
      }
    }
    cout << anc(u, ok, doubling) << endl;
  }
  return 0;
}



Measured memory_bytes: 10468
#include<iostream>
using namespace std;
int main(){
    int a, n;
    n = 1;
    
    while (n <= 10000){
        cin >> a;
        if (a == 0) break;
        cout << "Case" << " " << n << ":" << " " << a << endl;
        n += 1;
        a = 0;
    }
    
    return 0;
}


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

void solve(long long N, std::vector<long long> P) {
  // solver code

  int cnt = 1;
  int min = P[0];

  for (int i = 1; i < N; i++) {
    if (min > P[i]) {
      min = P[i];
      cnt++;
    }
  }

  cout << cnt << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> P(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &P[i]);
  }
  solve(N, std::move(P));
  return 0;
}


Measured memory_bytes: 1792
s = input()

lis = list(s)
lis.reverse()

rs = "".join(lis)

ans = len(s)


for i in range(len(s)):

    if s[i] == "A":

        ans -= i
        break

for i in range(len(rs)):

    if rs[i] == "Z":

        ans -= i
        break

print (ans)


Measured memory_bytes: 4968
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<deque>
#include<bitset>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
template<class T> inline bool chmax(T&a , T b){ if(a<b){ a=b; return true; } else{ return false; } }
template<class T> inline bool chmin(T&a , T b){ if(a>b){ a=b; return true; } else{ return false; } } 

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main(){
    ll x;
    cin >> x;
    ll n = 100;
    ll cnt=0;
    while(n<x){
        n = n + n/100;
        cnt++;
    }
    cout << cnt << endl;
}

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

int main() {
  int n;
  cin >>n;
  
  int count=0;
  
  for(int i=1; i<=n;i++){
    int tmp=0;
    for(int j=1; j<=i;j++){
 	   if(j%2==1 && i%j ==0)
  	    tmp++;
    }
    if(tmp==8) count++;
  }
  cout << count <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int dx[9] = {-2, -2, -2, -1, -1, -1, 0, 0, 0};
int dy[9] = {-2, -1,  0, -2, -1,  0,-2,-1, 0};
LL res[10];
int H,W,N;

map<pair<int,int>, int> mp;

int main()
{
    ios::sync_with_stdio(false);
    cin >> H >> W >> N;
    res[0] = (LL)(H-2)*(LL)(W-2);
    int u,v,tx,ty;
    for(int i = 0; i < N; ++i)
    {
        cin >> u >> v;
        for(int k = 0; k < 9; ++k)
        {
            tx = u + dx[k];
            ty = v + dy[k];
            if(tx < 1 || ty < 1 || tx > H-2 || ty > W-2) continue;
            mp[make_pair(tx,ty)]++;
        }
    }

    for(pair<pair<int,int>,int> pa : mp)
    {
        --res[0];
        ++res[pa.second];
    }
    for(int i = 0; i <= 9; ++i)
        cout << res[i] <<endl;
    return 0;
}


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

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

using ll = long long int;
const ll MOD = 1e9 + 7;

template<long long int P>
struct _mint {
  long long int x;
  _mint(long long int x = 0): x((x % P + P) % P) {}

  _mint operator-() const {
    return _mint(-x);
  }

  _mint& operator+=(const _mint a) {
    if((x += a.x) >= P) {
      x -= P;
    }
    return *this;
  }
  _mint& operator-=(const _mint a) {
    if((x += P - a.x) >= P) {
      x -= P;
    }
    return *this;
  }
  _mint& operator*=(const _mint a) {
    (x *= a.x) %= P;
    return *this;
  }
  _mint& operator/=(const _mint a) {
    return (*this) *= a.inv();
  }

  _mint operator+(const _mint a) const {
    _mint res(*this);
    return res += a;
  }
  _mint operator-(const _mint a) const {
    _mint res(*this);
    return res -= a;
  }
  _mint operator*(const _mint a) const {
    _mint res(*this);
    return res *= a;
  }
  _mint operator/(const _mint a) {
    _mint res(*this);
    return res /= a;
  }

  _mint pow(long long int t) const {
    if(! t) return 1;
    _mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }

  // for prime P
  _mint inv() const {
    return pow(P - 2);
  }
};
using mint = _mint<MOD>;

int main() {
  int N, K;
  std::cin >> N >> K;

  mint ans = {0};
  std::vector<mint> cnt(K + 1);
  for(int X = K; X >= 1; --X) {
    cnt[X] = mint(K / X).pow(N);
    int k = 2;
    while(k * X <= K) {
      cnt[X] -= cnt[k * X];
      ++k;
    }
    ans += cnt[X] * X;
  }

  std::cout << ans.x << '\n';
}


Measured memory_bytes: 4052
import math
n, m  = map(int, input().split())
A = []
for i in range(n):
    a = list(map(int, input().split()))
    A.append(a)
B = []
for j in range(m):
    b = int(input())
    B.append(b)

C = []
for i in range(n):
    for j in range(m):
        c = A[i][j]*B[j]
        C.append(c)
        
d = math.ceil(len(C)/n)
r = [C[x: x+d] for x in range(0,len(C),d)]

for i in range(len(r)):
    s = sum(r[i])
    print(s)


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

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

ll N;




int main(){
    scanf("%lld", &N);
    printf("%lld", N / 2 - 1 + N % 2);

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	long long n,a,b;
	scanf("%lld%lld%lld",&n,&a,&b);
	if(a%2==b%2)
		printf("%lld",(b-a)/2);
	else
		printf("%lld",(b-a)/2+min(a-1,n-b)+1);
	return 0;
}


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

ll dpow(int a){
  ll k=1;
  for(int i=0;i<a;i++){
    k*=2;
  }
  return k;
}

int main(){
  ll N,P;cin >> N >> P;
  vector<ll> Bi(N);
  ll odd=0,even=0;
  for(int i=0;i<N;i++){
    cin >> Bi.at(i);
    if(Bi.at(i)%2){
      odd++;
    }else{
      even++;
    }
  }
  ll ans=0;
  if(odd==0){
    if(P){
      ans=0;
    }else
      ans=1;
  }else{
    ans=dpow(odd-1);
  }
  for(int i=0;i<even;i++){
    ans*=2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n;
    cin >> n;
    bool flag=false;
    rep2(i, 1, 10){
        rep2(j, 1, 10){
            if(i*j==n){
                cout << "Yes" << endl;
                flag = true;
                break;
            }
        }
        if(flag){
            break;
        }
    }
    if(!flag){
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3576
//@source : 
//@create : 19:00:59 Sunday 05/07/2020
//@author : nghethuat102
//@status : 
#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
template<typename T> void write(const T&x) { cout << x; }
template<typename T, typename... Args> void write(const T&x, Args... args) { cout << x; write(args...); }
template<typename... Args> void writeln(Args... args) { write(args..., "\n"); }
template<typename T> void read(T&x) { cin >> x; }
template<typename T, typename... Args> void read(T&x, Args&... args) { cin >> x; read(args...); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << "\n"; err(++it, args...); }

void solve() {
    int n;
    read(n);
    if (n % 1000 == 0) {
        writeln("0");
        return;
    }
    writeln(1000 - n % 1000);
}

int main() {
    fastio();
    int t = 1;
    for (int it = 1; it <= t; ++it) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3644
N = int(input())
abc=[list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
    dp[i+1][0] = max(dp[i][1], dp[i][2]) + abc[i][0]
    dp[i+1][1] = max(dp[i][0], dp[i][2]) + abc[i][1]
    dp[i+1][2] = max(dp[i][0], dp[i][1]) + abc[i][2]

print(max(dp[-1]))

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if (A == B){
    if (A != C){
      cout << "Yes";
    }
    else {
      cout << "No";
    }
  }
  else if (A != B){
    if (A == C){
      cout << "Yes";
    }
    else if (B == C){
      cout << "Yes";
    }
    else {
      cout << "No";
    }
  }

}


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

public class Main {
    static class Fast {
        BufferedReader br;
        StringTokenizer st;

        public Fast() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String args[]) throws Exception {
        Fast in = new Fast();
        int n = in.nextInt();
        int arr[][]=new int[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j <n; j++) {
                arr[i][j]=in.nextInt();
            }
        }
        for (int i = 0; i <n-1; i++) {
            arr[0][i+1]=arr[0][i+1]+arr[0][i];
        }
        arr[1][0]+=arr[0][0];
        int ans=0;
        for (int i = 1; i <n; i++) {
            arr[1][i]+=Math.max(arr[0][i],arr[1][i-1]);
        }
        System.out.println(arr[1][n-1]);

    }
}






Measured memory_bytes: 21204
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int mod = 1000000007;

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

    vi r(q), l(q);
    rep(i, q){
        cin >> l[i] >> r[i];
    }

    //p[i]: iが素数かどうかを0・1で格納
    vi p(100100, 1);
    p[0] = 0; p[1] = 0;
    rrep(i, 100000){
        if(p[i]==0) continue;
        int j=i+i;
        while(j <= 100000){
            p[j] = 0;
            j += i;
        }
    }

    //like[i]: iが2017likeかどうか
    vi like(100100, 0);
    rrep(i, 100000){
        if(p[i]==1 && p[(i+1)/2]==1) like[i] = 1;
    }

    //累積和
    vi like_sum(100100, 0);
    rrep(i, 100000){
        like_sum[i] = like_sum[i-1] + like[i];
    }

    rep(i, q){
        cout << like_sum[r[i]] - like_sum[l[i]-1] << endl;
    }

    /*
    rep(i, 10){
        printf("i:%d\n", i);
        printf("p:%d\n", p[i]);
        printf("like:%d\n", like[i]);
        printf("like_sum:%d\n\n", like_sum[i]);
    }
    */

    return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define AB_BHI_NI_DEGI                \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
int mod = 1e9 + 7;
//int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

void solve()
{
    int n;
    cin >> n;
    vector<P> v;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        v.pb({x, y});
    }
    for (int i = 0; i + 3 <= n; i++)
    {
        if (v[i].F == v[i].S and v[i + 1].F == v[i + 1].S and v[i + 2].F == v[i + 2].S)
        {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}
int32_t main()
{
    AB_BHI_NI_DEGI
    int Test = 1;
    //cin >> Test;
    //init();
    while (Test--)
        solve();
    return 0;
}
/*

*/

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:
ll n;
const int limit = 200010;
ll a[limit];

int main(void){
	cin >> n;
	rep(i,n) cin >> a[i];
	rep(i,n) a[i] -= i + 1;
	sort(a, a + n);

	ll ans = 0LL;
	rep(i,n) ans += abs(a[i] - a[n/2]);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> int_pair;
typedef pair<ll,ll> ll_pair;
#define pb push_back
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const int N=100;
const int W=10000;


ll partition(vector<ll> &a,ll p,ll r){
	ll x = a[r];
	ll i = p - 1;
	FOR(j,p,r){
		if(a[j]<=x){
			i = i+1;
			swap(a[i],a[j]);
		}	
	}
	swap(a[i+1],a[r]);
	return i+1;
}

int main(){
	ll n;
	cin>>n;
	vector<ll> a;
	FOR(i,0,n){
		ll k;
		cin>>k;
		a.pb(k);
	}
	ll i = partition(a,0,a.size()-1);
	FOR(j,0,a.size()){
		if(i==j){
			cout<<"["<<a[j]<<"]";
		}else{
			cout<<a[j];
		}
		if(j!=a.size()-1)cout<<" ";
	}
	cout<<endl;
}


Measured memory_bytes: 3944
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int k = sc.nextInt();
    int jibun = a;
    int aite = b;
    int tmp = -1;
    for (int i = 0; i < k; i++) {
      if (jibun % 2 == 1) {
        jibun--;
      }
      aite += (jibun / 2);
      jibun /= 2;
      tmp = jibun;
      jibun = aite;
      aite = tmp;
    }
    if (k % 2 == 0) {
      System.out.println(jibun + " " + aite);
    } else {
      System.out.println(aite + " " + jibun);
    }
  }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main() 
{
  int n, m, ans = 0; cin >> n >> m;
  vector<pair<int, int>> v(m);
  rep(i, m) cin >> v[i].first >> v[i].second;
  vector<int> t(n+1, 0);
  rep(i, m){
    t[v[i].first-1] += 1;
    t[v[i].second] -= 1;
  }
  vector<int> sum(n+2);
  rep(i, n){
    sum[i+1] = t[i]+sum[i];
    if(sum[i+1] == m)ans++;
  }
  cout << ans << endl;
  system("pause");
}

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

int main(){
	int n, y;
  	cin >> n >> y;
  	for (int a = 0; a <=n; a++){
    	int tmp = y - 9000 * a - 1000 * n;
      	if (tmp % 4000 != 0)
        	continue;
      	int b = tmp / 4000;
      	if (0 <= b and b <= n - a){
        	printf("%d %d %d\n", a, b, n - (a + b));
          	return 0;
        }
    }
  	printf("%d %d %d\n", -1, -1, -1);
}

Measured memory_bytes: 256
#include <cstdio>

int main(){
    int A,B;
    scanf("%d %d",&A,&B);
    int a[3] = {A + B,A - B,A * B};
    int max = a[0];
    for(int i = 1; i < 3; i++){
        if(max < a[i]){
            max = a[i];
        }
    }
    printf("%d\n",max);

    return 0;
}

Measured memory_bytes: 128
X = input()
flag = ['+','-']
check = 0
for i in flag:
    if check == 1:
        break
    for j in flag:
        if check == 1:
            break
        for k in flag:
            ans = 0
            if i == '+':
                ans = int(X[0]) + int(X[1])
            else:
                ans = int(X[0]) - int(X[1])
            if i == '+':
                ans = int(X[0]) + int(X[1])
            else:
                ans = int(X[0]) - int(X[1])
            if j == '+':
                ans += int(X[2])
            else:
                ans -= int(X[2])
            if k == '+':
                ans += int(X[3])
            else:               
                ans -= int(X[3])
            if ans == 7:
                anslist = [X[0],i,X[1],j,X[2],k,X[3],'=','7']
                check = 1
print(''.join(anslist))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
#define LL long long

void _131() {
    int n;
    cin >> n;
    int tmp_a, tmp_b;
    vector<pair<int, int> > data;
    for (int i = 0; i < n; ++i) {
        cin >> tmp_a >> tmp_b;
        data.push_back(make_pair(tmp_b, tmp_a));
    }

    sort(data.begin(), data.end());

    LL sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += data[i].second;
        // cout << sum << " " << data[i].first << endl;
        if (sum > data[i].first) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

void print_result(int length, int* result) {
    for (int i = 0; i < length; ++i) {
        cout << result[i];
        if (i != length - 1) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
}

void _136() {
    string s;
    cin >> s;

    int result[100000] = {0};
    string::size_type pos;
    // LL times = (LL)pow((LL)10, 100);
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'R') {
            pos = s.substr(i).find("RL");
            // cout << pos << endl;
            if (pos % 2 == 0) {
                result[i + pos]++;
            } else {
                result[i + pos + 1]++;
            }
        } else {
            // pos = s.substr(0, i).rfind("RL");
            pos = s.rfind("RL", i);
            // cout << pos << endl;
            if ((i - pos) % 2 == 0) {
                result[pos]++;
            } else {
                result[pos + 1]++;
            }
        }
        // print_result(s.length(), result);
    }

    print_result(s.length(), result);
}

void __136() {
    string s;
    cin >> s;

    int result[100000] = {0};

    string::size_type pos = 0;
    vector<int> rl_position;
    pos = s.find("RL", pos);
    while (pos != string::npos) {
        rl_position.push_back(pos);
        pos = s.find("RL", pos + 1);
    }

    int rl_index = 0;
    int next_rl_position = rl_position[rl_index];
    for (int i = 0; i < s.length(); ++i) {
        // cout << i << endl;
        if (s[i] == 'R') {
            if ((i != 0) &&(s[i - 1] == 'L')) {
                rl_index++;
                next_rl_position = rl_position[rl_index];
            }

            if ((next_rl_position - i) % 2 == 0) {
                result[next_rl_position]++;
            } else {
                result[next_rl_position + 1]++;
            }
        } else {
            if ((i - next_rl_position) % 2 ==0) {
                result[next_rl_position]++;
            } else {
                result[next_rl_position + 1]++;
            }
        }
    }

    print_result(s.length(), result);
}

int main()
{
    __136();
    return 0;
}



Measured memory_bytes: 1280
#include <iostream>
#include <string>


using namespace std;

int main(){
	int n,m;
	string *u,*t;

	cin>>n;
	u = new string [n];

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

	cin>>m;
	t = new string [m];
	for(int i=0;i<m;i++)cin>>t[i];

	int state=0;
	int flag=0;

	for(int i=0;i<m;i++){
		flag=0;
		for(int j=0;j<n;j++){
			if(t[i] == u[j]){
				flag=1;
				if(state==0){
					cout<<"Opened by "<<t[i]<<endl;
				}
				else{
					cout<<"Closed by "<<t[i]<<endl;
				}
				state++;
				state%=2;
				break;
			}
		}
		if(flag==0){
			cout<<"Unknown "<<t[i]<<endl;
		}
	}

	return 0;
}

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

int main() {
	int n, m, s, c;
	int num[3] = { 0 };
	vector<bool> check(3, true);
	bool out = false;

	cin >> n >> m;
	if (n == 3)num[2] = 1;
	if (n == 2)num[1] = 1;

	for (int i = 0; i < m; i++) {
		cin >> s >> c;
		if (n >=2 && s == 1 && c == 0)out = true;
		if (check.at(n - s) || num[n - s] == c) {
			num[n - s] = c;
			check.at(n - s) = false;
		}else out = true;
	}

	
	if (!out)cout << 100 * num[2] + 10 * num[1] + num[0] << endl;
	else cout << -1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int64_t N, sum = 0;
    cin >> N;
    vector<int64_t> A(N);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A.at(i) = a - (i + 1);
    }
    sort(ALL(A));
    for (int i = 0; i < N; i++) {
        sum += abs(A.at(i) - A.at(((N - 1) / 2)));
    }
    cout << sum << endl;

}


Measured memory_bytes: 1792
n=int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans=0
l=len(factorization(n))
s=factorization(n)
for i in range(l):
    for j in range(1,1000):
        if s[i][1]>=j:
            ans+=1
            s[i][1]-=j
        else:
            break
if n==1:
    print(0)
else:
    print(ans)


Measured memory_bytes: 63348
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  int N=S.size();
  int64_t Q=1000000007;
  int64_t A=0,B=0,C=0,D=1;
  for(int i=0;i<N;i++){
    if(S[i]=='A'){
      A+=D;
    }
    else if(S[i]=='B'){
      B+=A;
    }
    else if(S[i]=='C'){
      C+=B;
    }
    else{
      C=3*C+B;
      B=3*B+A;
      A=3*A+D;
      D*=3;
    }
    A%=Q;
    B%=Q;
    C%=Q;
    D%=Q;
  }
  cout<<C<<endl; 
}

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

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

    int ans = 0;
    for (int i = 0; i < 3; i++)
    {
        if (s[i] == t[i]) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <string>
using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int n, k, c;
    cin >> n >> k >> c;
    cin >> s; s = "o" + s;
    vector<int> dpl(n + 2, 0), dpr(n + 2, 0);
    for(int i = 1; i <= n; i++) {
        dpl[i] = dpl[i - 1];
        if(s[i] == 'o') {
            dpl[i] = max(dpl[i], dpl[max(0, i - c - 1)] + 1);
        }
    }
    for(int i = n; i > 0; i--) {
        dpr[i] = dpr[i + 1];
        if(s[i] == 'o') {
            dpr[i] = max(dpr[i], dpr[min(i + c + 1, n + 1)] + 1);
        } 
    }
    //for(int i = 1; i <= n; i++) cout << dpl[i] << " \n"[i == n];
    //for(int i = 1; i <= n; i++) cout << dpr[i] << " \n"[i == n];
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'o' && dpl[max(0, i - c - 1)] + dpr[min(i + c + 1, n + 1)] == k - 1) {
            ans.push_back(i);
            //cout << i << '\n';
        }
    }
    //cout << "---------------------------------\n";
    for(int i = 0; i < (int)ans.size(); i++) {
        if(i > 0 && ans[i] - ans[i - 1] <= c) continue;
        if(i < (int)ans.size() - 1 && ans[i + 1] - ans[i] <= c) continue;
        cout << ans[i] << '\n';
    }    
    return 0;
}

Measured memory_bytes: 4556
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

LL n, x, m;

LL fp(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
const int N = 1e5 + 3;
int p[N];
LL a[10 * N];
LL s[10 * N];
#include <cstring>
signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);


    cin >> n >> x >> m;
    a[1] = s[1] = x;
    memset(p, -1, sizeof p);
    LL ans = 0;
    ans = x;
    for (int i = 2; i <= n; i++) {
        if (i > 10 * N) throw;
        a[i] = a[i - 1] * a[i - 1] % m;
        s[i] = a[i] + s[i - 1];
        if (~p[a[i]]) {
            int l = i - p[a[i]];
            LL x = n - i + 1;
            LL t = x / l;
            LL sl = s[i - 1] - s[p[a[i]] - 1];
            LL r = x % l;
            ans += sl * t;
            ans += s[p[a[i]] + r - 1] - s[p[a[i]] - 1];
            cout << ans << endl;
            return 0;
        }
        p[a[i]] = i;
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4764
let break p lst =
  let rec doit acc = function
    | [] -> (List.rev acc, [])
    | x :: xs as l ->
      if p x then (List.rev acc, l)
      else doit (x :: acc) xs in
  doit [] lst

let split_n n lst =
  let rec doit n acc l =
    if n = 0 then (List.rev acc, l)
    else
      match l with
      | [] -> assert false
      | hd :: tl -> doit (n - 1) (hd :: acc) tl in
  doit n [] lst

let make_postorder preorder inorder =
  let rec doit = function
    | ([], []) -> []
    | ([], _) -> assert false
    | (x :: xs, ys) ->
        begin match break (fun e -> e = x) ys with
        | (_, []) -> assert false
        | (yl, _ :: yr) ->
          let (xl, xr) = split_n (List.length yl) xs in
          doit (xl, yl) @ doit (xr, yr) @ [x]
        end in
  doit (preorder, inorder)

let () =
  let n = read_int () in
  let rec read_tree i acc =
    if i = n then List.rev acc
    else read_tree (i + 1) ((Scanf.scanf "%d " (fun i -> i)) :: acc) in
  let read_tree i = read_tree i [] in
  let preorder = read_tree 0 in
  let inorder = read_tree 0 in
  make_postorder preorder inorder
  |> List.iteri (fun i e -> if i <> 0 then print_string " "; print_int e);
  print_newline ()

Measured memory_bytes: 2428
def m_dist p,c
  
  ( p[0] - c[0] ).abs + ( p[1] - c[1] ).abs 
  
end

N, M = gets.split.map(&:to_i)

pps = []
cps = [] # people points, check points
N.times{ pps.push( gets.split.map(&:to_i) ) }
M.times{ cps.push( gets.split.map(&:to_i) ) }

ans = 0

pps.each do |p|
  min = (10**8)*4
  cps.each_with_index do |c,i|
    
    m = m_dist(p,c)
    if min > m
      min = m
      ans = i
    end
  end
  puts ans + 1
end


Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N,sum;
  cin >> N;
  sum=0;
  rep(i,N){
    int l, r ;
    cin >> l >> r;
    sum+=(r-l+1);
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 10005;
const int mod = 998244353;

int x,y,n;char a[maxn],b[maxn];
int fac[maxn],inc[maxn];
int dp[maxn][maxn],ans;

LL comb(int n,int m) {
	return (LL)fac[n]*inc[m]%mod*(LL)inc[n-m]%mod;
}
LL fpm(LL p,LL k) {
	LL res=1ll;
	while (k) {
		if (k&1) (res*=p)%=mod;
		(p*=p)%=mod;k>>=1;
	}
	return res;
}

int main()
{
	#ifdef Amberframe
		freopen("agc019e.in","r",stdin);
		freopen("agc019e.out","w",stdout);
	#endif
	scanf("%s %s",a+1,b+1);n=strlen(a+1);
	for (int i=1;i<=n;i++)
		x+=(a[i]=='1'&&b[i]=='1'),
		y+=(a[i]=='0'&&b[i]=='1');
	
	fac[0]=inc[0]=1;
	for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%mod;
	inc[n]=fpm(fac[n],mod-2);
	for (int i=n;i>=2;i--) inc[i-1]=(LL)inc[i]*i%mod;
	dp[0][0]=1;
	
	for (int j=1;j<=n;j++) dp[0][j]=(LL)fac[j]*fac[j]%mod;
	for (int i=1;i<=x;i++)
	for (int j=1;j<=y;j++)
		dp[i][j]=((LL)dp[i-1][j]*i+(LL)dp[i][j-1]*j)*j%mod;
	for (int t=0;t<=x;t++)
		ans=(ans+(LL)dp[x-t][y]*dp[0][t]%mod*comb(x,t)%mod*comb(x+y,t))%mod;
	printf("%d",ans);
	return 0;
}

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


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 5e5 + 1;                                          
const int M = 22;
const int pri = 997;
const int Magic = 801;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int n, cnt[4];
int main () {
    cin >> n;
    For (i, 1, n) {
        int x;
        cin >> x;
        cnt[x % 4] ++;
    }
    
    int zt = n - cnt[2];
    if ((zt + (cnt[2] > 0)) / 2 > cnt[0]) cout << "No";
    else cout << "Yes";
}

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

int main() {


    int n,i,j,c=0;
    cin >> n;
    int a[n];
    for(i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(i=1;i<=n;i++)
    {
       if(a[i] != i)
       {
           c++;
       }

    }
    if(c>2)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
    }




  return 0;

}







Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int a[10];
	for (int i = 0; i < 10; i++){
		cin >> a[i];
	}
	sort(a, a+10, less<int>());
	cout << a[9] << endl;
	cout << a[8] << endl;
	cout << a[7] << endl;
}

Measured memory_bytes: 1176
#include <iostream>

using namespace std;

int SelectionSort(int A[], int N){
  int minj, tmp, cnt=0;

  for(int i = 0; i < N-1; i++){
    minj = i;
    for(int j = i; j < N; j++){
      if(A[j] < A[minj]){
	minj = j;
      }
    }
    tmp = A[i];
    A[i] = A[minj];
    A[minj] = tmp;
    if(i != minj) cnt++;
  }

  return cnt;
}

int main(){
  int A[100], N, cnt;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  cnt = SelectionSort(A, N);

  cout << A[0];
  for(int i = 1; i < N; i++){
    cout << " " << A[i];
  }
  cout << endl << cnt << endl;
  
  return 0;
}



Measured memory_bytes: 3088
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] s = new long[n+1];
        s[0] = 0;
        for (int i=1;i<=n;i++){
            s[i]=s[i-1]+sc.nextLong();

        }
        Arrays.sort(s);
        long count = 1;
        long ans = 0;
        for (int i=0;i<n;i++){
            while (i<n&&s[i]==s[i+1]){
                i++;
                count++;
            }
            ans+=combination(count,2);
            count=1;
        }
        System.out.println(ans);
    }
    static long factorial(long num){
        if (num<2)return 1;
        else return num*factorial(num-1);
    }
    static int arraySum(int[] array){
        int ans = 0;
        for (int value : array) ans += value;
        return ans;
    }
    static long combination(long a, long b){
        long data = 1;
        for (int i=0;i<b;i++){
            data*=a-i;
        }
        return data/factorial(b);
    }
    static double log(double base,double antilogarithm){
        return Math.log(antilogarithm)/Math.log(base);
    }
}


Measured memory_bytes: 61676
n, k = gets.split.map(&:to_i)
hs = n.times.map { gets.to_i }.sort!

ans = (10 ** 9) - 1
(n - k + 1).times do |i|
  diff = hs[i + k - 1] - hs[i]
  ans = diff if diff <= ans

  break if ans == 0
end

puts ans


Measured memory_bytes: 4016
#include <cstdio>
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <math.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

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

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

template<class T>
bool umax(T &a, const T &b){
    if (a<b) {
        a=b; return true;
    }
    return false;
}

template<class T>
bool umin(T &a, const T &b) {
    if (b<a) {
        a=b; return true;
    }
    return false;
}

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};
vector<int>G[10010];
vector<int>c(10010,0);
int num[10010];
bool used[10010];
int now_c=0;
int dfs(int s){
    if(used[s]){
        return 0;
    }else{
        used[s]=true;
    }

    num[s]=c[now_c];
    now_c++;

    for(int i=0; i<G[s].size(); i++){
        dfs(G[s][i]);
    }
    return 0;
}

int main() {
    int N; cin >> N;
    vector<int>a(N),b(N);

    rep(i,N){
        cin >> a[i];
        b[i]=a[i];
    }

    sort(b.begin(), b.end(), greater<>());

    rep(i,N){
        if(a[i]==b[0]){
            cout << b[1] << endl;
        }else{
            cout << b[0] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);

using namespace std;
const int N = 1e6 + 4;
const int mod = 1e9 + 7;
const long long INF = 1e18;
const int inf = 1e9;

int main () {
	boost;
	string s, q, w;
	int n;
	cin >> n;
	cin >> s;
	for (int i = 0 ; i < n ; ++ i) {
		if (i < n / 2) q += s[i];
		else w += s[i];
	}
	if (q == w) cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    public static bool f = false, t = true;
    static void Main(string[] args)
    {
        int[] a = new int[26];
        string n = Console.ReadLine();
        for(int i = 0; i < n.Length; i++)
        {
            a[n[i] - 'a']++;
        }
        for(int i = 0; i < 26; i++)
        {
            if (a[i] == 0) { Console.WriteLine((char)(i+'a'));Console.ReadLine(); break; }
            if (i == 25) { Console.WriteLine("None"); }
        }
        
    }

    public static long gcd(long a, long b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static long lcm(long a, long b)
    {
        return a / gcd(a, b) * b;
    }
    public static bool IsPrime(long n)
    {
        if (n < 2) return false;
        if (n == 2) return true;

        for (long i = 2; i < Math.Sqrt(n); i++)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static long Long()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] longs()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
    public static int Int()
    {
        return int.Parse(Console.ReadLine());
    }
    public static int[] ints()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 11232