akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.BitSet;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        MedianSum solver = new MedianSum();
        solver.solve(1, in, out);
        out.close();
    }

    static class MedianSum {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int[] A = new int[N];
            int sum = 0;
            for (int i = 0; i < N; i++) {
                A[i] = in.nextInt();
                sum += A[i];
            }

            BitSet bitSet = new BitSet(sum);
            bitSet.set(sum);
            for (int i = 0; i < N; i++) {
                bitSet.or(bitSet.get(A[i], sum + 1));
            }
            out.println(bitSet.nextSetBit((sum + 1) / 2));

//        boolean[][] F = new boolean[N + 1][sum + 1];
//
//        F[0][0] = true;
//        for (int i = 0; i <= N; i++) F[i][0] = true;
//
//
//        for (int i = 1; i <= N; i++) {
//            for (int s = 1; s <= sum; s++) {
//                F[i][s] |= F[i - 1][s];
//                if (s - A[i - 1] >= 0) F[i][s] |= F[i - 1][s - A[i - 1]];
//            }
//        }
//
//        for (int s = (sum + 1) / 2; s <= sum; s++) {
//            if (F[N][s]) {
//                out.println(s);
//                return;
//            }
//        }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }
}



Measured memory_bytes: 274644
#include <iostream>
#include <cmath>
#include <cstdlib> // rand
#include <cfloat> // DBL_MAX
#include <vector>
#include <algorithm> // sort
#include <utility> // pair

typedef long long ll;
using namespace std;

struct fenwick{
  vector<int> arr;
  fenwick(const int n){
    arr = vector<int> (n,0);
  };

  int lsb(const int i){
    return i & (-i);
  }
  int sum(const int idx){
    ll ret = 0;
    int i=idx;
    while(i>0){
      ret += arr[i-1];
      i -= lsb(i);
    }
    return ret;
  }
  int num(const int idx){
    ll ret=0;
    int i=idx-1, j=idx;
    while(j>i){
      ret += arr[j-1];
      j -= lsb(j); // remove LSB (least significant bit) (-i : !i-1)
    }
    while(i>j){
      ret -= arr[i-1];
      i -= lsb(i);
    }
    return ret;
  }
  void update(const int l, const int r){
    /* TLE, O((r-l)*log M)
    for(int i=l; i<=r; i++){
      int idx = i-1;
      while(idx < arr.size()){
        arr[idx] += 1;
        idx += lsb(idx+1);
      }
      }*/
    int idx = l-1;
    while(idx < arr.size()){
      arr[idx] += 1;
      idx += lsb(idx+1);
    }
    idx = r;
    while(idx < arr.size()){
      arr[idx] -= 1;
      idx += lsb(idx+1);
    }
  }
};

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

  vector<int> ans(M,0);
  vector<pair<int,int> > lr(N);
  for(int i=0; i<N; i++){
    int l,r;
    cin >> l >> r;
    lr[i] = make_pair(l,r);

    // for(int j=1; j<=r; j++){ // naive count (TLE)
    //   if(r-l >= r%j){
    //     ans[j-1] += 1;
    //   }
    // }
  }

  sort(lr.begin(), lr.end(), [](pair<int,int> a, pair<int,int> b)->bool{
      return (a.second-a.first) < (b.second-b.first);
    });

  fenwick fw(M);

  int idx=0;
  for(int d=1; d<=M; d++){
    while(idx<N && lr[idx].second - lr[idx].first + 1 <= d){
      fw.update(lr[idx].first, lr[idx].second);
      idx++;
    }

    ans[d-1] += N-idx; // r-l+1 <= d, always stop
    for(int i=d; i<=M; i+=d){
      // cout << d << " " << fw.sum(i) << " " << i << endl;
      ans[d-1] += fw.sum(i);
    }
  }

  // out
  for(int i=0; i<M; i++){
    cout << ans[i] << endl;
  }

  return 0;
}


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

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;
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;}
const long long INF = 1LL << 60;
typedef pair<int, int> P;


int N, K, Q;

int main() {
    cin >> N >> K >> Q;
    vector<int> B(N,K-Q);
    for (int i = 0; i < Q; i++) {
        int a;
        cin >> a;
        B[a-1]++;
    }
    for (int i = 0; i < N; i++) {
        if (B[i] > 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

}


Measured memory_bytes: 1024
package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)

	left := make([]int, m)
	right := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scanf("%d %d", &left[i], &right[i])
	}

	l, r := left[0], right[0]
	for i := 1; i < m; i++ {
		if r < left[i] || right[i] < l {
			r = 0
			l = 1
			break
		} else if l < left[i] && r < right[i] {
			l = left[i]
		} else if l < left[i] && right[i] < r {
			l = left[i]
			r = right[i]
		} else if left[i] < l && right[i] < r {
			r = right[i]
		}
	}

	fmt.Println(r - l + 1)
}


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

