akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int a[100005];
int main()
{
    ios::sync_with_stdio(false);
    int w,h,n;cin>>w>>h>>n;
    int a,b,c;
    int x1=0,y1=0,x2=w,y2=h;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        if(c==1)
            x1=max(x1,a);
        if(c==2)
            x2=min(x2,a);
        if(c==3)
            y1=max(y1,b);
        if(c==4)
            y2=min(y2,b);
    }
        cout<<(x2-x1)*(y2-y1)*(x2>x1)*(y2>y1)<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string S;
  cin >> S;
  
  int n = S.size();
  
  bool tf = false;
  for(int i=0; i<n; i++){
   for(int j=i; j<n+1; j++){
     string left = S.substr(0, i);
     string right = S.substr(j, n);
//     cout << left + right << endl;
     if(left+right == "keyence") {
       tf = true;
       break;
     }
   }    
  }
  if(tf) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}

Measured memory_bytes: 384
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300IQ as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int[] cnt = new int[N+1];
         for(int d=1; d <= N; d++)
            for(int v=d; v <= N; v += d)
               cnt[v]++;
         long res = 0L;
         for(int k=1; k <= N; k++)
            res += (long)k*cnt[k];
         System.out.println(res);
      }
   }

Measured memory_bytes: 71836
S = input()
cnt = 0
prev = 0
while prev != len(S):
    prev = len(S)
    ans = []
    for i, n in enumerate(S):
        if i == 0:
            ans.append(n)
            continue
        if len(ans) > 0 and ans[-1] != n:
            ans.pop()
            cnt += 2
        else:
            ans.append(n)
    S = ''.join(ans)
print(cnt)



Measured memory_bytes: 50944
# coding:utf-8

import itertools

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N, M = inpl()

cakes = []
for i in range(N):
    cakes.append(inpl())

sign = [-1, 1]
ans = -INF
for a, b, c in itertools.product(*([sign] * 3)):
    score = [a * x + b * y + c * z for x, y, z in cakes]
    score.sort()
    score.reverse()
    ans = max(ans, sum(score[:M]))

print(ans)

Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld long double
#define fast ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define F(i,a,b) for(int i= (int)(a); i<(int)(b);i++)
#define FI(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
const int N = 1e6+7 ;
string s ;
int main(){fast ;
	int n,k ;
	cin >> n ;
	vector<pii> a(n) ;
	vector<int> x(n) , y(n) ;
	for(int& i : x)
		cin >> i ;
	for(int& j : y)
		cin >> j ;
	for(int i = 0 ; i < n ; i++)
		a[i] = {x[i],y[i]} ;
	int res = 0 ;
	for(auto it : a){
		res += (it.ff - it.ss > 0 ? it.ff - it.ss : 0) ;
	}
	cout << res << endl ;

}




Measured memory_bytes: 256
use maplit::hashmap;
use proconio::input;

fn main() {
    input! {
        n: usize,
        r#as: [i64; n],
    }

    let mut ans = 0u64;
    let mut counter = hashmap!();
    for (i, a) in r#as.into_iter().enumerate() {
        let i = i as i64;
        ans += counter.get(&(a - i)).unwrap_or(&0);
        *counter.entry(-a - i).or_insert(0) += 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 11772
def main():
    n, a = int(input()), list(map(int, input().split()))

    right = 0
    cnt, s = 0, 0

    for left in range(n):
        while right < n and s ^ a[right] == s + a[right]:
            s += a[right]
            right += 1

        if right == left:
            right += 1
        cnt += right - left
        s -= a[left]

    print(cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 24840
#define DINGER_GISBAR
#include <bits/stdc++.h>
using namespace std;
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
#ifdef ZEROKUGI
#include <dumper.hpp>
#define dump(x) dumper::dumper(cerr, __LINE__, (#x), (x), 50, 1, 1)
#define tick(...) dumper::tick(__VA_ARGS__)
#pragma message "Compiling " __FILE__
#else
#define dump(x)
#define tick(...)
#endif
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n) \
    for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c)   \
    sort(all(c)); \
    for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto &
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) { return 1LL << x; }
template <class T>
inline int size(const T& a) {
    return (int)a.size();
}
template <class T>
inline bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
    return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T>& v, const char& c) {
    return make_pair(v, c);
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
#ifdef ZEROKUGI
    if (v.empty()) {
        cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
        exit(EXIT_FAILURE);
    }
#endif
    for (auto& x : v) is >> x;
    return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const pair<vector<T>, char>& v) {
    bool t = 0;
    for (const T& x : v.first) {
        if (t) os << v.second;
        os << x;
        t = 1;
    }
    return os;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
    return os << v * ' ';
}
struct before_main {
    before_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
        tick(0, 0);
    };
} __before_main;
//}}}TEMPLATE_END

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

    long long ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == 0) continue;
        a[i] += b[i];
        ans += a[i]/2;
        b[i+1] = a[i]%2;
    }
    ans += (a[n-1] + b[n-1])/2;
    cout << ans << endl;
}


