akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
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; }

// input
int N;
long long a[100010][3];

// DP table
long long dp[100010][3];

int main() {
    int N; cin >> N;
    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) cin >> a[i][j];

    // loop
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
            }
        }
    }

    // answer
    long long res = 0;
    for (int j = 0; j < 3; ++j) chmax(res, dp[N][j]);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>
int linearsearch(int A[],int n,int key){
  int i=0;
  A[n]=key;
  while(A[i]!=key)i++;
  if(i==n) return 0;
  return 1;
}
int main(){
  int i,n,A[10001],q,key,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(linearsearch(A,n,key)==1)sum++;
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

signed main(){
    int n, x;
    cin >> n >> x;
    int l = 2 * n - 1;
    if(x == 1 || x == l) o("No");
    else{
        o("Yes");
        int s = (x - n + l) % l;
        rep(i, 0, l){
            int tmp = (s + i) % l;
            o(tmp + 1);
        }
    }
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}

void calc(int a[],int f){
  for(int i=f*(f+1)*(f+2)/6;i<=1000000;i++){
    if(a[i]==0) a[i]=a[i-f*(f+1)*(f+2)/6]+1;
    else if(a[i]>a[i-f*(f+1)*(f+2)/6]+1) a[i]=a[i-f*(f+1)*(f+2)/6]+1;
  }
}

int x[1000001],b[1000001];
int main(){
  for(int i=1;i*(i+1)*(i+2)/6<1000000;i++){
    calc(x,i);
  }
  for(int i=1;i*(i+1)*(i+2)/6<1000000;i++){
    if(i*(i+1)*(i+2)/6%2==1){
    calc(b,i);
    }
  }
  while(1){
    int z;
    cin>>z;
    if(z==0) break;
    cout<<x[z]<<" "<<b[z]<<endl;
  }
  return 0;
}



Measured memory_bytes: 10892
H,W = map(int,input().split())

temp = [list(map(int,input().replace("#", "1").replace(".","0"))) for _ in range(H)]

cnt = 0


while cnt != 2:
    ans = []
    s = 0
    for row in temp:
        if sum(row) != 0:
            ans.append(row)
        else:
            s += 1
    if s == 0:
        cnt += 1
    else:
        cnt = 0
        
            
    temp = []
    for row in zip(*ans):
        temp.append(row)
    
    ans = []
    s = 0
    for row in temp:
        if sum(row) != 0:
            ans.append(row)
        else:
            s += 1
    if s == 0:
        cnt += 1
    else:
        cnt = 0
            
    temp = []
    for row in zip(*ans):
        temp.append(row)


for row in temp:
    res = list(map(str,row))
    res = ",".join(res).replace("1","#").replace("0",".").split(",")
    print("".join(res))
    



Measured memory_bytes: 3188
#include<iostream>
using namespace std;
int main()
{
  int w,a,b;
  cin >> w >> a >> b;
  int ans;
  if(a < b)
    ans = b - a -w;
  else
    ans = a - b -w;
  if(ans < 0)
    ans = 0;
  cout << ans << endl;

  return 0;
}


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

using namespace std;
const int N = 22222;

int n;
int p[N];
int a[N], b[N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		a[i] = i * n;
		b[i] = n * (n - i + 1);
	}
	for (int i = 1; i <= n; i++) a[p[i]] += i;
	for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
	for (int i = 1; i <= n; i++) printf("%d%c", b[i], " \n"[i == n]);
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>

int main(){
	int a,b,c;
	scanf("%d %d %d", &a,&b,&c);
	if(a>b){
		if(b>c)
			printf("%d %d %d\n",c,b,a);
		else{
			if(a>c)
				printf("%d %d %d\n",b,c,a);
			else
				printf("%d %d %d\n",b,a,c);
		}
	} else {
		if(a>c)
			printf("%d %d %d\n",c,a,b);
		else{
			if(b>c)
				printf("%d %d %d\n",a,c,b);
			else
				printf("%d %d %d\n",a,b,c);
		}
	}
	return 0;
}

Measured memory_bytes: 596
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

ll a[21234];
ll b[21234];
int p[21234];

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) a[i] = 1;
  for(int i = 0; i < n; i++) b[i] = -1;

  for(int i = 0; i < n; i++) {
    cin >> p[i], p[i]--;
    a[p[i]] += i;
    b[p[i]+1] -= i;
  }



  for(int i = 1; i < n; i++) a[i] += a[i-1];
  for(int i = 1; i < n; i++) b[i] += b[i-1];
  ll amin = a[0], bmin = b[0];
  for(int i = 0; i < n; i++) amin = min(amin, a[i]);
  for(int i = 0; i < n; i++) bmin = min(bmin, b[i]);
  for(int i = 0; i < n; i++) a[i] += 1 - amin;
  for(int i = 0; i < n; i++) b[i] += 1 - bmin;
  for(int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
  for(int i = 0; i < n; i++) cout << b[i] << " \n"[i == n - 1];
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

int main(){
    vector<ll> a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    ll k ; cin >> k;
    cout << a.at(k-1) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(long long x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<long long,long long> P;
typedef pair<long long,P> PP;
long long n;
long long ans;
long long k;
long long a[1000006];
int main()
{
	cin>>n>>k;
	rep(i,n)cin>>a[i+1];
	rep2(i,1,n+1)
	{
		if(a[i]+a[i-1]<=k)continue;
		ans+=a[i]-(k-a[i-1]);
		a[i]=(k-a[i-1]);
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);
  string ans(b, '0' + a);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	int i,n;cin>>n;
	vector<int>h(n);
	for(i=0;i<n;i++){cin>>h[i];}
	set<pair<int,llint>>dp;dp.ins(mp(0,0LL));
	for(i=0;i<n;i++){
		llint x;cin>>x;
		x+=prev(dp.lower_bound(mp(h[i],0LL)))->sec;
		auto itr=dp.ins(mp(h[i],x)).fir;
		while(next(itr)!=dp.end()&&next(itr)->sec<=x){dp.erase(next(itr));}
	}
	cout<<prev(dp.end())->sec<<endl;
	return 0;
}


Measured memory_bytes: 13568
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

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

typedef long long ll;

int hand(char c){
	string right = "yuiophjklnm";
	int n = right.length();
	REP(i,n){
		if (c == right[i])
			return 1;
	}
	return 0;
}

int main(void){
	int n;
	while (cin >> n && n){
		int ans = 0;
		int a = 3 , i = 2;
		while (a<=n){
			if ((n-a)%i==0)
				ans++;
			i++;
			a+=i;
		}
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1164
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int R = scanner.nextInt();
        int G = scanner.nextInt();
        int B = scanner.nextInt();
        int N = scanner.nextInt();

        System.out.println( RGBBox(R,G,B,N));
    }

    public static int RGBBox(int r, int g, int b, int n) {
        int cnt=0;
        for( int i=0 ; i<=n ; i+=r ) {
            for( int j=0 ; j<=n-i ; j+=g ) {
                if( (n-i-j)%b == 0) {
                    cnt++;
                }

            }
        }

        return cnt;
    }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;

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

    int ans = N;
    map<int,int> m;
    
    //お菓子を持っているをカウント
    for(int i = 0; i < K; ++i){
        for(int j = 0; j < d[i]; ++j){
            //key add
            if(m.count(A[i][j]) == 0) m.insert(make_pair(A[i][j],1));
        }
    }
    
    //Nから引く
    for(auto i = m.begin(); i != m.end(); ++i){
        //key: i->first, value: i->second
        ans--;
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define MAX 50
#define INFTY (1<<10)
class State {
public:
	int ty, tx, ky, kx, t;
	State(int ty = 0, int tx = 0, int ky = 0, int kx = 0, int t = 0) :
			ty(ty), tx(tx), ky(ky), kx(kx), t(t) {
	}
	bool operator <(const State &s) const {
		if (ty != s.ty)
			return ty < s.ty;
		if (tx != s.tx)
			return tx < s.tx;
		if (ky != s.ky)
			return ky < s.ky;
		if (kx != s.kx)
			return kx < s.kx;
		return false;
	}
};
int H, W, G[MAX][MAX];
bool isBlock(int y, int x) {
	if (0 > y || 0 > x || y >= H || x >= W)
		return true;
	return G[y][x];
}
int bfs(int ty, int tx, int ky, int kx) {
	queue<State> Q;
	map<State, bool> V;
	State start = State(ty, tx, ky, kx, 0);
	V[start] = true;
	Q.push(start);
	State u, v;
	const int dy[4] = { 0, -1, 0, 1 };
	const int dx[4] = { 1, 0, -1, 0 };
	int nty, ntx, nky, nkx;
	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		if (u.tx == u.kx && u.ty == u.ky)
			return u.t;
		for (int r = 0; r < 4; r++) {
			nty = u.ty + dy[r];
			ntx = u.tx + dx[r];
			nky = u.ky + dy[r] * (-1);
			nkx = u.kx + dx[r] * (-1);
			if (isBlock(nty, ntx)) {
				nty = u.ty;
				ntx = u.tx;
			}
			if (isBlock(nky, nkx)) {
				nky = u.ky;
				nkx = u.kx;
			}
			v = State(nty, ntx, nky, nkx);
			if (!V[v]) {
				v.t = u.t + 1;
				V[v] = true;
				Q.push(v);
			}
		}
	}
	return INFTY;
}
int main() {
	int tx, ty, kx, ky;
	while (cin >> W >> H && W) {
		cin >> tx >> ty >> kx >> ky;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				cin >> G[i][j];
		int t = bfs(ty - 1, tx - 1, ky - 1, kx - 1);
		if (t == INFTY)
			cout << "NA" << endl;
		else
			cout << t << endl;
	}
	return 0;
}

Measured memory_bytes: 14012
import sys

def main():
    k = int(input())
    a,b = map(int, input().split())
    n = "OK"
    for ai in range(a,b+1):
        if ai%k==0:
            n = "OK"
            break
            sys.exit()
        else:
            n="NG"
    print(n)
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 9180
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FScanner sc = new FScanner();
		int n = sc.nextInt();
		int[] ary = new int[n];
		for (int i = 0; i < n; i++) {
			ary[i] = sc.nextInt();
		}
		int cnt = 0;
		for (int i = 0; i < n - 2; i++) {
			int p1 = ary[i];
			int p2 = ary[i + 1];
			int p3 = ary[i + 2];
			if ((p1 < p2 && p2 < p3) || (p3 < p2 && p2 < p1)) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}

class FScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

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

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

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

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

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

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

Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
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 (b<a) {a=b; return 1;} return 0;}

int main(){
    string s;
    cin >> s;
    int n = s.size();
    ll sum = 0;
    for (int bit = 0; bit < 1<<n-1; ++bit) {
        ll cur = 0;
        rep(i, n) { 
            ll num = s[n-1-i] - '0';
            rep(j, cur) { 
                num *= 10;
            }
            sum += num;
            cur++;
            if (i == n) break;
            if (bit>>i&1) cur = 0;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	string s, t; cin >> s >> t;
	sort( s.begin(), s.end() );
	sort( t.begin(), t.end() );
	reverse( t.begin(), t.end() );
	cout << ( ( s < t ) ? "Yes" : "No" ) << endl;
}

Measured memory_bytes: 256
import heapq
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(M):
        a, b = map(int, input().split())
        heapq.heappush(Q, [b, a])
    
    cnt = 0
    x = 0
    while len(Q)!=0:
        b, a = heapq.heappop(Q)
        if x<a:
            cnt += 1
            x = b-1

    print(cnt)


if __name__ == '__main__':
    main()

Measured memory_bytes: 19572
s = input()
n = len(s)
for i in range(n-1):
    if i < n-2:
        if s[i] == s[i+1]:
            print(i+1,i+2)
            break
        elif s[i] == s[i+2]:
            print(i+1,i+3)
            break
        else:
            continue
    else:
        if s[i] == s[i+1]:
            print(i+1,i+2)
        else:
            print(-1,-1)


Measured memory_bytes: 39408
let () =
  let rec doit (x, y) r =
    match Scanf.scanf "%f,%f\n" (fun d t -> d, t) with
    | (0., 0.) -> Printf.printf "%d\n%d\n" (truncate x) (truncate y)
    | (d, t) -> let z = 3.1415926535897932 *. r /. 180. in doit (x +. d *. cos z, y +. d *. sin z) (r -. t)
  in
  doit (0., 0.) 90.

Measured memory_bytes: 2656
#include<iostream>
#include <algorithm>
using namespace std;
int main(){
  int N,K,i;
  
  long long int ans = 100000000000;
  long long int diff;
  cin >> N >> K;
  long long int A[N];
  for(i = 0;i<N;i++){
      cin>>A[i];
  }
  sort(A, A + N);
  for(i = 0;i<=N - K;i++){
      diff = A[i + K - 1] - A[i];
      if(ans > diff) ans = diff;
  }
  
  cout << ans << "\n";
  return 0;
}

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

ac = 0
wa = 0
tle = 0
re = 0

for i in range(n):
    s = str(input())
    if s == 'AC':
        ac += 1
    elif s == 'WA':
        wa += 1
    elif s == 'TLE':
        tle += 1
    else:
        re += 1

print('AC x '+str(ac))
print('WA x '+str(wa))
print('TLE x '+str(tle))
print('RE x '+str(re))

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n);
    vector<int> path;
    rep(i,m){
        int a, b;
        cin >> a >> b;
        --a; --b;
        if(i == 0){
            path.push_back(a);
            path.push_back(b);
        }
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<bool> used(n, false);
    for(auto x : path) used[x] = true;
    rep(i,2){
        while(true){
            bool flag = true;
            for(auto nv : G[path.back()]){
                if(!used[nv]){
                    used[nv] = true;
                    path.push_back(nv);
                    flag = false;
                    break;
                }
            }
            if(flag) break;
        }
        reverse(path.begin(), path.end());
    }
    cout << path.size() << endl;
    for(auto p : path){
        cout << p+1 << " ";
    }
    cout << endl;
	return 0;
}

Measured memory_bytes: 9316
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  n <- getInt
  qs <- VM.new n
  forM_ [0..(n-1)] $ \i -> do
    p <- getInt
    VM.write qs (p-1) i
  qs' <- V.freeze qs

  let solve i x m res
        | i >= n = res
        | otherwise = let y = qs' V.! i
                          m' | y > x = m + 1
                             | otherwise = 1
                          res' = max m' res
                      in solve (i+1) y m' res'

      nseq = solve 0 inf 0 0

      ans = n - nseq

  print ans


Measured memory_bytes: 8036
#include <stdio.h>

int main()
{
	 long n, t, touch[200000], i, sum;

	 sum = 0;

	scanf("%ld %ld", &n, &t);
	for (i = 0; i < n; i++)
		scanf("%ld", &touch[i]);

	for (i = 0; i < n; i++)
		if (i == n - 1)
		{
			sum += t;
		}

		else
		{
			if (touch[i + 1] - touch[i] >= t)
				sum += t;
			else sum += touch[i + 1] - touch[i];
		}

	printf("%ld\n", sum);

	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define int long long
const int MOD = 1e9 + 7;
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 5005;

int n, dp[maxn][maxn];    // dp[steps][filled]
string s;

int mod_expo(int x, int p)
{
    if(!p)
        return 1;
    int res = mod_expo(x, p / 2);
    res *= res;
    res %= MOD;
    if(p & 1)
        res *= x;
    return res % MOD;
}

int mod_inv(int x)
{
    return mod_expo(x, MOD - 2);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    assert(n <= 5000);
    dp[0][0] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(dp[i][j])
            {
                dp[i + 1][j + 1] += 2ll * dp[i][j];
                dp[i + 1][j + 1] %= MOD;
                if(j > 0)
                {
                    dp[i + 1][j - 1] += dp[i][j];
                    dp[i + 1][j - 1] %= MOD;
                }
                else 
                {
                    dp[i + 1][j] += dp[i][j];
                    dp[i + 1][j] %= MOD;
                }
            }
    int ans = dp[n][s.length()];
    ans *= mod_inv(mod_expo(2, (int)s.length()));
    ans %= MOD;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 120352
#include <stdio.h>

inline void gc(int *x) {
    *x = 0;
    for (;;) {
        int c = getc_unlocked(stdin);
        if ('0' <= c && c <= '9') {
            *x = *x * 10 + c - '0';
        } else {
            break;
        }
    }
}

#define KMAX (1000)
int s[KMAX + 1][2 * KMAX + 1];
int main(void) {
    char c;
    int n, k, x, y;
    scanf("%d %d\n", &n, &k);
    for (int i = 0; i < n; i++) {
        gc(&x);
        gc(&y);
        c = getc_unlocked(stdin);
        getc_unlocked(stdin);
        y %= 2 * k;
        if (c == 'W') {
            if (y >= k) {
                y -= k;
            } else {
                x += k;
            }
        } else {
            if (y >= k) {
                y -= k;
                x += k;
            }
        }
        x %= 2 * k;
        s[y + 1][x + 1]++;
    }
    for (int y = 0; y < k; y++) {
        for (int x = 0; x < 2 * k; x++) {
            s[y + 1][x + 1] += s[y][x + 1] + s[y + 1][x] - s[y][x];
        }
    }
    int max = 0;
    int v = s[0][0] - s[0][2 * k];
    for (int y = 0; y < k; y++) {
        int u = v - s[y][0] + s[y][2 * k];
        for (int x = 0; x < k; x++) {
            int t = u - s[0][x] - s[k][x] + s[0][x + k] + s[k][x + k] +
                    2 * s[y][x] - 2 * s[y][x + k];
            t = t < n / 2 ? n - t : t;
            max = t > max ? t : max;
        }
    }
    printf("%d\n", max);
    return 0;
}


Measured memory_bytes: 7936
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {
		new Main().run();
	}
	
	void run() {
		Scanner sc=new Scanner(System.in);
		String a=sc.next();
		String b=sc.next();
		String c=sc.next();
		System.out.println(a.charAt(a.length()-1)==b.charAt(0)&&b.charAt(b.length()-1)==c.charAt(0)?"YES":"NO");
	}
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
	
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int a,b,x;cin>>a>>b>>x;
    if(a>x){
        coutN; return 0;
    }
    if(a+b<x){
        coutN; return 0;
    }
    coutY;
}

Measured memory_bytes: 3624
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main() {
    int n;
    typedef tuple<int, int> t;
    vector<t> v;
    int inp;

    cin >> n;
    FOR(i, 1, n) {
        cin >> inp;
        v.push_back(make_tuple(i, inp));
    }

    sort(ALL(v), [](const auto &x, const auto &y) {
        return get<1>(x) < get<1>(y);
    });

    REP(i, n) {
        if (i != 0) {
            cout << " ";
        }
        cout << get<0>(v.at(i));
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1780
#include<bits/stdc++.h>
using namespace std;
#include <math.h>
#define ll long long 
// to increase precision
// std::cout<<std::fixed;
// 	std::cout<<std::setprecision(6)<<z;
#define max1 1000001

//long long int mod=1e18 ;




int main(){	
	int n;
	cin>>n;
	int k=n%10;
	if(k==3){
		cout<<"bon";
	}
	else if(k==0||k==1||k==6||k==8){
		cout<<"pon";
	}
	else{
		cout<<"hon";
	}

		
}
	
	
	
	





Measured memory_bytes: 3624
#include <cstdio>
#include <set>
using namespace std;
int main(){
    set<int> st;
    int n,x;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&x);
        if(st.count(x)==0)
            st.insert(x);
        else st.erase(x);
    }
    printf("%d\n",st.size());
    return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ll long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 200010
 
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}

void swapl(ll* a,ll* b){ll tmp=*a;*a=*b;*b=tmp;}
ll absl(ll a){if(a<0)return -a;return a;}
ll dupl(ll a,ll d){if(a%d==0)return a/d;else return a/d+1;}
ll modl(ll a,ll m){if(a<0)return a%m+m;else return a%m;}

ll GCD(ll a,ll b){ll c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
ll LCM(ll a,ll b){return a*b/GCD(a,b);}

ll factorial(ll n, ll m) {return n < m ? 1 : n*factorial(n-1, m);}

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

// ll dp[]

int main(){
  ll n, d;
  ll x, y;
  ll cnt = 0;

  scanf("%lld%lld", &n, &d);
  d = d*d;

  for(int i=0; i<n; i++){
      scanf("%lld %lld", &x, &y);
      if(x*x + y*y <= d){
          cnt++;
      }
  }
  printf("%lld", cnt);
  return 0;
}

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

dimensions = []
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        dimensions.append(a)
    dimensions.append(b)
inf = float('inf')
dps = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    dps[i][i] = 0
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            dps[i][j] = min(dps[i][j],
                            dps[i][k] + dps[k + 1][j] + (dimensions[i] * dimensions[k + 1] * dimensions[j + 1]))
print(dps[0][n - 1])



Measured memory_bytes: 5676
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int n;
vstr ans;
string alpha = "abcdefghijklmn";
void dfs(string s, int d) {
    if (d >= n) {
        set<char> st;
        int mx = 0;
        for (char c : s) {
            st.insert(c);
            mx = max(mx, c-'a'+1);
            if (st.size() < mx) return;
        }
        ans.push_back(s);
        return;
    }
    rep(i, d+1) dfs(s + alpha[i], d+1);
}

int main() {
    cin >> n;
    dfs("a", 1);
    for (string s : ans) cout << s << endl;
    return 0;
}

Measured memory_bytes: 7796
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long int ll;

class UnionFind{
    public:
        vector<ll> uni;
        UnionFind(ll s) : uni(s, -1) { }
 
       //頂点aが所属するグループを調べる
        ll root(ll a)
        {
            if (uni[a] < 0) return a;
            return uni[a] = root(uni[a]);
        }
    
        //頂点aと頂点bを繋ぐ。もともと同じグループの時falseを返す
        bool connect(ll a, ll b)
        {
            a = root(a);
            b = root(b);
            if (a == b) return false;
    
            if (uni[a] > uni[b])
            {
                a ^= b;
                b ^= a;
                a ^= b;
            }
    
            uni[a] = uni[a] + uni[b];
            uni[b] = a;
            return true;
        }
    
        //頂点a,bが同じグループであるかを調べる
        bool isConnect(ll a, ll b)
        {
            return root(a) == root(b);
        }
    
        //頂点aを含むグループの頂点数を調べる
        ll size(ll a)
        {
            return -uni[root(a)];
        }
};

int main(int argc, char const *argv[])
{
    ll n, m;
    cin >> n >> m;

    UnionFind u(n);

    stack<ll> a, b;
    for(ll i = 0; i < m; i++)
    {
        ll _a, _b;
        cin >> _a >> _b;
        a.push(_a), b.push(_b);
    }

    stack<ll> s;

    ll ans = n * (n - 1) / 2;
    s.push(ans);

    for (ll i = 0; i < m - 1; i++)
    {
        if (!u.isConnect(a.top() - 1, b.top() - 1)) {
            ans -= u.size(a.top() - 1) * u.size(b.top() - 1);
            u.connect(a.top() - 1, b.top() - 1);
        }
        s.push(ans);
        a.pop(), b.pop();
    }

    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
}


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

const int MAXN = 55;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];

int n, m, q;
vector<int> vec;

int ans = 0;

void solve(int x, int y) {
    if (x == n + 1) {
        int cur = 0;
        for (int i = 1; i <= q; i++) {
            if (vec[b[i]] - vec[a[i]] == c[i]) {
                cur += d[i];
            }
        }
        ans = max(ans, cur);
    } else {
        for (int i = y; i <= m; i++) {
            vec.push_back(i);
            solve(x + 1, i);
            vec.pop_back();
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &q);// don't forget &
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);// don't forget &
    }
    vec.push_back(0);
    solve(1, 1);
    printf("%d", ans);
    return 0;
}


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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll C[15][15];
//! iを1に変えるのに必要な魔力の最小値
ll T[15];
bool B[15];

struct Node
{
    Node(ll c, int i)
        : cost(c), i(i)
    {
    }
    ll cost;
    int i;
};

int main()
{
    int H, W;
    cin >> H >> W;
    REP(i, 10)
    {
        REP(j, 10)
        {
            cin >> C[i][j];
        }
    }

    priority_queue<Node, vector<Node>, function<bool(Node, Node)>> q([](Node a, Node b) { return a.cost > b.cost; });
    q.push(Node(0, 1));
    while (!q.empty())
    {
        Node t = q.top();
        q.pop();
        if (B[t.i])
            continue;
        B[t.i] = true;
        T[t.i] = t.cost;
        REP(i, 10)
        {
            if (B[i])
                continue;
            q.push(Node(t.cost + C[i][t.i],i));
        }
    }

    ll sum = 0;
    REP(h, H)
    {
        REP(w, W)
        {
            int a;
            cin >> a;
            if (a == -1)
                continue;
            sum += T[a];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <ios> 
#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
ll T;
ll a[100004],ans;
int main(){
	cin>>n>>T;
	ll minn=1e9+1;
	for (int i=0;i<n;i++){
		scanf ("%d",&a[i]);
		if (a[i]>minn)ans=max(ans,a[i]-minn);
		minn=min(minn,a[i]);
	}
	minn=a[0];ll res=0;
	for (int i=1;i<n;i++){
		if (a[i]>minn+ans-1){
			res+=a[i]-(minn+ans-1);
			a[i]=minn+ans-1;
		}
		minn=min(minn,a[i]);
	}
	cout<<res;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 55556;

bool prime[MAX];

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

    for (int i = 0; i < MAX; ++i) {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;

    bool first = true;
    int cnt = 0;
    for (int i = 2; i < MAX; ++i) {
        if (!prime[i]) continue;
        // TODO
        if ((i - 1) % 5 == 0) {
            if (first) {
                first = false;
            } else {
                cout << " ";
            }
            cout << i;
            cnt++;
            if (cnt == N) break;
        }
        for (int k = i + i; k < MAX; k += i) {
            prime[k] = false;
        }
    }
    cout << endl;
}

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

int main(){
  map<char, char> m;
  m['A'] = 'T';
  m['T'] = 'A';
  m['C'] = 'G';
  m['G'] = 'C';
  
  char b;
  cin >> b;
  cout << m[b] << endl;
  return 0;
}

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

using namespace std;

const int N = 2e5 + 3;

int n, k;
long long ans = 0;
long long cnt[N];

long long C2(long long n) {
	if (n < 2) return 0;
	return (n - 1) * n / 2;
}

long long C3(long long n) {
	if (n < 3) return 0;
	return n * (n - 1) * (n - 2) / 6;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		++cnt[i % k];	
	}	
	for (int i = 0; i < k; ++i) {
		if ((i + i) % k == 0) {
			ans += cnt[i]; // same  number
			ans += C2(cnt[i]) * 6;    // choose two numbers
			ans += C3(cnt[i]) * 6;					
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

const array<int, 4> dx = {0, 1, 0, -1};
const array<int, 4> dy = {1, 0, -1, 0};


typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);
}

int main()
{
	ios_init();
	int n;
	while(cin >> n) {
		vector<int> p(n);
		REP(i, n) cin >> p[i];
		int ans = 0;
		REP(i, n - 2) {
			vector<int> t(3);
			REP(k, 3) t[k] = p[i + k];
			sort(ALL(t));
			ans += (t[1] == p[i+1]);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;
const ll MAX_N = 3000;
/**/
int main() {
	// 入力
	ll N,M;cin>>N>>M;
	ll A[M];
    REP(i,M)cin>>A[i];
    
	// 解法
	ll ans = N;
	REP(i,M)ans -= A[i];
	if (ans<0) ans = -1;

	//出力
	printf("%lld\n", ans);
}


Measured memory_bytes: 3828
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using vi = vector<int>;
using vl = vector<int64_t>;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64_t INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

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

  int a, b; cin >> a >> b;
  if (a % 2 == 0 && b % 2 == 0) {
    cout << (a + b) / 2 << '\n';
  } else if (a & 1 && b & 1) {
    cout << (a + b) / 2 << '\n';
  } else {
    cout << "IMPOSSIBLE" << '\n';
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>

int main() {
  unsigned n, t;
  std::cin >> n >> t;
  std::vector<unsigned> A(n);
  for (auto &i : A) {
    std::cin >> i;
  }
  std::vector<unsigned> min(n);
  std::vector<unsigned> max(n);
  min[0] = *A.begin();
  max[n - 1] = A.back();
  for (unsigned i = 1; i < n; ++i) {
    min[i] = std::min(min[i - 1], A[i]);
    max[n - i - 1] = std::max(max[n - i], A[n - i - 1]);
  }
  std::vector<unsigned> diff(n);
  unsigned diff_max = 0u;
  for (unsigned i = 0; i < n; ++i) {
    diff[i] = max[i] - min[i];
    diff_max = std::max(diff[i], diff_max);
  }
  std::list<unsigned> index;
  for (unsigned i = 0; i < n; ++i) {
    if (diff[i] == diff_max) {
      index.push_back(i);
    }
  }
  unsigned cost = 0u;
  unsigned prev_min = UINT32_MAX;
  for (const auto &i : index) {
    if (prev_min != min[i]) {
      ++cost;
    }
    prev_min = min[i];
  }
  std::cout << cost;
  return 0;
}

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

int main() {
	string str;
	int n, k;
	cin >> n >> k;
	cin >> str;

	str = str.substr(0, k - 1) + char(int(str[k - 1]) + 32) + str.substr(k);
	cout << str << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

S = sum(A)
S_2 = sum(map(lambda x: x*x, A))

ans = (S*S - S_2)//2 #切り捨て除算にしないと結果をfloatで返してきやがるので

print(ans%(10**9 + 7))

Measured memory_bytes: 31632