int main() {
  int d, g;
  cin >> d >> g;
  vector<int> p(d);
  vector<int> c(d);
  for (int i = 0; i < d; i++) {
    cin >> p[i];
    cin >> c[i];
  }
  int min_cnt = pow(2, 10);
  for (int i = 0; i < int(pow(2, d)); i++) {
    int sum = 0;
    int cnt = 0;
    for (int j = 0; j < d; j++) {
      if ((i & int(pow(2, j))) == 0) {
        continue;
      };
      sum += ((j + 1) * 100) * p[j] + c[j];
      cnt += p[j];
    }
    // 1. achieve with completion
    if (sum >= g) {
      if (cnt < min_cnt) {
        min_cnt = cnt;
      }
      continue;
    }
    // 2. with additional solve
    for (int j = d - 1; j >= 0; j--) {
      if ((i & int(pow(2, j))) != 0) {
        continue;
      }
      for (int k = 0; k < p[j]; k++) {
        sum += (j + 1) * 100;
        cnt += 1;
        if (sum >= g) {
          break;
        }
      }
      if (sum >= g) {
        if (cnt < min_cnt) {
          min_cnt = cnt;
        }
        break;
      }
    }
  }
  cout << min_cnt << endl;
  return 0;
}

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

int main() {
    string S, T;
    cin >> S >> T;
    int N = S.size(), ans = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] != T[i]) ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3864
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var: ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        p: [usize; n]
    }
    let mut counter = 0;
    for i in 0..p.len() {
        if i + 1 != p[i] {
            counter += 1;
        }
    }
    println!(
        "{}",
        if counter == 0 || counter == 2 {
            "YES"
        } else {
            "NO"
        }
    );
}