Measured memory_bytes: 1024
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq # 優先度付きキュー(最小値取り出し)

inf = 10**15
mod = 10**9+7
s = list(input())
t = list(input())
dict = {}
dict_t = {}
s_judge = [True for i in range(26)] # 全種類使っていない
t_judge = [True for i in range(26)] # 全種類使っていない
aint = ord('a')
flag = True
for i,c in enumerate(s):
    tmp = t[i]
    sint = ord(c)-aint
    tint = ord(tmp)-aint
    if s_judge[sint]:
        dict[sint] = tint
        s_judge[sint] = False
    else:
        if dict[sint] != tint:
            flag = False
            break
    if t_judge[tint]:
        dict_t[tint] = sint
        t_judge[tint] = False
    else:
        if dict_t[tint] != sint:
            flag = False
            break
if flag:
    print('Yes')
else:
    print('No')





Measured memory_bytes: 71624
#include "bits/stdc++.h"
using namespace std;
int main()
{
	int i,j,n,m;
	char str[51][51]={0};
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%s",str[i]);
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(str[i][j]!='#')
			{
				continue;
			}
			if(str[i-1][j]!='#'&&str[i][j-1]!='#'&&str[i+1][j]!='#'&&str[i][j+1]!='#')
			{
				printf("No\n");
				return 0;
			}
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(int& a){printf("%d",a);}
void print(long long& a){printf("%lld",a);}
void print(double& a){printf("%.15lf",a);}
template<class T> void print(T& a){cout<<a;}
template<class T> void print(vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(Head& head, Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(T& a){cerr<<a;}
template<class T> void dprint(vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(Head& head, Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}

int main(){
    int s;
    in(s);
    printf("%d:%d:%d\n",s/3600,(s/60)%60,s%60);
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int num, N, K;
  	cin >> N >> K;
	num = 1;
      
      while(N){
        if(2 * num > num + K){
          num += K;
        }
        else{
          num *= 2;
        }
      
        N--;
        
      }
	cout << num << endl;
  
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func swap(a []int, i, j int) {
	tmp := a[i]
	a[i] = a[j]
	a[j] = tmp
}

func swapRange(a []int, b, e, t int) {
	for k := 0; k < e-b; k++ {
		swap(a, b+k, t+k)
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}

	nQueries := nextInt()
	for i := 0; i < nQueries; i++ {
		b := nextInt()
		e := nextInt()
		t := nextInt()
		// fmt.Println(b, e, t, ":", stringifyArray(a))
		swapRange(a, b, e, t)
	}
	fmt.Println(stringifyArray(a))
}



Measured memory_bytes: 1280
N, Q = map(int, input().split())
s = input()
td = [input().split() for i in range(Q)]
#print("td = {}".format(td))

s = " " + s + " "
llim = 0
rlim = -1
for t, d in reversed(td):
    if("L" == d):
        if(s[llim + 1] == t):
            llim += 1
        if(s[rlim] == t):
            rlim += 1
    else:# if("R" == d):
        if(s[rlim - 1] == t):
            rlim -= 1
        if(s[llim] == t):
            llim -= 1
#    print("td = {}, llim = {}, rlim = {}".format([t, d], llim, rlim))

print(str(max(0, N + rlim - llim + 1)))


Measured memory_bytes: 39484
#include <bits/stdc++.h>
using namespace std;
int nxt[26][200010];
int dp[200010];
char s[200010];
int n;

const int alpha = 26;

int main() {
	scanf("%s", s);
	n = strlen(s);
	
	for(int i = 0; i < alpha; i++) {
		int last = n;
		for(int j = n-1; j >= 0; j--) {
			nxt[i][j] = last;
			if(s[j] - 'a' == i) last = j;
		}
	}
	dp[n] = 1;
	for(int i = n-1; i >= 0; i--) {
		int opt = 0;
		for(int j = 0; j < alpha; j++) {
			opt = max(opt, nxt[j][i]);
		}
		dp[i] = 1 + dp[opt];
	}
	int ans = n+1;
	bool vis[30];
	memset(vis, false, sizeof vis);
	vector <int> pos;
	
	for(int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		if(vis[c] == false) {
			vis[c] = true;
			ans = min(dp[i], ans);
			pos.push_back(i);
		}
	}
	for(int i = 0; i < alpha; i++) {
		if(vis[i] == false) {
			printf("%c\n", i + 'a');
			exit(0);
		}
	}
	
	int cur = 0;
	int opt = 26;
	for(int i : pos) {
		int c = s[i] - 'a';
		if(dp[i] == ans && opt > c) {
			opt = c;
			cur = i;
		} 
	}
	
	string res = "";
	res += s[cur];
	
	for(int i = 2; i <= ans; i++) {
		int best = ans - i + 1;
		assert(cur < n);
		for(int j = 0; j < alpha; j++) {
			if(best == dp[nxt[j][cur]]) {
				char x = j + 'a';
				res += x;
				cur = nxt[j][cur];
				break;
			}
		}
	}
	assert(cur == n);
	cout << res << '\n';
	return 0;
}

Measured memory_bytes: 21504
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int p[200100];
bool use[200100],u2[200100];
vector<int> gr[200100];
vector<int> ch[200100];
int m;
int cal(vector<int> x){
	x.pb(-1);x.pb(200100);
	sort(All(x));
	rep(i,x.size()-1){
		if(x[i]<x[i+1]-1) return x[i]+1;
	}
}
int dfs(int v){
	vector<int> x;
	rep(i,gr[v].size()) x.pb(dfs(gr[v][i]));
	return cal(x);
}
bool che(int a){
	int now=a;
	rep(i,m){
		vector<int> v=ch[i];
		v.pb(now);
		now=cal(v);
	}
	return (now==a);
}
int main()
{
	int n,c;
	vector<int> fl;
	cin>>n;
	rep(i,n){
		cin>>p[i];p[i]--;
		gr[p[i]].pb(i);
	}
	memset(use,false,sizeof(use));
	int now=0;
	while(!use[now]){
		use[now]=true;now=p[now];
	}
	memset(use,false,sizeof(use));
	while(!use[now]){
		fl.pb(now);use[now]=true;now=p[now];
	}
	m=fl.size();
	rep(i,m){
		rep(j,gr[fl[i]].size()){
			int v=gr[fl[i]][j];
			if(!use[v]) ch[i].pb(dfs(v));
		}
	}
	memset(u2,false,sizeof(u2));
	rep(i,ch[m-1].size()) u2[ch[m-1][i]]=true;
	vector<int> ca;
	rep(i,200100){
		if(!u2[i]) ca.pb(i);
	}
	if(che(ca[0])) cout<<"POSSIBLE"<<endl;
	else if(che(ca[1])) cout<<"POSSIBLE"<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
}


Measured memory_bytes: 19060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

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

    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> gusuc(n, 0);
    REP(i, n)
    {
        cin >> a[i];
        b[i] = a[i] / 2;

        ll pow2 = 2;
        while (b[i] % pow2 == 0){
            gusuc[i]++;
            pow2 *= 2;
        }
    }



    bool flag = true;
    REP(i,n){
        if(gusuc[i] != gusuc[0]){
            flag = false;
            break;
        }
    }

    if(flag){
        // ll pow2 = pow(2, gusuc[0]);
        // REP(i, n)
        // {
        //     b[i] /= pow2;
        // }
        ll lcm = b[0];

        FOR(i,1,b.size()){
            lcm = lcm * (b[i] / gcd(lcm, b[i]));
        }

        ll cnt = 0;
        ll kisu = 1;
        //lcm *= pow2;

        while (kisu  <= m / lcm)
        {
            cnt++;
            kisu += 2;
        }
        cout << cnt << endl;
    }
    else{
        cout << 0 << endl;
    }


    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cmath>
#include <map>
#include <utility>
#include <list>
#include <string>

using namespace std;


int main() {
    int n;
    int p[10000];
    int max = 0;
    int total = 0;

    cin >> n;

    for (int i=0; i < n; i++){
        int t;
        cin >> t;
        if (t > max){
            max = t;
        }
        total += t;
    }

    total -= max / 2;

    cout << total << endl;


    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
  int N;
  scanf("%d", &N);

  vector< vector<int> > F(N, vector<int>(10));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 10; ++j) scanf("%d", &F[i][j]);
  }
  vector< vector<int> > P(N, vector<int>(11));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= 10; ++j) scanf("%d", &P[i][j]);
  }

  int ans = -2e9;
  for (int i = 1; i < 1 << 10; ++i) {
    int sum = 0;
    for (int j = 0; j < N; ++j) {
      vector<int> f = F[j];
      int cnt = 0;
      for (int k = 0; k < 10; ++k) {
	if ((i >> k & 1) && f[k] == 1) cnt++;
      }
      sum += P[j][cnt];
    }
    ans = max(ans, sum);
  }
  printf("%d\n", ans);
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N;
  cin>>N;
  vector<Int> A(N);
  cin>>A;

  vector<Int> cnt(1000010);
  for(Int a:A) cnt[a]++;
  sort(A.begin(), A.end());
  A.erase(unique(A.begin(), A.end()), A.end());

  for(Int a:A){
    for(Int j=2;a * j < (Int)cnt.size();j++) cnt[a * j] = 0;
  }

  Int ans = 0;
  for(Int c:cnt) if(c==1)ans += c;
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 12696
// 有點不耐煩會破壞偉大的計劃

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 1e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug() {
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main() {
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    long long n; cin >> n;

    vector<long double> v(n);

    for(long long i = 0; i < n; i++) {
        cin >> v[i];
    }

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

    for(long long i = 1; i < n; i++){
        v[i] = (v[i] + v[i - 1]) / 2.0;
    }

    cout << fixed << setprecision(7) << v[n - 1];

    return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <stack>

using namespace std;

int main(){
	int n;
	stack<int> st;
	
	while(cin>>n){
		if(n==0){
			cout<<st.top()<<endl;
			st.pop();
		}else{
			st.push(n);
		}
	}

	return 0;
}

Measured memory_bytes: 2992
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	as := make([]int, n)
	for i := range as {
		sc.Scan()
		as[i], _ = strconv.Atoi(sc.Text())
	}
	var cnt int
	for i := range as {
		if (i+1)%2 == 1 && as[i]%2 == 1 {
			cnt++
		}
	}
	fmt.Println(cnt)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


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

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

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	int n;
	int d[100100];

	cin >> n;

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

	int j;
	cin >> j;
	if(j!=0) {
		cout << "0" << endl;
		return 0;
	} else {
		d[0]+=1;
	}

	for(int i=1; i<n; i++){
		int j;
		cin >> j;
		d[j]+=1;
	}

	long int r=1;
	int s=1;
	if(d[0]==1){
		for(int i=1; i<n && s<n; i++){
			for(int j=0; j<d[i]; j++){
				r*=d[i-1];
				r%=998244353;
			}
			s+=d[i];
		}
	}else{
		r=0;
	}

	cout << r << endl;

	return 0;
}




Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i,a[100001],res[100001];
	cin>>n;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	res[1]=0;
	res[2]=abs(a[1]-a[2]);
	for(i=3;i<=n;i++)
	res[i]=min(res[i-1]+abs(a[i]-a[i-1]),res[i-2]+abs(a[i]-a[i-2]));
	cout<<res[n];
}

Measured memory_bytes: 1024
program main
  implicit none
  integer :: n, me
  integer, allocatable :: x(:)
  read (*, *) n
  allocate (x(n))
  read (*, *) x(:)
  me = sum(x) / n
  write (*, "(i0)") min(sum((x(:) - me) ** 2), sum((x(:) - me - 1) ** 2))
  deallocate (x)
end program main


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int  INF=10e7;

typedef  pair<int,int> P;


int main(){
     int a,b,c;
     int ans=0;
cin>>a>>b>>c;
if(a==b&&b==c){
     cout<<1<<endl;
}else{
     int ans=3;
     if(a==b)ans--;
     if(b==c)ans--;
     if(a==c)ans--;
     cout<<ans<<endl;
}
}

Measured memory_bytes: 256
n,k = (int(i) for i in input().split())
x =list(int(i) for i in input().split())
a = [999999999999999]*(n-k+1)
for i in range(n-k+1):
  left =x[i]
  right =x[i+k-1]
  leftdistance = abs(left)+abs(right-left)
  rightdistance = abs(right)+abs(left-right)
  a[i] = min(leftdistance,rightdistance)
print(min(a))

Measured memory_bytes: 14568
#include<bits/stdc++.h>
#define maxn 100007
using namespace std;
int n,m,a[maxn],b[maxn],ans;
bool check[407];

bitset<500>f[407];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		f[i][i]=1;
		for(int j=m;j>0;j--){
			int x=a[j],y=b[j];
//			cerr<<f[i][x]<<" "<<f[i][y]<<endl;
			if(f[i][x]&f[i][y]){
				check[i]=1;
				break;
			}
			if(f[i][x]) f[i][y]=1;
			if(f[i][y]) f[i][x]=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(check[i]) continue;
		for(int j=i+1;j<=n;j++){
			if(check[j]) continue;
			if(!((f[i]&f[j]).any())) ans++;
		}
	}
	printf("%d\n",ans);
} 

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
int main () {
  int k,a,b;
  cin >>k;
  cin >>a>>b;
  for(int i=a;i<=b;i++){
    if(i%k == 0){
      cout<<"OK"<<endl;
      return 0;
    }
  }
  cout <<"NG"<<endl;
return 0;
}

Measured memory_bytes: 3608
l = [
  [], [], [], []
]

3.times do
  (a, b) = gets.split.map(&:to_i)
  l[a - 1] << b - 1
  l[b - 1] << a - 1
end

l.each_with_index do |p, i|
  if p.size >= 3
    puts 'NO'
    break
  end

  if i == 3
    puts 'YES'
  end
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000000000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;

ll n, top, pre, ans = inf, a[N];

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld",&n);
	for(ll i = 1; i <= n; i++){
		scanf("%lld", a + i);
		top += a[i];
	}
	for(ll i = 1; i <= n; i++){
		pre += a[i];
		ll kal = top - pre;
		ans = min(ans, abs(pre - kal));
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <cmath>
typedef long long LL;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
 
int main(){
  string S;
  cin >> S;
  vector<LL> members(S.length());
  

  LL i=0;
  while(i<S.length()){
    LL cnt_r=0;
    LL cnt_l=0;
    while(S[i]=='R'){
      cnt_r++;
      i++;
    }
    while(S[i]=='L'){
      cnt_l++;
      i++;
    }
    
    if((cnt_r-cnt_l)%2==0){
      members[i-cnt_l-1]=(cnt_r+cnt_l)/2;
      members[i-cnt_l]=(cnt_r+cnt_l)/2;
    }else{
      members[i-cnt_l-1]=(cnt_r-1)/2+cnt_l/2+1;
      members[i-cnt_l]=(cnt_r)/2+(cnt_l-1)/2+1;
    }
  }
  
  rep(i,S.length()){
    cout << members[i] << " ";
  }
  return 0;
}

Measured memory_bytes: 1408
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
a=set(a)
mod=10**9+7
dp=[0]*(n+1)

if 0 in a:
    dp[0]=0
else:
    dp[0]=1

if 1 in a:
    dp[1]=0
else:
    dp[1]=1

for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-2]+dp[i-1])%mod

print(dp[-1])
    


Measured memory_bytes: 13192
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Gput(a, b) G[a].push_back(b)
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));

int main()
{
    cout << fixed << setprecision(30);
    ll n;
    cin >> n;
    vec x(n), y(n), h(n);
    loop(i, n) cin >> x[i] >> y[i] >> h[i];
    loop(cx, 101)
    {
        loop(cy, 101)
        {
            ll H;
            //ピラミッドの高さを決めてしまう
            loop(i, n)
            {
                if (h[i] > 0)
                {
                    H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                    break;
                }
            }
            //条件を満たすかどうか
            bool check = true;
            loop(i, n)
            {
                if (h[i] != 0)
                {
                    ll nH = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                    if (nH != H)
                        check = false;
                }
                if (h[i] == 0)
                {
                    ll cH = H - abs(x[i] - cx) - abs(y[i] - cy);
                    if (cH > 0)
                        check = false;
                }
            }
            if (check)
            {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <tuple>
#include <stack>
#include <list>

using namespace std;

using pair_int = std::tuple<int, int>;
using point_t = pair_int;
using mt_data_list_t = std::list<std::tuple<int, point_t>>;

pair_int& operator+=(pair_int &l_location, const pair_int &r_location) {
   int l_x, l_y;
   std::tie(l_x, l_y) = l_location;
   int r_x, r_y;
   std::tie(r_x, r_y) = r_location;
   l_location = std::make_tuple(l_x + r_x, l_y + r_y);
   return l_location;
}

class Mountain {

public:
   Mountain() :
      is_going_up{ false },
      location{},
      location_par_height{},
      pond_list{} {
   }

   void Push(const char word) {
      switch(word) {
      case '/': {
         int x = std::get<0>(location);
         location += point_t{ 1, 1 };
         int y = std::get<1>(location);

         if (location_par_height.empty()) { return; }
         const int slope_x = location_par_height.top();
         int area = x - slope_x;
         location_par_height.pop();
         if (is_going_up) {
            auto itr = pond_list.rbegin();
            if (itr != pond_list.rend()) {
               ++itr;
            }
            while (itr != pond_list.rend()) {
               int pond_x, pond_y;
               std::tie(pond_x, pond_y) = std::get<1>(*itr);
               if (pond_x < slope_x || pond_y >= y) {
                  break;
               }
               area += std::get<0>(pond_list.back());
               pond_list.pop_back();
               itr = pond_list.rbegin();
               if (itr != pond_list.rend()) {
                  ++itr;
               }
            }
            std::get<0>(pond_list.back()) += area;
            std::get<1>(pond_list.back()) += point_t{ 0, 1 };
         } else {
            const auto& pond_location = std::make_tuple(x, y);
            pond_list.emplace_back(std::make_tuple(area, pond_location));
         }

         is_going_up = true;
         break;
      }
      case '_': {
         location += point_t{ 1, 0 };
         break;
      }
      case '\\': {
         int x = std::get<0>(location);
         location_par_height.push(x);
         location += point_t{ 1, -1 };

         is_going_up = false;
         break;
      }
      }
   }

   void Print() {
      std::string ret_text{ std::to_string(pond_list.size()) };
      int area_sum = 0;
      for (const auto& pond : pond_list) {
         int area = std::get<0>(pond);
         area_sum += area;
         ret_text += " " + std::to_string(area);
      }
      cout << std::to_string(area_sum) << endl << ret_text << endl;
   }

private:
   bool is_going_up;
   point_t location;
   std::stack<int> location_par_height;
   mt_data_list_t pond_list;

};

int main () {

   Mountain mt;
   char word;
   while (cin >> word) {
      mt.Push(word);
   }

   mt.Print();

   return 0;

}

Measured memory_bytes: 3380
(function main(){
  let lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n");
  let [n, k] = lines.shift().split(' ').map(Number);
  let w = lines.map(Number);

  const canAllStack = (p) => {
    let cnt = 0;
    let sum = 0;
    for (let i = 0; i < k; i++) {
      sum = 0;
      while (sum + w[cnt] <= p) {
        sum += w[cnt++]
        if (cnt === n) return n;
      }
    }
    return cnt;
  };

  let mid, left = 0, right = 1e9;
  while (right - left > 1) {
    mid = ((right + left) / 2);
    if (canAllStack(mid) >= n) right = mid;
    else left = mid;
  }
  console.log(Math.floor(right));
})();



Measured memory_bytes: 29220
A,B,Q=map(int,input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]
xx=[int(input()) for _ in range(Q)]

#二分探索関数
def bin_search(x,seq):
    a=0
    b=len(seq)-1
    for i in range(len(seq)):
        center=((a+b)//2)
        if x>=seq[center]:
            a=center
        else:
            b=center
        if b-a<=1:
            break
    return seq[a],seq[b]
 
for i in range(Q):
    x=xx[i]
    Nb_s0,Nb_s1=bin_search(x,s)
    Nb_t0,Nb_t1=bin_search(x,t)
    p1=abs(Nb_s0-x)
    p2=abs(Nb_s1-x)
    p3=abs(Nb_t0-x)
    p4=abs(Nb_t1-x)
    q1=abs(Nb_t0-Nb_s0)
    q2=abs(Nb_t0-Nb_s1)
    q3=abs(Nb_t1-Nb_s0)
    q4=abs(Nb_t1-Nb_s1)
    print(min(p1+q1,p2+q2,p1+q3,p2+q4,p3+q1,p4+q4,p3+q2,p4+q3))

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

int main() {
  int N, M, C; cin >> N >> M >> C;
  vector<int> B(M);
  for (int i = 0; i < M; i++) {
    cin >> B.at(i);
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int AB = 0;
    int right = C;
    for (int j = 0; j < M; j++) {
      int A; cin >> A;
      AB = A * B.at(j);
      right += AB;
    }
    if (right > 0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		Map<Long,Long> drink = new TreeMap<Long,Long>();
		for(int i = 0; i < n; i++) {
			long a = sc.nextLong();
			long b = sc.nextLong();
			if(drink.containsKey(a)) {
				drink.put(a,drink.get(a)+b);
			}
			else {
				drink.put(a, b);
			}
		}
		long ans = 0;
		for(long key:drink.keySet()) {
			int buy = (int) Math.min(m, drink.get(key));
			ans += buy*key;
			m -= buy;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 67916
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int MOD = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;

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

// value
int N, M;
int u[100010], v[10010];
int S, T;
vii g;
vi dist;

void bfs(int s, int t) {
	queue<int> q;
	dist[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int v = q.front(); q.pop();
		for (int i = 0; i < g[v].size(); i++) {
			if (dist[g[v][i]] == -1) {
				dist[g[v][i]] = dist[v] + 1;
				q.push(g[v][i]);
			}
		}
	}
}

void solve() {

	cin >> N >> M;
	g.resize(3 * (N + 1));
	dist.resize(3 * (N + 1), -1);
	for (int i = 0; i < M; i++) {
		cin >> u[i] >> v[i];
		g[u[i]].eb(N + v[i]);
		g[N + u[i]].eb(2 * N + v[i]);
		g[2 * N + u[i]].eb(v[i]);
	}
	cin >> S >> T;

	bfs(S, 0);

	if (dist[T] == -1) {
		cout << -1 << endl;
		return;
	}

	cout << dist[T] / 3<< endl;

	return;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

Measured memory_bytes: 18304
#include <iostream>
#include <string>
using namespace std;
int main() {
    int a[26]={0};
    string s;
    int b;
    while(getline(cin,s)){
        for (int i =0;i<s.size();i++){
            b=s[i];
            if ((s[i]>='A')&&(s[i]<='Z'))
                b+=32;
            a[b-97]++;
        }
    }
    char c='a';
    for (int i=0 ;i<26;i++){
        cout << c << " : " << a[i] << endl;
        c++;
    }
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>  
using namespace std;  
#define INF 0x3f3f3f3f  
typedef long long ll;  
const int N =  1010;  
#define FI first
#define SE second
typedef pair<int, int>pii;

int main()  
{  
//   freopen("in.txt","r",stdin);
   string ori;
   while (cin >> ori)
   {
   		int n = ori.size(), ans = 1000000;
   		for (int i = n - 1; i >= 0; i--)
   		{
   			string pre = ori;
   			int m = n;
   			int cur = 0;
	   		for (int k = 0; k < n; k++)
	   		{
   				string tmp = "";
   				int cnt = 0;
   				char s = pre[m-1];
   				for (int j = 0; j < m - 1; j++)
   				{
   					if (pre[j] == ori[i])
   					{
   						tmp = pre[j] + tmp;
   					}else if (pre[j+1] == ori[i])
   						tmp = pre[j+1] + tmp;
   					else
   					{
   						tmp = pre[j] + tmp;
   						
   					}
   					if (pre[j] != s)
   						cnt++;
   				}
   				m--;
   				if (cnt)
   					cur++;
   				pre = tmp;
  				// printf("%d ", cnt);	cout<<pre<<endl;

   				if (cnt == 0)
   					break;
   			}
   			ans = min(ans, cur);
   		}
   		printf("%d\n", ans);
   }
   return 0;  
}  

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.*;
public class Main {
	int N;
	int[] A,B;
	HashMap<Integer,Integer> a,b;
    public void solve() {
		N = nextInt();
		A = new int[N];
		B = new int[N];
		a = new HashMap<Integer,Integer>();
		b = new HashMap<Integer,Integer>();
		
		for(int i = 0;i < N;i++){
			A[i] = nextInt();
			a.put(A[i],i);
			
			B[i] = A[i];
		}
		Arrays.sort(B);
		for(int i = 0;i < N;i++){
			b.put(B[i],i);
		}
		int ans = 0;
		for(int key : b.keySet()){
			
			int aIndex = a.get(key);
			int bIndex = b.get(key);
			
			if(aIndex % 2 == 0 && bIndex % 2 == 1){
				ans++;
			}
		}
		
		out.println(ans);
    }
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
		/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

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

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

Measured memory_bytes: 45300
#include <stdio.h>
#include <string.h>

int main(void)
{
  char S[100];
  int i,count,n;

  scanf("%s",S);
  n=strlen(S);

  for(i=0;i<n;i++){
   if(S[i]!=S[n-1])
     count++;
     n--;
  }

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

  return 0;

 }


Measured memory_bytes: 128
import java.io.IOException;
import java.util.Scanner;
public class Main {
	static int mod=1000000007;
	static Scanner scan=new Scanner(System.in);
	static long gcd (long a, long b) {return b>0?gcd(b,a%b):a;}
	static long lcm (long a, long b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
			}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	static String reverce(String str) {
		String strr="";
		for(int i=str.length()-1;i>=0;i--) {
			strr+=str.charAt(i);
		}
		return strr;
	}
	static long modpow(long a,long n) {
		if(n==0) return 1;
		else if(n==1)return a;
		long tmp=modpow(a,n/2);
		tmp%=mod;
		tmp*=tmp;
		tmp%=mod;
		if(n%2==0)return tmp;
		else return (tmp*a)%mod;
	}
	public static void main(String[] args) throws IOException {
		String a=scan.next();
		if(a.length()==3) {
			System.out.println(""+a.charAt(2)+a.charAt(1)+a.charAt(0));
		}
		else {
			System.out.println(a);
		}
	}
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
    public static void debug(String str) {
        boolean debug = false;
        if (debug != false) {
            return;
        }
        System.out.println(str);
    }

    static long[] C1;
    static long[] C2;


    public static void main(String[] args) {

        int N;
        int K;
        int mod = 1000_000_007;

        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            K = sc.nextInt();
        }
        C1 = new long[N+1];
        C2 = new long[K+1];

        C1[0] = 1;
        C2[0] = 1;

        for (int i = 1; i <= (N-K)+1; i++)
        {
            // Fill entries of current row using previous
            // row values
            for (int j = (N-K)+1; j > 0; j--){
                // nCj = (n-1)Cj + (n-1)C(j-1);
                C1[j] = (C1[j] + C1[j-1])%mod;
            }
        }
        for (int i = 1; i <= K-1; i++)
        {
            // Fill entries of current row using previous
            // row values
            for (int j = K-1; j > 0; j--){
                // nCj = (n-1)Cj + (n-1)C(j-1);
                C2[j] = (C2[j] + C2[j-1])%mod;
            }
        }

        for(int i = 1;i< K+1;i++){
            long temp;
            temp = nCrModpLucas1((N-K)+1,i,mod);
            temp = (temp * nCrModpLucas2(K-1,i-1,mod))% mod;
            System.out.println(temp);
        }

    }


    static long nCrModpLucas1(int n, int r, int p)
    {
    // Base case
    if (r==0)
        return 1;

    // Compute last digits of n and r in base p
    int ni = n%p;
    int ri = r%p;

    // Compute result for last digits computed above, and
    // for remaining digits. Multiply the two results and
    // compute the result of multiplication in modulo p.
    return (nCrModpLucas1(n/p, r/p, p) * // Last digits of n and r
            C1[ri]) % p; // Remaining digits
    }

    static long nCrModpLucas2(int n, int r, int p)
    {
    // Base case
    if (r==0)
        return 1;

    // Compute last digits of n and r in base p
    int ni = n%p;
    int ri = r%p;

    // Compute result for last digits computed above, and
    // for remaining digits. Multiply the two results and
    // compute the result of multiplication in modulo p.
    return (nCrModpLucas2(n/p, r/p, p) * // Last digits of n and r
            C2[ri]) % p; // Remaining digits
    }



}


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


int main() {
	string s, t;
	cin >> s >> t;
	vector<int> rs(26, -1);
	vector<int> rt(26, -1);
	for (int i = 0; i < s.length(); i++)
	{
		int a = s[i] - 'a';
		int b = t[i] - 'a';

		if (rs[a] != -1 || rt[b] != -1) {
			if (rs[a] != b || rt[b] != a) {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			rs[a] = b;
			rt[b] = a;
		}
	}

	cout << "Yes" << endl;
}


Measured memory_bytes: 776