Measured memory_bytes: 4476
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main(void){
    int n,W;
    cin >> n >> W;
    long long dp[102][100005];
    long long w,v;
    for(int i=0; i<=n; i++){
    	for(int j=0; j<=W; j++){
        dp[i][j]=0;
        }
    }
    for(int i=1; i<=n; i++){
        cin >> w >> v;
        dp[i][w]=max(dp[i-1][w],v);
        for(int j=0; j<=W; j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
            if(j+w<=W&&dp[i-1][j]!=0)dp[i][j+w]=max(dp[i-1][j+w],dp[i-1][j]+v);
        }
    }
    long long ans=0;
    for(int i=0; i<=W; i++){
        ans=max(ans,dp[n][i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 79616
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 100001
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<int,ll>Pil;
typedef pair<P1,ll> P2;
typedef list<int> li;
typedef list<li> lli;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	ll a;
	int b;
};

int main(){

	string s;
	cin>>s;
	if(s[s.size()-1]=='s')cout<<s<<"es"<<endl;
	else cout<<s<<"s"<<endl;

	return 0;
}


Measured memory_bytes: 3628
s=list(input())

ans=[]
for i in range(len(s)):
    if s[i] == "0":
        ans.append(s[i])
    elif s[i] == "1":
        ans.append(s[i])
    if s[i] == "B" and ans !=[]:
        ans.pop(-1)
    
print(*ans, sep="")
    


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define pf printf
#define sc scanf
#define sf(n) scanf("%d",&n)
#define sff(n1,n2) scanf("%d %d",&n1,&n2)
#define sfff(n1,n2,n3) scanf("%d %d %d",&n1,&n2,&n3)
#define sl(n) scanf("%lld",&n)
#define sll(n1,n2) scanf("%lld %lld",&n1,&n2)
#define slll(n1,n2,n3) scanf("%lld %lld %lld",&n1,&n2,&n3)

signed main(){
    string s, t;
    cin>>s>>t;
    int c=0;
    for(int i=0; s[i]; i++){
        if(s[i]!=t[i]) c++;
    }
    cout<<c<<endl;
}


Measured memory_bytes: 3920
#include <iostream>
#include <stdio.h>
#include <vector>

using std::vector;
using std::cout;
using std::cin;

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

int main() {
    int n;
    float res = 0;
    cin >> n;
    for (int i = 0;i < n; i++) {
        float c;
        std::string str;
        cin >> c >> str;
        if (str == "JPY") {
            res += c;
        } else {
            res += c * 380000.;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
      ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,s;
  cin>>n;
  s=n%10;
  if(s==0 || s==1 || s==6 || s==8)
  cout<<"pon"<<endl;
  else if(s==3)
  cout<<"bon"<<endl;
  else
  cout<<"hon"<<endl;
}

Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main()
{
	string inputStr;		// 入力文字列
	int    strLength = 0;	// 文字列長
	long   sum;				// 合計
	
	while(1)
	{
		sum = 0;
		
		// 数字入力
		getline(cin, inputStr);
		strLength = inputStr.size();
		
		// ゼロのみの入力のときはbreak
		if('0' == inputStr[0])
		{
			break;
		}
		
		// 和の計算
		for(int i = 0; i < strLength; i++)
		{
			sum += inputStr[i] - '0';			// アスキーのゼロをマイナス
		}
		
		cout << sum << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3216
n=int(input())
a=list(map(int,input().split()))
num=[0]*(max(a)+1)
maxa=max(a)
cnt=1

for i in a:
  while 1:
    try:
      num[i*cnt]+=1
      cnt+=1
      
      
    except IndexError:
      break
  cnt=1      

count=0

for i in range(n):
  if num[a[i]]==1:
    count+=1
    
print(count)

Measured memory_bytes: 32000
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        {
            Scanner input = new Scanner(System.in);
            int mis = 0, N;
            N = input.nextInt();

            for(int i = 0; i<N; i++) {
                int cur = input.nextInt();
                if (cur != i+1)
                    mis++;
            }
            String ans = (mis <= 2) ? "YES" : "NO";
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 21844
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

if max(a) < 0:
    a.sort()
    ans = 1
    if k % 2 == 0:
        for e in a[:k]:
            ans *= e
            ans %= mod
    else:
        for e in a[-k:]:
            ans *= e
            ans %= mod

    print(ans)

elif k == n:
    ans = 1
    for e in a:
        ans *= e
        ans %= mod

    print(ans)

else:
    neg = []
    pos = []
    for e in a:
        if e < 0:
            neg.append(e)
        else:
            pos.append(e)

    neg.sort()
    pos.sort(reverse=True)

    ans = 1
    if k % 2:
        ans *= pos.pop(0)
        k -= 1

    nums = [e1 * e2 for e1, e2 in zip(neg[::2], neg[1::2])]
    nums += [e1 * e2 for e1, e2 in zip(pos[::2], pos[1::2])]

    nums.sort(reverse=True)
    for e in nums[:k//2]:
        ans *= e
        ans %= mod

    print(ans)


Measured memory_bytes: 115996
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define MOD 1000000007

using namespace std;
using ll = long long;

int main() {
	string n;
	int ans;
	cin >> n;
	if (n == "SSS") ans = 0;
	else if (n[1] == 'S') ans = 1;
	if (n == "RRR") ans = 3;
	if (n == "SRR" || n == "RRS") ans = 2;
	if (n == "SRS") ans = 1;

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3620
import java.{util => ju}
import scala.collection.{mutable => mu}
import MyPredef._


object Main extends App {
    val H, W = nextInt
    val rows = Array.fill(H)(next)
    println("#"*(W+2))
    rows.foreach(row => println(s"#$row#"))
    println("#"*(W+2))
}

object MyPredef {
  @inline def rep(n: Int, f: => Unit): Unit = { var c = 0; while (c < n) { f; c += 1 } }
  @inline def rep(n: Int, f: Int => Unit): Unit = { var c = 0; while (c < n) { f(c); c += 1 } }

  private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0
  @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
  @inline private def hasNextByte(): Boolean =
    if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true }
  @inline private def hasNext(): Boolean = {
    while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
    hasNextByte()
  }
  @inline private def readByte(): Byte =
    if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 }
  def next(): String = {
    if(!hasNext()) ???
    val sb = new StringBuilder; var b = readByte()
    while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
    sb.toString
  }
  def nextInt(): Int = {
    val n = nextLong()
    if (n < Int.MinValue || Int.MaxValue < n) ???
    n.toInt
  }
  def nextLong(): Long = {
    if(!hasNext()) ???
    var minus = false; var b = readByte()
    if (b == '-') { minus = true; b = readByte() }
    def go (b: Byte, n: Long = 0): Long =
      if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') }
      else if (minus) { -n } else { n }
    go(b)
  }
  def nextDouble(): Double = next.toDouble
}

Measured memory_bytes: 26344
N = int(input())
X = [int(x) for x in input().split(' ')]
Pa = sum(X) // N
Pb = Pa + 1
Ca = Cb = 0
for i in range(N):
  Ca += (X[i] - Pa)**2
  Cb += (X[i] - Pb)**2
print(min(Ca, Cb))

Measured memory_bytes: 38256
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i = (a);i < (n);i++)
typedef unsigned long long ull;
typedef long long ll;
using namespace std;

int main(){
	string s,t,memo = "",ans = "";
	bool flag = true;
	cin >> s >> t;
	
	rep(i,0,s.size()-t.size()+1){
		memo = s;
		if(s[i] == t[0] || s[i] == '?'){
			rep(j,0,t.size()){
				if(s[i+j] == t[j] || s[i+j] == '?'){
					memo[i+j] = t[j];
					if(j == t.size()-1){
						rep(k,0,s.size()){
							if(memo[k] == '?'){
								memo[k] = 'a';
							}
						}
						
						if(flag){
							ans = memo;
						}
						else if(ans > memo){
							ans = memo;
						}
					}
				}
				else{
					memo = "";
					break;
				}
			}
		}
	}
	
	
	if(ans == "") cout << "UNRESTORABLE" << endl;
	else cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  string s;
  cin>>s;
  string t = s;
  reverse(ALL(t));
  REP(i,t.size()){
    if(t[i]=='b')t[i]='d';
    else if(t[i]=='d')t[i]='b';
    else if(t[i]=='p')t[i]='q';
    else if(t[i]=='q')t[i]='p';
  }
  puts(s==t?"Yes":"No");
  return 0;
}


Measured memory_bytes: 512
import Control.Applicative
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- readLn
  unless (n == 0) $ do
    solve <$> replicateM n f >>= mapM_ print
    putStrLn "#"
    main
  where
    f = g <$> words <$> getLine
    g [l, p, a, b, c, d, e, f, s, m] = Crop l (read p) (read a) (read b) (read c) (read d) (read e) (read f) (read s) (read m)

solve :: [Crop] -> [Crop]
solve = sortBy cmp
  where
    g cr = let prft = m cr * f cr * s cr - p cr
               prd = a cr + b cr + c cr + m cr * (d cr + e cr)
           in (prft, prd)
    cmp cr1 cr2 = let (w, x) = g cr1
                      (y, z) = g cr2
                  in if x * y == w * z
                     then compare (l cr1) (l cr2)
                     else compare (x * y) (w * z)
      
data Crop = Crop {l::String, p::Int, a::Int, b::Int, c::Int, d::Int, e::Int, f::Int, s::Int, m::Int}

instance Show Crop where
  show cr = l cr



Measured memory_bytes: 5084
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD  1000000007
#define ll long long
#define int long long 
# define INF 2e5+5
#define ar array
# define fr first
# define sc second
#define wt(x) int x;cin>>x;while(x--)
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
//#define cerr if(false)cerr
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> pbds;

void  c_p_c(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
#ifndef ONLINE_JUDGE
  freopen("input1.txt","r",stdin);
  freopen("output1.txt","w",stdout);
#endif
 }
 
int power(int a,int b,int mod){
    a=a%mod;
    if(a==0){
        return 1;
    }
    int res=1;
    while(b){
        if(b&1){
            res=(res*a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return res;
 }
 
int  MMI(int p){
    return power(p,MOD-2,MOD);
}


int32_t main()
{
    c_p_c();
     int a;
     cin>>a;
     cout<<a+a*a+a*a*a<<"\n";
    
        



         
 
 
    
      return 0;
       
        }
        
        
 
        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
        


Measured memory_bytes: 3604
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int d = 0;

		HashSet<Integer> hs = new HashSet<>();
		for (int i=1; i<n+1; i++) {
			hs.add(i);
	    }

		for (int j=0; j<k; j++) {		
			d = scan.nextInt();
			for (int i=0; i<d; i++) {
				hs.remove(scan.nextInt());
	    	}
	    }
        
		System.out.println(hs.size());
	    scan.close();	
    }
}

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

int main() {
    int N, Q;

    while(cin >> N >> Q, N) {
        vector<int> alive(N);
        iota(alive.begin(), alive.end(), 1);

        int person = 0, alive_cnt = N, game_end = false;
        for(int word=1; word<=Q; word++) {
            string s; cin >> s;

            if(game_end) continue;

            bool ok = true;
            if     (word % 15 == 0) {
                if(s != "FizzBuzz") ok = false;
            }
            else if(word %  3 == 0) {
                if(s != "Fizz"    ) ok = false;
            }
            else if(word %  5 == 0) {
                if(s != "Buzz"    ) ok = false;
            }
            else {
                if(s != to_string(word)) ok = false;
            }

            if(!ok) {
                alive.erase(alive.begin() + person);
                person %= alive.size();
                alive_cnt--;
                if(alive_cnt == 1) game_end = true;
            }
            else {
                person = (person + 1) % alive.size();
            }
        }

        for(size_t i=0; i<alive.size(); i++) {
            cout << alive[i] << " \n"[i+1==alive.size()];
        }
    }
    return 0;
}


Measured memory_bytes: 3176
N = int(input())
arr = list(map(int, input().split()))
ans = 1000
kabu = 0
flg = True
for i in range(N-1):
    if flg and arr[i] < arr[i+1]:
        tmp = ans//arr[i]
        ans -= tmp*arr[i]
        kabu += tmp
        flg = False
    if not flg and arr[i] > arr[i+1]:
        ans += kabu*arr[i]
        kabu = 0
        flg = True
print(ans+kabu*arr[-1])

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m,X,Y; cin>>n>>m>>X>>Y;
	vector<int>x(n),y(m); for(auto&&i:x)cin>>i; for(auto&&i:y)cin>>i;
	sort(x.rbegin(),x.rend()); sort(y.begin(),y.end());
	int za=X,zb=Y,zc=x.front(),zd=y.front();
	cout<<(min(zb,zd)-max(za,zc)>=1?"No War"s:"War"s)<<"\n"s;
}


Measured memory_bytes: 3644
/*
    @uthor: Amit Kumar
    user -->GitHub: drviruses ; CodeChef: dr_virus_ ; Codeforces,AtCoder,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#define ln mp::cpp_int;
#define ll    long long
#define ld    long double
#define ull   unsigned long long
#define all(vec) vec.begin(),vec.end()
#define endl "\n"
ll google_itr = 1;
#define google(x) cout<<"Case #"<<x<<":"
#define pi 3.14159265358979323846264338327950L

const ll mod = 1e9+7;
const ll inf = 1e18;


void virus(){
    ll len;
    cin>>len;
    vector<ll> arr(len);
    for(auto &i:arr) cin>>i;
    ll mx = arr[0];
    ll sum = 0;
    for(auto i=1; i<len; i++){
        if(arr[i] < mx) sum += abs(mx-arr[i]);
        mx = max(mx,arr[i]);
    }
    cout<<sum<<endl;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    ll t = 1;
    //cin>>t;
    while(t--){
           auto start = high_resolution_clock::now();
           virus();
           auto stop = high_resolution_clock::now();
           auto duration = duration_cast<seconds>(stop - start);
           cerr << "\n Time: "<<duration.count()<<endl;
        //your code goes here
    }
    return 0;
}

Measured memory_bytes: 4804
N,M=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(M)]
l=[]
for x in a:
    if x[0]==1:l.append(x[1])
m=[]
for x in a:
    if x[1]==N:m.append(x[0])
if set(l) & set(m):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Measured memory_bytes: 48640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e5+1)


int main (){
fastio;

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

int a[n],b[m];
int i;
for(i=0;i<n;i++)
    cin>>a[i];

for(i=0;i<m;i++)
    cin>>b[i];

int prefa[n+1];
int prefb[m+1];

int ans=0;

prefa[0]=0;
for(i=0;i<n;i++)
    prefa[i+1]=prefa[i]+a[i];
prefb[0]=0;
for(i=0;i<m;i++)
    prefb[i+1]=prefb[i]+b[i];

int p1=0;
int p2=0;

int curr=0;

while(p1<=n && prefa[p1]<=k)
    p1++;
p1--;
ans=p1;

while(p2<=m && prefb[p2]<=k)
    p2++;

p2--;
ans=max(ans,p2);

p2=0;

while(p1>=0 && p2<=m){
    while(p2<=m && prefb[p2]+prefa[p1]<=k)
        p2++;

    p2--;
    ans=max(ans,p2+p1);

    p1--;
}
cout<<ans;


}


Measured memory_bytes: 6724
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = deque()
reverse = 1
for i in range(n):
    if reverse == 1:
        b.append(a[i])
        reverse *= -1
    else:
        b.appendleft(a[i])
        reverse *= -1

b_list = list(b)
if reverse == 1:
    print(*b_list)
else:
    print(*b_list[::-1])

Measured memory_bytes: 32548
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;


namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Trim().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            var NW = Sarray();
            var n = NW[0];
            var ws = NW[1];
            var dp = new long[ws + 1];
            var max = 0L;
            for (var i = 1; i <= n; ++i)
            {
                var vw = Sarray();
                var v = vw[0];
                var w = vw[1];
                for (var j = ws; 0 < j; --j)
                {
                    var pre = j - w;
                    if (0 < pre && 0 < dp[pre])
                    {
                        dp[j] = Math.Max(dp[j], dp[pre] + v);
                        max = Math.Max(dp[j], max);
                    }
                }
                dp[w] = Math.Max(dp[w], v);
                max = Math.Max(dp[w], max);
            }
            WriteLine(max);
        }
    }
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define MSGF(x, n) MSG(fixed << setprecision(n) << x)
#define END(x) cout << x << endl; exit(0);
#define IPT(v, n) REP(i, 0, n){ cin >> v[i]; }
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<ull> vul;
typedef vector<vector<ull>> vvul;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
const static ll INF = 1LL << 30;

ll a, b, c, d, k, l, m, n, h, w, q, x, y;
string s, t;

ll ans = 0;
ll sum = 0;
ll cnt = 0;
ll cur = 0;
ll tmp = 0;
ll mini = INF;
ll maxi = 0;

double ave = 0.0;

ll mod_pow(ll base, ll power) {
    if (power == 0) return 1;
    if (power == 1) return base % MOD;
    if (power % 2 == 0) return ((mod_pow(base % MOD, (power / 2)) % MOD) * (mod_pow(base, (power / 2)) % MOD)) % MOD;
    return (base % MOD * (mod_pow(base % MOD, power - 1) % MOD)) % MOD;
}

ll mod_fact(ll number) {
    ll ret = 1;
    ll count = 1;
    while (count <= number) {
        ret *= (count % MOD);
        ret %= MOD;
        count++;
    }
    return ret % MOD;
}

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

int main() {
    cin >> k >> s;
    if (s.length() <= k) {
        MSG(s)
    } else {
        MSG(s.substr(0, k) << "...")
    }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i = s; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  ll r,d,x;
  cin >> r >> d >> x;
  rep(i,0,10) {
    x = r*x - d;
    cout << x << endl;
  }
  return 0;
}


Measured memory_bytes: 3572
x, n = map(int, input().split())
p = list(map(int, input().split()))

p = set(p)

diff = 101
indx = 0
if n != 0:
    for now in range(0, 102):
        if now not in p:
            now_diff = abs(now - x)
            if diff > now_diff:
                diff = now_diff
                indx = now
            else:
                break
    print(indx)
else:
    print(x)


Measured memory_bytes: 9132
#include<stdio.h>


int main(void){
	int a, b,c;
	scanf("%d" "%d" "%d", &a, &b, &c);

	int i,count=0;
	for (i = a; i < b + 1; i++){
		if (c%i == 0)
			count++;
		else
			; //何もしない
	}
	printf("%d\n", count);


	return 0;
}


Measured memory_bytes: 2120
import java.util.*;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      int k = sc.nextInt();
      int sum =  0;
      for(int i=0;i<k;i++){
        if(a!=0){
          sum +=1;
          a--;
        }
        else if(b!=0){
          sum += 0;
          b--;
        }
        else{
          sum -=1;
          c--;
        }
      }
      System.out.println(sum);

    
     

      
    }
}

Measured memory_bytes: 27252
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
#include <utility>
//#include <set>
#include <map>
//#include <queue>
//#include <deque>
#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<string> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

ll INF = 1000000000000 ;

struct drug{
	int a ;
	int b ;
	int c ;
};

int main(){
	ll n,ma,mb ;
	cin >> n >> ma >> mb ;
	vector<pair<ll,ll>> must ;
	ll sub1=ma,sub2=mb ;
	while(ma<=10*n&&mb<=10*n){
		must.push_back(make_pair(ma,mb)) ;
		ma += sub1 ;
		mb += sub2 ;
	}
	vector<drug> fr,ba ;
	for(int i=0;i<n;i++){
		drug d ;
		cin >> d.a >> d.b >> d.c ;
		if(i&1){
			ba.push_back(d) ;
		}else{
			fr.push_back(d) ;
		}
	}
	map<pair<ll,ll>,ll> m1,m2 ;
	pair<ll,ll> ins ;
	for(int i=0;i<(1<<fr.size());i++){
		bitset<25> bit(i) ;
		ll a = 0,b = 0 ;
		ll cost = 0 ;
		for(int j=0;j<fr.size();j++){
			if(bit[j]){
				a += fr.at(j).a ;
				b += fr.at(j).b ;
				cost += fr.at(j).c ;
			}
		}
		ins.first = a ;
		ins.second = b ;
		if(m1.count(ins)){
			m1[ins] = min(m1[ins],cost) ;
		}else{
			m1[ins] = cost ;
		}
	}
	for(int i=0;i<(1<<ba.size());i++){
		bitset<25> bit(i) ;
		ll a = 0,b = 0 ;
		ll cost = 0 ;
		for(int j=0;j<ba.size();j++){
			if(bit[j]){
				a += ba.at(j).a ;
				b += ba.at(j).b ;
				cost += ba.at(j).c ;
			}
		}
		ins.first = a ;
		ins.second = b ;
		if(m2.count(ins)){
			m2[ins] = min(m2[ins],cost) ;
		}else{
			m2[ins] = cost ;
		}
	}
	ll ans = INF ;
	pair<ll,ll> serch ;
	for(auto p:m1){
		ll a = p.first.first ;
		ll b = p.first.second ;
		ll c = p.second ;
		bool ok = false ;
		for(int i=0;i<must.size();i++){
			if(a>must.at(i).first||b>must.at(i).second) continue ;
			serch.first = must.at(i).first-a ;
			serch.second = must.at(i).second-b ;
			if(m2.count(serch)){
				ok = true ;
				ll cost = c+m2[serch] ;
				ans = min(ans,cost) ;
			}
		}
	}
	if(ans==INF) cout << -1 << endl ;
	else cout << ans << endl ;
}


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

template <typename T> void chmin(T&x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef int64_t s64;
typedef uint64_t u64;
typedef uint32_t u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
	char c;
	while(gc<'-');
	if(c=='-')
	{
		int x=gc-'0';
		while(gc>='0')x=x*10+c-'0';
		return -x;
	}
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}
#undef gc

const int N=2e5+5;
int n;
vector<int>lk1[N],lk2[N];
int deep[N],fa[N];

void dfs2(int x)
{
	for(auto y:lk2[x])
	if(y!=fa[x])
	{
		fa[y]=x;deep[y]=deep[x]+1;
		dfs2(y);
	}
}
void check(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	if(fa[x]==fa[y]||fa[x]==y||fa[fa[x]]==y)return ;
	//cerr<<x<<" "<<y<<endl;
	puts("-1");
	exit(0);
}
int ans;
void dfs1(int x,int fr,int dep)
{
	if(dep>=deep[x])return ;
	chmax(ans,deep[x]);
	for(auto y:lk1[x])
	if(y!=fr)
	{
		check(x,y);
		dfs1(y,x,dep+1);
	}
}

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
	int x1,x2;
	cin>>n>>x1>>x2;
	rep(i,1,n-1)
	{
		int x=read(),y=read();
		lk1[x].push_back(y);
		lk1[y].push_back(x);
	}
	rep(i,1,n-1)
	{
		int x=read(),y=read();
		lk2[x].push_back(y);
		lk2[y].push_back(x);
	}
	dfs2(x2);
//	rep(i,1,n)cerr<<deep[i]<<" ";cerr<<endl;
	dfs1(x1,0,0);
	cout<<ans*2;
}


Measured memory_bytes: 32252
n,k=map(int,input().split())
s=input()
s+="2"
lst=[]
ruiseki=[0]
i=0;cnt=1;ans=0
while True:
    if s[i]==s[i+1]:
        i+=1
        cnt+=1
    else:
        lst.append(cnt)
        ruiseki.append(ruiseki[-1]+cnt)
        i+=1
        cnt=1 
    if i==n:
        break
if s[0]=="1":
    flag=True
    if 2*k>=len(lst)-1:
        print(ruiseki[-1])
        exit()
else:
    flag=False
    if 2*k>=len(lst):
        print(ruiseki[-1])
        exit()

for i in range(1,len(lst)):
    if flag:
        ans=max(ans,ruiseki[min(i+2*k,len(lst))]-ruiseki[i-1])
        flag=False
    else:
        ans=max(ans,ruiseki[min(i+2*k-1,len(lst))]-ruiseki[i-1])
        flag=True
print(ans)

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

int main() {
  string s;
  cin >> s;
  int i, ans = 0;
  for (i = 0; i < s.size(); ++i) {
    if (s[i] == '2') {
      ++ans;
    }
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int x;
cin >> x;
int happiness = 0;
while (x > 5){
if(x >= 500){
	happiness += floor(x / 500) * 1000;
	x = x % 500;
} else {
	happiness += floor(x / 5) * 5;
	x = x % 5;
}
}
cout << happiness << endl;

}




Measured memory_bytes: 3628
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 1の塊の長さと位置を調べる
    l = []
    if S[0] == '1':
        l.append(0)
    # 先端0の場合、一番左に長さ0の1の塊があるとする
    else:
        l.append(0)
        l.append(0)
    for i in range(N - 1):
        if S[i] == '0' and S[i+1] == '1':
            l.append(i + 1)
        elif S[i] == '1' and S[i+1] == '0':
            l.append(i + 1)
    if S[-1] == '1':
        l.append(N)
    # 後端0の場合、一番右に長さ0の1の塊があるとする
    else:
        l.append(N)
        l.append(N)

    ans = 0
    # 0の塊がK個以下の場合
    if len(l) // 2 - 1 < K:
        ans = N
    # 1の塊をK+1個くっつけた場合の長さを調べる
    else:
        for i in range(len(l) // 2 - K):
            ans = max(l[2*i+2*K+1] - l[2*i], ans)

    print(ans)

if __name__ == '__main__':
    resolve()


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

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"

map <int, int> d;

int main()
{
	#ifdef LOCAL
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	#endif

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int t;
		scanf("%d", &t);
		++d[t - 1];
		++d[t];
		++d[t + 1];
	}

	int ans = 0;
	for (const auto& t : d) {
		ans = max(ans, t.s);
	}

	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 4736
from collections import deque
def myAnswer(N:int,A:list) -> None:
   ans = deque()
   for n,a in enumerate(A):
      if((n + 1)% 2==0):
         ans.append(str(a))
      else:
         ans.appendleft(str(a))
   if(N % 2 == 0):
      ans = reversed(ans)
   print(" ".join(ans))

def modelAnswer():
   return
def main():
   N = int(input())
   A = list(map(int,input().split()))
   myAnswer(N,A[:])
if __name__ == '__main__':
   main()

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

int s[10000];
int t[500];

bool linersearch(int t, int n)
{
  int i;
  
  i = 0;
  while(s[i] != t){
    i++;
    if(s[i] == t) return true;
    if(i == n-1) return false;
  }
  return true;//caution
}

int main(){
  int n,q;
  int cnt=0;
  
  cin >> n;
  for(int i=0;i < n;i++){
    cin >> s[i];
  }
  cin >> q;
  for(int i=0;i < q;i++){
    cin >> t[i];
    if(linersearch(t[i],n))cnt++;
  }
  
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
//#pragma GCC optimize ("02")
#define ll long long
#define oo 1000000007
using namespace std;

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

	ll x, ans = 0;
	cin >> x;
	ll p = x/500;
	ans += 1000*p;
	x -= 500*p;
	ll c = x/5;
	ans += c*5;
	cout << ans;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Num implements Comparable<Num>{
	int v;
	int id;
	boolean isOddPos = false;
	
	public Num(int v, int id) {
		this.v = v;
		this.id = id;
	}
	
	public void check() {
		
	}

	@Override
	public int compareTo(Num that) {
		return this.v - that.v;
	}
}

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		Num[] a = new Num[n];
		for(int i = 0; i < n; i++) {
			a[i] = new Num(sc.nextInt(), i);
		}
		
		sc.close();
		
		Arrays.sort(a);
		
		for(int i = 0; i < n; i += 2) {
			a[i].isOddPos = true;
		}
		
		for(int i = 0; i < n; i += 2) {
			a[i].isOddPos = true;
		}
		
		int ans = 0;
		for(int i = 0; i < n; i++) {
			if(a[i].isOddPos) {
				if(a[i].id%2 != 0) ans++;
			} else {
				if(a[i].id%2 == 0) ans++;
			}
		}
		
		System.out.println(ans/2);
		
		return;
	}
	
}

Measured memory_bytes: 26556
def main():
    t = list(input())
    for i in range(len(t)-1):
        if t[i] == '?':
            if t[i-1] == 'P':
                t[i] = 'D'
            elif t[i+1] == 'D' or t[i+1] == '?':
                t[i] = 'P'
            else:
                t[i] = 'D'

    if t[-1] == '?':
        t[-1] = 'D'
        
    for i in t:
        print(i,end = '')


main()


Measured memory_bytes: 83676
//* AuThOr GaRyMr *//
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB(a) push_back(a)
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int p[55];
vector<mp> v;
int main(){
	int n;
	scanf("%d",&n);
	rb(i,1,n){
		scanf("%d",&p[i]); 
		if(p[i]!=i){
			v.PB(II(p[i],i));
		}
	} 
	if(v.size()==0){
		puts("YES");
	}
	else{
		if(v.size()==2){
			if(v[0].FIR==v[1].SEC&&v[0].SEC==v[1].FIR){
				puts("YES");
			}
			else{
				puts("NO");
			}
		}
		else{
			puts("NO");
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
#define pc putchar
#define lowbit(x) ((x)&(-(x)))
#define mo 1000000007
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
const int N=17;
int n,m,dp[N][1<<N],ny[1<<N],jc[1<<N],a[N],sta,f[1<<N],ans; 
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+(ch^48);ch=getchar();}
    return ret*ff;
}
void write(int x){if(x<0){x=-x,pc('-');}if(x>9) write(x/10);pc(x%10+48);}
void writeln(int x){write(x),hh;}
void writesp(int x){write(x),pc(' ');}
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=res*x%mo;
		y>>=1;
		x=x*x%mo;
	}
	return res;
}
int C(int x,int y){
	if(x<y) return 0;
	return jc[x]*ny[y]%mo*ny[x-y]%mo; 
} 
bool cmp(int A,int B){
	return A>B;
}
signed main(){
	n=read(),m=read();sta=(1<<n);
	for(int i=1;i<=m;i++) a[i]=read();
	sort(a+1,a+m+1,cmp);
	jc[0]=1;
	for(int i=1;i<=sta;i++) jc[i]=jc[i-1]*i%mo;
	ny[sta]=ksm(jc[sta],mo-2);
	for(int i=sta-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mo;
	for(int i=1;i<=sta;i++) f[i]=f[i-lowbit(i)]+1;
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int zt=0;zt<sta;zt++){
			if(dp[i-1][zt]){
				dp[i][zt]=(dp[i][zt]+dp[i-1][zt])%mo;
				for(int j=0;j<n;j++){
					if(!(zt&(1<<j)))
						dp[i][zt|(1<<j)]=(dp[i][zt|(1<<j)]+dp[i-1][zt]*jc[1<<j]%mo*C(sta-zt-a[i],(1<<j)-1)%mo)%mo;
				}
			}
		}
	}
	for(int i=0;i<sta;i++){
		if(f[i]&1) ans=(ans-dp[m][i]*jc[sta-1-i]%mo+mo)%mo;
		else ans=(ans+dp[m][i]*jc[sta-1-i]%mo)%mo;
	}
	write(ans*sta%mo);
    return 0;
}

Measured memory_bytes: 19712
def bi(x):
    x = int(x)
    i = 0
    o = [0]*61
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

N = int(input())
A = list(map(bi,input().split()))

# print(*A,sep='\n')
a = 0
ruijoo = 1
bbb = 0
B = [0]*N
h = 0
while h < 61:
    i = 0
    isOne = 0
    while i < N:
        aaaa = A[i][h]
        isOne += aaaa
        B[i] = aaaa
        i += 1
    isZero = N - isOne
    C = [isOne,isZero]
    bbbb = 0
    i = 0
    while i < N:
        bbbb += C[B[i]]
        i += 1
    bbbb *= ruijoo
    bbb += bbbb
    bbb %= 1000000007
    ruijoo *= 2
    ruijoo %= 1000000007
    h += 1

bbb *= 500000004
bbb %= 1000000007
print(bbb)

Measured memory_bytes: 234352
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt(); 
		
		int[]h = new int[n];
		
		h[0] = stdIn.nextInt();
		
		int cnt = 1;
		int max = h[0];
		
		for(int i = 1; i < n; i++) {
			h[i] = stdIn.nextInt();
			if(h[i]>= max) {
				cnt++;
				max = h[i];
			}
			
			
		}
		System.out.println(cnt);
		
		
	}

}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 5100000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  int N; cin >> N;
  map<int,int> C;
  for(int n = 1; n <= N; n++) {
    int nn = n;
    for(int i = 2; i <= n; i++) {
      while(nn%i == 0){
        C[i]++;
        nn /= i;
      }
    }
  }
  // for(auto c : C) {
  //   cout << c.first << " " << c.second << endl;
  // }

  int ans = 0;
  //パターン１
  int c2 = 0,c4 = 0,c14 = 0,c24 = 0,c74 = 0;
  for(auto c : C) {
    int num = c.second;
    if(num >= 2) c2++;
    if(num >= 4) c4++;
    if(num >= 14) c14++;
    if(num >= 24) c24++;
    if(num >= 74) c74++;
  }

  ans += c74;
  ans += c14*(c4-1);
  ans += c24*(c2-1);
  ans += c4*(c4-1)/2*(c2-2);

  //printf("%d %d %d %d %d\n", c2,c4,c14,c24,c74);

  cout << ans << endl;
}


Measured memory_bytes: 764
a, b, c, d = input()

op_choice = ["+", "-"]

for op1 in op_choice:
    for op2 in op_choice:
        for op3 in op_choice:
            check = a + op1 + b + op2 + c + op3 + d
            if eval(check) == 7:
                print(check + "=7")
                exit()


Measured memory_bytes: 2940