akhauriyash/Code-Regression huggingface dataset:
N, A, B = map(int, input().split())
diff = B - A
if diff % 2 == 0:
    print(diff//2)
else:
    tmp1 = (B - A + 1) // 2
    tmp1 = B - tmp1
    tmp2 = (2 * N - B + A + 1) // 2 
    tmp2 = tmp2 - A
    print(min(N-A, B-1, tmp1, tmp2))


Measured memory_bytes: 2940
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
using namespace std;

struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k) {
	Node *y = NIL;
	Node *x = root;
	Node *z;
	
	z = (Node *)malloc(sizeof(Node));
	z->key   = k;
	z->left  = NIL;
	z->right = NIL;
	
	while(x != NIL) {
		y = x;
		if(z->key < x->key) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	
	z->parent = y;
	if(y == NIL) {
		root = z;
	} else {
		if( z->key < y->key) {
			y->left = z;
		} else {
			y->right = z;
		}
	}
}

void inorder(Node *u) {
	if(u == NIL) return;
	inorder(u->left);
	printf(" %d",u->key);
	inorder(u->right);
}
void preorder(Node *u) {
	if(u == NIL) return;
	printf(" %d",u->key);
	preorder(u->left);
	preorder(u->right);
}
	
int main(void) {
	int n, i, x;
	string com;
	scanf("%d",&n);
	
	for(i=0;i<n;i++) {
		cin >> com;
		if(com == "insert") {
			scanf("%d",&x);
			insert(x);
		} else if(com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}

	return 0;
}

/*
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print
*/


Measured memory_bytes: 26620
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
res = 1 
if 0 in a:
  res = 0
else:
  a.sort(reverse=True)
  for num in a:
    res *= num
    if res > 10**18:
      res = -1
      break
print(res)

Measured memory_bytes: 21652
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> class Graph2 {
public:
	static const T INF = numeric_limits<T>::max();
	int V, E; vector<vector<pair<int, T> > > G;
	Graph2() : V(0), E(0), G(vector<vector<pair<int, T> > >()) {}
	Graph2(int v) : V(v), E(0), G(vector<vector<pair<int, T> > >(v)) {}
	Graph2(vector<vector<pair<int, T> > > g) : V(g.size()), G(g) { for (int i = 0; i < g.size(); i++) E += g[i].size(); }
	int size() { return V; }
	void add1(int v1, int v2, T w) { G[v1].push_back(make_pair(v2, w)); E++; }
	void add2(int v1, int v2, T w) { add1(v1, v2, w); add1(v2, v1, w); }
	bool operator==(const Graph2& g) const { return G == g.G; }
	bool operator!=(const Graph2& g) const { return G != g.G; }
	vector<pair<int, T> > operator[](int x) { return G[x]; }
	T minspan() {
		vector<T> d(V, INF);
		vector<bool> used(V, false);
		priority_queue<pair<T, int> > que;
		for (int i = 0; i < V; i++) d[i] = INF;
		d[0] = 0; que.push(make_pair(0, 0));
		while (!que.empty()) {
			pair<T, int> pa = que.top(); que.pop();
			int u = pa.second; used[u] = true;
			for (int i = 0; i < G[u].size(); i++) {
				int v = G[u][i].first;
				if (d[v] > G[u][i].second && !used[v]) {
					d[v] = G[u][i].second; que.push(make_pair(-d[v], v));
				}
			}
		}
		T sum = 0;
		for (int i = 0; i < V; i++) sum += d[i];
		return sum;
	}
};
int V, E, s, t, w;
int main() {
	scanf("%d%d", &V, &E);
	Graph2<int> G(V);
	for(int i = 0; i < E; i++) {
		scanf("%d%d%d", &s, &t, &w);
		G.add2(s, t, w);
	}
	cout << G.minspan() << endl;
}

Measured memory_bytes: 6168
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
int n,i,j,k,a[N],head[N],adj[N*2],nxt[N*2],d[N];
ll w[N];
bool dfs(int x,int dad)
{
	if(!nxt[head[x]])
	{
		w[x]=a[x];
		return true;
	}
	long long s=0,mx=0;
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad)
		{
			if(!dfs(adj[y],x))
				return false;
			s+=w[adj[y]];
			mx=max(mx,w[adj[y]]);
		}
	ll B=s-a[x],A=2*a[x]-s;
	if(B<0||A<0||(mx>s/2&&B>s-mx))
		return false;
	w[x]=A;
	return true;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",a+i);
	if(n==2)
	{
		if(a[1]==a[2])
			printf("YES");
		else
			printf("NO");
		return 0;
	}
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&j,&k);
		adj[i*2-1]=k;
		nxt[i*2-1]=head[j];
		head[j]=i*2-1;
		adj[i*2]=j;
		nxt[i*2]=head[k];
		head[k]=i*2;
		++d[j],++d[k];
	}
	for(i=1;i<=n;++i)
		if(d[i]!=1)
			break;
	if(!dfs(i,-1)||w[i])
		printf("NO");
	else
		printf("YES");
	return 0;
}


Measured memory_bytes: 8960
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(std::string S)
{
    if (S == "Sunny")
    {
        cout << "Cloudy";
    }
    else if (S == "Cloudy")
    {
        cout << "Rainy";
    }
    else
    {
        cout << "Sunny";
    }
    cout << endl;
}

int main()
{
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

int main() {
  int H, W, i, j;
  char s;
  cin >> H >> W;
  
  int k=0;
  
  while(k<W+2){
    cout << "#";
    k++;
  }
  
  cout << endl;
  
  for (i = 0; i < H; i++) {
    cout << "#";
    for (j = 0; j < W; j++) {
      cin >> s;
      cout << s;
    }
    cout << "#" << endl;
  }
  
  k=0;
  
  while(k<W+2){
  	cout << "#";
    k++;
  }
  
  cout << endl;

}


Measured memory_bytes: 256
N,K=map(int,input().split())
S=input()

K-=1

if S[K]=="A":
   S=[c for c in S]
   S[K]="a"
   print("".join(S))

elif S[K]=="B":
   S=[c for c in S]
   S[K]="b"
   print("".join(S))

else:
   S=[c for c in S]
   S[K]="c"
   print("".join(S))

Measured memory_bytes: 3064
N,K,Q=map(int,input().split())
if K>Q:
  for i in range(0,N):
    print('Yes')
else:
  peoplepoints=[]
  for i in range(0,N):
    peoplepoints.append(0)
  for i in range(0,Q):
    temp=int(input())
    peoplepoints[temp-1]=peoplepoints[temp-1]+1
  for i in range(0,N):
    if peoplepoints[i]>Q-K:
      print('Yes')
    else:
      print('No')

Measured memory_bytes: 4620
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,W;
  cin>>n>>W;
  vlong w(n+10),v(n+10);
  rep(i,n){
    cin>>w[i+1]>>v[i+1];
  }
  vector<vector<long long> > dp(n+100,vector<long long>(W+100,0));
  dp[0][0]=0;
  REP(i,1,n+1){
    REP(j,1,W+1){
      dp[i][j]=dp[i-1][j];
      if(j-w[i]>=0){
        chmax(dp[i][j],dp[i-1][j-w[i]]+v[i]);
      }
      //chmax(dp[i][j],dp[i][j-1]);
    }
  }
  cout<<dp[n][W]<<'\n';
  return(0);
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1e5+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {

}

int n, k;
string s;

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

    cin >> n >> k;
    cin >> s;

    int i = 0;
    int lSub = 0, rSub = 0;
    int specL = 0, specR = 0;

    int ans = 0;
    for (int i=1; i<n; i++) {
        if (s[i] == s[i-1]) ans++;
    }

    while (i < n) {
        int start = i;
        while (i < n && s[i] == s[start]) i++;

        if (s[start]=='L') {
            lSub++;
            continue;
        }
        if (s[start]=='R') {
            rSub++;
            continue;
        }
    }

    ans += 2 * min(k, min(lSub, rSub));
    k -= min(lSub, rSub);

    if (ans >= n) ans = n-1;
    cout << ans;

    return 0;
}


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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	for(int n;cin>>n&&n;){
		vi f(26);
		string s; cin>>s;
		for(char c:s) f[c-'a']++;
		rep(_,n-1){
			cin>>s;
			vi g(26);
			for(char c:s) g[c-'a']++;
			rep(i,26)
				f[i]=min(f[i],g[i]);
		}
		string res;
		rep(i,26) res+=string(f[i],'a'+i);
		cout<<res<<endl;
	}
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		String str=in.nextLine(),key=in.nextLine();
		int i=0;
		while(true) {
			int p=str.indexOf(key, i);
			if(p==-1)break;
			System.out.println(p);
			i=p+1;
		}
	}

}



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

int main()
{
	int a,b;
	cin >> a >> b;
	if (a > b)
		cout << "a > b" << endl;
	else if(a < b)
		cout << "a < b" << endl;
	else
		cout << "a == b" << endl;
	return 0;
}



Measured memory_bytes: 3076
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new MyInputStream(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(MyInputStream cin)
        {
            var H = cin.ReadInt();
            var W = cin.ReadInt();
            var a = cin.ReadStrArray(H);
            WriteLine(string.Join("", Enumerable.Repeat('#', W + 2)));
            a.Select(s => $"#{s}#").ToList().ForEach(WriteLine);
            WriteLine(string.Join("", Enumerable.Repeat('#', W + 2)));
        }
    }

    public class MyInputStream
    {
        private readonly System.IO.TextReader _stream;
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(System.IO.TextReader s, char separator = ' ')
        {
            this.separator = separator;
            this._stream = s;
            inputStream = new Queue<string>();
        }
        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = _stream.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
        public string ReadLine() { return _stream.ReadLine(); }
        public int ReadInt() { return int.Parse(Read()); }
        public long ReadLong() { return long.Parse(Read()); }
        public double ReadDouble() { return double.Parse(Read()); }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read(); return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt(); return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong(); return ret;}
    }
}

Measured memory_bytes: 13524
n = int(input())
a = [int(x) for x in input().split()]

for i in range(n):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v
    print(" ".join(map(str,a)))

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

int main(){
    int k;
    cin>>k;
    string s;
    cin>>s;
    if(s.size()>k){
        for(int i=0;i<k;++i){
            cout<<s[i];
        }
        cout<<"..."<<endl;
    }
    else{
        cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 3600
#include "bits/stdc++.h"
using namespace std;

int main()
{
	int64_t a, b, k;
	cin >> a >> b >> k;

	if (k <= a) {
		a -= k;
	} else if (k <= a + b) {
		b -= (k - a);
		a = 0;
	} else {
		a = 0;
		b = 0;
	}

	cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

signed main() {
    int n;
    while (cin >> n) {
	if (!n) break;

	int ret = 0;
	REP(i, 1, n / 2) {
	    int sum = 0;
	    rep(j, n) {
		sum += i + j;
		if (sum == n) {
		    ret++;
		    break;
		}
		if (sum > n) {
		    break;
		}
	    }
	}
	cout << ret << endl;
    }

    return 0;
}

Measured memory_bytes: 3040
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
	int H, W;
	cin >> H >> W;

	for (int i = 0; i < W + 2; i++) printf("#");
	printf("\n");
	for (int i = 0; i < H; i++) {
		string S;
		cin >> S;
		cout << '#' << S << '#' << endl;
	}
	for (int i = 0; i < W + 2; i++) printf("#");
	printf("\n");
	return 0;
}

Measured memory_bytes: 256
def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    digit = len(str(bin(K)))-2
    digits1 = [0]*digit
    ans = 0
    for a in A:
        ans += a-a%(1<<digit)
        for i in range(digit):
            if a&1<<i:
                digits1[i] += 1
    x = 0
    for i in range(digit-1,-1,-1):
        if digits1[i]<N/2 and x+(1<<i) <=K:
            x += 1<<i
            ans += (1<<i)*(N-digits1[i])
        else:
            ans += (1<<i)*digits1[i]
    return ans
print(solve())

Measured memory_bytes: 14712
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 2e3+17;
int main(int argc ,char const *argv[])
{
	#ifdef noob
	freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
	#endif		
	LL a,b,c,d,e,f,g;
	cin>>a>>b>>c>>d>>e>>f>>g;
	LL ans = b;
	if((a&1)&&(d&1)&&(e&1))
		ans += a/2*2+d/2*2+e/2*2+3;
	else if(e&&(a&1)&&(d&1)&&(e%2==0))
		ans += a/2*2+d/2*2+(e-1)/2*2+3;
	else if(d&&(a&1)&&(d%2==0)&&(e&1))
		ans += a/2*2+(d-1)/2*2+e/2*2+3;
	else if((a&1)&&(d%2==0)&&(e%2==0))
		ans += a/2*2+d/2*2+e/2*2;
	else if(a>0&&(a%2==0)&&(d&1)&&(e&1))
		ans += (a-1)/2*2+d/2*2+e/2*2+3;
	else 
		ans += a/2*2+d/2*2+e/2*2;
	cout<<ans<<endl;
	return 0;		
}

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

map<pair<int,int>,int> m;

int main(void){
	int H,W,N;
	cin >> H >> W >> N;
	for(int i=0;i<N;i++){
		int x,y;
		cin >> x >> y;
		for(int a=0;a<3;a++){
			for(int b=0;b<3;b++){
				int nx = x-a;
				int ny = y-b;
				if(nx<1||ny<1||nx>H-2||ny>W-2)continue;
				m[pair<int,int>(nx,ny)]++;
			}
		}
	}
	for(int i=0;i<10;i++){
		ll ans = 0;
		for(auto x:m){
			if(x.second==i)ans++;
		}
		if(i==0){
			ans = (ll)(H-2)*(W-2) - m.size();
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 56448
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


int main() {
	vector<string> v = { "SUN","MON","TUE","WED","THU","FRI","SAT" };
	map<string, int> m;
	for (int i = 0; i < 7; i++) {
		m[v[i]] = 7 - i;
	}
	string s; cin >> s;
	cout << m[s] << endl;
	return 0;
}

Measured memory_bytes: 764
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

int main(){

    size_t n;
    std::cin >> n;

    std::vector<size_t> h(n);

    for(auto&& e : h){
        std::cin >> e;
    }

    size_t cnt = 0;

    while(std::accumulate(h.begin(), h.end(), 0ul) != 0){
        auto first = std::find_if(h.begin(), h.end(), [](size_t x){ return x != 0; });
        auto second = std::find(first, h.end(), 0);

        std::for_each(first, second, [](size_t& x){ x--; });
        
        cnt++;
    }

    std::cout << cnt << std::endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
dic = {}
for i in range(n):
  p = int(input())
  if p - 1 in dic:
    dic[p] = dic[p - 1] + 1
  else:
    dic[p] = 1
Max = 0
for i in range(1, n + 1):
  di = dic[i]
  if di > Max:
    Max = di

print(n - Max)


Measured memory_bytes: 32648
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;


import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final long A = sc.nextLong();
			final long V = sc.nextLong();
			final long B = sc.nextLong();
			final long W = sc.nextLong();
			
			final long T = sc.nextLong();
			
			if(V <= W) {
				System.out.println("NO");
				return;
			}
			
			final long abs = Math.abs(A - B);
			final long acc = V - W;
			final long turn = (abs + acc - 1) / acc;
			
			if(turn <= T) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
			
			
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

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

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

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}


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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REPR(i,a,b) for(ll i=b;i>=a;i--)
#define repr(i,n) REPR(i,0,n)
#define All(v) (v).begin(), (v).end()
#define Pb push_back

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

    ll n,ans; cin >> n;
    ans = n * 800;
    ans -= 200 * (n/15);
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n, m, l;
    cin >> n >> m >> l;
    int a, b, c;
    if (n >= m) {
        if (m >= l) {a = n; b = m; c = l;}
        else if (l >= n) {a = l; b = n; c = m;}
        else {a = n; b = l; c = m;}
    }
    else {
        if (n >= l) {a = m; b = n; c = l;}
        else if (l >= m) {a = l; b = m; c = n;}
        else {a = m; b = l; c = n;}
    }
    cout << 10 * a + b + c << endl;
        return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
  for (x=nc();!(x>='a' && x<='z');x=nc());
}

const int N=1005;

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

int main(){
  char order;
  read(n);
  for (int i=1;i<=n;i++){
    read(order); read(a[i]);
    if (order=='y') b[i]=1;
  }
  for (int i=1;i<=n;i++){
    int t=0;
    for (int j=1;j<=n;j++)
      if (b[j] && (!t || a[j]<a[t]))
	t=j;
    if (!t) break;
    for (int j=t-1;j;j--)
      if (!b[j] && a[j]>=a[t])
	break;
      else if (b[j])
	a[j]=-1;
    for (int j=t+1;j<=n;j++)
      if (!b[j] && a[j]>=a[t])
	break;
      else if (b[j])
	a[j]=-1;
    a[t]=-1;
    int pnt=0;
    for (int j=1;j<=n;j++)
      if (a[j]!=-1)
	a[++pnt]=a[j],b[pnt]=b[j];
    n=pnt;
    ++ans;
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 2700
#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define setDP(arr) memset(arr,-1,sizeof arr)
#define Clear(arr) memset(arr,0,sizeof arr)
#define oo 1000000000
#define inf 1000000000000000000
#define M 1000000007
#define M2 1000000009
#define pii pair<ll,ll>
using namespace std;
typedef long long ll;
const int N = 2e5+100;
const int SQRTN = 320;
const int LOGN = 20;
const double PI = acos(-1);
const double TAU = 2*PI;

int n , m , a[N];
bool done[N];
int x;
string s;
inline void solve(){
    cin >> n >> m ;
    while(m--){
        cin >> x >> s;
        if(s[0]=='A')done[x]=1;
        if(done[x])continue;
        a[x]++;
    }
    int aa,ab;
    aa=ab=0;
    for(int i = 0 ; i <= n ; i++){
        if(!done[i])continue;
        aa++;
        ab+=a[i];
    }
    cout << aa << ' ' << ab << endl;


}

signed main() {
	int t=1;
	while(t--){
		solve();
	}
    return 0;
}


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

int main() {
  int n, k, p;
  cin >> n;
  int res[n] = {0};
  for(int i=0; i<n; ++i) {
    cin >> k >> p;
    if(k % p == 0) res[i] = p;
    else res[i] = k % p;
  }
  for(int i=0; i<n; ++i) {
    cout << res[i] << endl;
  }

}




Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
#include<map>
#define MEM(var,val) memset(var,(val),sizeof(var))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define nitro   ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define F first
#define S second
int  main()
{
    nitro;
    ll n;
    cin>>n;
    ll num=100,d=0;
    while(num<n)
    {
        num=num+num/100;
        d++;
    }
    cout<<d;

}


Measured memory_bytes: 3652
// Best practice
 
#include<bits/stdc++.h>
 
#define int         long long
#define pb          push_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define pii 		pair<int,int>
#define psi 		pair<string,int>
#define vi 			vector<int>
#define vpii  		vector<pii>
#define vvi 		vector<vi>
#define sz(x)	    (int)(x).size()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007
#define hell        998244353
#define prec(n) 	fixed<<setprecision(n)
#define ini(a, i) 	memset(a, i, sizeof(a))
#define output(x)   cout << (x ? "YES" : "NO")<<endl;
using namespace std;
 
#define debug(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<i<<" "; cout<< "]" << endl
#define debugp(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<"("<<i.x<<","<<i.y<<")"<<" "; cout<< "]" << endl
#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << "[" << *it << ": " << a << "]\t";
    err(++it, args...);
}
 
// const int dx[4] = { -1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// int dX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
// int dY[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
 
// Code from Here -------------------------------------------------------------------------------


signed main() {
	tezz
 
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif

	int n;
	cin >> n;
	int a[n];
	int pre[n];
	for(int i=0; i<n; i++){
		cin >> a[i];
		if(i==0)pre[i]=a[i];
		else pre[i] = pre[i-1] + a[i];
	}
	int dp[n][n];	
	ini(dp, 0);
	for(int i=n-1; i>=0; i--){
		for(int j=i; j<n; j++){
			dp[i][j]=LLONG_MAX;
			if(i==j){
				dp[i][j] = 0;
			}		
			else{
				for(int k=i; k<j; k++){
					dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-(i==0 ? 0 :pre[i-1]));
				}
			}
		}
	}
	cout << dp[0][n-1] << endl;
 
	return 0;
}  

Measured memory_bytes: 4880
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+6, M = 1e5+5, OO = 0x3f3f3f3f;
int arr[N];
 int i=10,t=11;
int main(){

    iota(arr,arr+10,0);


    while(t<100){
        arr[i++]=t;
        t+=11;}

   for(t=101;t<1000;t+=101)
        for(int p=0;p<=90;p+=10)
            arr[i++]=t+p;

   for(t=1001;t<10000;t+=1001)
        for(int p=0;p<=990;p+=110)
            arr[i++]=t+p;
    for(t=10001;t<100000;t+=10001)
        for(int p=0;p<=9990;p+=1010)
            for(int c=0;c<=900;c+=100)
            arr[i++]=t+p+c;

    int l,r;
    scanf("%d %d",&l,&r);
    printf("%d\n",upper_bound(arr,arr+i,r)-lower_bound(arr,arr+i,l));

return 0;
}


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

int main() {
  char c;
  cin >> c;
  
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  }
    
    else {
      cout << "consonant" << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] In1 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int h = In1[0];
            int w = In1[1];
            int[] In2 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int x = In2[0];
            int y = In2[1];
            Console.WriteLine((h - x) * (w - y));
        }
    }
}


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

long long N,K,arr[200001];

long long cmp(int a, int b){
	return a>b;
}

int main(){
	cin>>N>>K;
	for(long long i=0; i<N; i++){
		cin>>arr[i];
	}
	sort(arr,arr+N);
	long long l=1,r=1000000000,sol=-1;
	while(l<=r){
		long long mid=(l+r)/2;
		long long total=0;
		for(long long i=0; i<N; i++){
			total+=((arr[i]+mid-1)/mid)-1;
		}
		if(total>K){
			l=mid+1;
		}else{
			r=mid-1;
			sol=mid;
		}
	}
	cout<<sol<<'\n';
}

Measured memory_bytes: 5112
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,c,x;
  int y[10000];
  int cnt,ans,i;
  while(1){
    for(int i=0;i<10000;i++){
      y[i]=0;
    }
    cnt=ans=0;
    cin>>n>>a>>b>>c>>x;
    if(n==0 && a==0 && b==0 && c==0 && x==0) break;
    for(int i=0;i<n;i++){
      cin>>y[i];
    }
    i=0;
    while(cnt<n){
      if(x==y[i]){
	cnt++;
	y[i]=-1;
	i++;
      }
    x=(a*x+b)%c;
    if(cnt<n) ans++;
    if(ans==10001) break;
    }
    if(ans==10001) cout<<-1<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3132
#!/usr/bin/env python3

N = int(input())
CSF = []
for n in range(N-1):
    s = input()
    CSF.append([int(x) for x in s.split()])

for j in range(N - 1):
    time = 0
    for i in range(N - 1 - j):
        c, s, f = CSF[i + j]
        n = max(0, (time - s + f - 1) // f)
        time = s + n * f + c
    print(time)
print(0)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1000000000
#define mod 1000000007
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
int kaijo(int n){
	int ans=1;
	for(int i=2;i<=n;i++){
		ans*=i;
		ans%=mod;
	}
	return ans;
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%mod;
	return modpow(a,b/2)*modpow(a,b/2)%mod;
}
double a,b;
signed main(){
	cin>>a>>b;
	printf("%.12lf\n",a/b);
	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    var (n, m) = readLine()!!.split(" ").map { it.toInt()}
    var min = 1
    var max = n
    for (i in 0 until m){
        var (l, r) = readLine()!!.split(" ").map { it.toInt()}
        if (min < l) min = l
        if (max > r) max = r
    }
    println(if (max - min + 1 < 0) 0 else max - min + 1)
}

Measured memory_bytes: 55780
def snakeA(s):
    if s.startswith(">'") and s.endswith("~"):
        if s.count("#")==1:
            t=s[2:-1].split("#")
            if len(t)==2 and t[0]==t[1]:
                if set(list(t[0]))==set(list(t[1]))==set(["="]):
                    return True
    return False

def snakeB(s):
    if s.startswith(">^") and s.endswith("~~"):
        t=s[2:-2].split("Q=")
        if len(t)>1 and set(t)==set([""]):
            return True
    return False

for i in range(input()):
    s=raw_input()
    if snakeA(s):
        print "A"
    elif snakeB(s):
        print "B"
    else:
        print "NA"

Measured memory_bytes: 4280
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;

bool vis[30][30];

int main() {
	int H, W; cin >> H >> W;
	vector<string> s(H + 2);
	s[0] = s[H + 1] = string(W + 2, '#');
	for (int i = 1; i <= H; i++) {
		cin >> s[i];
		s[i] = '#' + s[i] + '#';
	}
	vector<int> dx = { 0, 1, 0, -1, 0 };
	auto func = [&](pair<int, int> st, pair<int, int> gl) -> int {
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				vis[i][j] = false;
			}
		}

		deque<pair<pair<int, int>, int>> que;
		que.emplace_back(st, 0);
		while (!que.empty()) {
			auto p = que.front();
			que.pop_front();
			auto &pos = p.first;
			auto &dis = p.second;
			if (vis[pos.first][pos.second]) continue;
			vis[pos.first][pos.second] = true;

			if (pos == gl) return dis;

			for (int i = 0; i < 4; i++) {
				pair<int, int> nxt(pos.first + dx[i], pos.second + dx[i + 1]);
				if (s[nxt.first][nxt.second] == '#') continue;
				if (vis[nxt.first][nxt.second]) continue;
				que.emplace_back(nxt, dis + 1);
			}
		}
	};
	int ans = 0;
	for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) {
		if (s[i][j] == '#') continue;
		for (int k = 1; k <= H; k++) for (int l = 1; l <= W; l++) {
			if (s[k][l] == '#') continue;
			if (i == k && j == l) continue;
			int ret = func({ i, j }, { k, l });
			ans = max(ans, ret);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (ll i=a;i<=b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define mod 998244353
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=100000+5;
char grid[405][405]= {};
bool vis[405][405]= {};
int h,w;
ll blacks=0,whites=0;
inline bool valid(int r,int c,bool black)
{
    if (r<=h&&r>=1&&c<=w&&c>=1&&!vis[r][c])
    {
        if (black&&grid[r][c]=='.')
            return true;
        if (!black&&grid[r][c]=='#')
            return true;
    }
    return false;
}
void dfs(int r,int c,bool black)
{
    vis[r][c]=true;
    if(black)
        blacks++;
    else
        whites++;
    lp(i,-1,1)
    {
        lp(j,-1,1)
        {
            if(i!=j&&(!i||!j))
            {
                int nr=r+i;
                int nc=c+j;
                if (valid(nr,nc,black))
                    dfs(nr,nc,black^1);
            }
        }
    }
}
int main()
{
#ifdef ONLINE_JUDGE
    FAST;
#endif
    cin>>h>>w;
    ll ans=0;
    lp(i,1,h)
    lp(j,1,w)
    cin>>grid[i][j];
    lp(i,1,h)
    {
        lp(j,1,w)
        {
            if (!vis[i][j]&&grid[i][j]=='#')
            {
                dfs(i,j,true);
                ans+=(blacks*whites);
                blacks=whites=0;
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 13056
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    int a,b,n,k,x,y,i,j;
    scanf("%d",&n);
    b=n/111;
    if(n%111!=0){
    a=(b+1)*111;}else{
        a=(b*111);
    }
    printf("%d",a);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<typename T> inline istream& operator>>(istream &i, vector<T> &v) {rep(j, size(v)) i >> v[j]; return i;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> T gcd(T a, T b) {if(b==0)return a; else return gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return a/gcd(a,b)*b;}
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = size(s);
    cout << s[0] << n - 2 << s[n - 1] << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define time cerr << (0.1 * clock()) / CLOCKS_PER_SEC << endl;
#define mod 1000000007
typedef long long ll;
typedef pair<ll, ll> pl;
#define forn(n) for (ll i = 0; i < ll(n); i++)

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> v(n);
    forn(n) {
        cin >> v[i];
    }
    vector<ll> dp(n, 1e15);
    set<pl> s;
    dp[0] = 0;
    s.insert({0, 0});
    for (int i = 1; i < n; ++i) {
        s.insert({dp[i], i});
    }
    while (!s.empty()) {
        auto temp = *(s.begin());
        s.erase(s.find(temp));
        for (int i = temp.second + 1; i < n and i <= temp.ss + k; ++i) {
            if (dp[i] > temp.first + (abs(v[i] - v[temp.second]))) {
                s.erase({dp[i], i});
                dp[i] = temp.first + (abs(v[i] - v[temp.second]));
                s.insert({dp[i], i});
            }
        }
    }
    cout << dp[n - 1] << '\n';
}

int main() {
    quick;
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
}

Measured memory_bytes: 8064
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
using namespace std;

int main(void)
{
	long long n;
	vector<long long> a;

	scanf("%lld", &n);
	a.resize(n);
	for (int i=0; i<n; i++){
		scanf("%lld", &a[i]);
	}

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

	bool flag=false;
	int i=0;
	while(!flag && i<n-1){
		if (a[i] ==  a[i+1]){
			flag = true;
		}
		i++;
	}

	if (flag) printf("NO\n");
	else printf("YES\n");

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int number;
  string train;
  cin >> number;
  while(cin >> train){
    set<string> type;
    string front, back;
    int size = train.size();
    for (int i = 0; i < size-1; i++){
      front = train.substr(0, i+1);
      back = train.substr(i+1, size-1-i);
      type.insert(front + back);
      type.insert(back + front);
      reverse(front.begin(), front.end());
      type.insert(front + back);
      type.insert(back + front);
      reverse(back.begin(), back.end());
      type.insert(front + back);
      type.insert(back + front);
      reverse(front.begin(), front.end());
      type.insert(front + back);
      type.insert(back + front);
    }
    cout << type.size() << endl;
  }
}

Measured memory_bytes: 3164
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
#define int long long
vector<int> vertexs[300000];
long long ans[300000];
map<pair<long long, long long>, long long> memo;
long long dfs2(long long now, long long back, long long c) {
	if (memo.find(make_pair(now, c)) != memo.end()) return memo[make_pair(now, c)];
	int res = 1;
	for (auto x : vertexs[now]) {
		if (x == back) continue;
		if (x > c) continue;
		res += dfs2(x, now, c);
	}
	return memo[make_pair(now, c)] = res;
}
void dfs(long long now, long long back, long long backback) {
	if (backback > now) {
		ans[now] = ans[back] - dfs2(now, back, backback) + dfs2(now, back, max(back, backback));
	}
	else {
		ans[now] = ans[back] + dfs2(now, back, max(back, backback));
	}
	for (auto x : vertexs[now]) {
		if (x == back) continue;
		dfs(x, now, max(back, backback));
	}
}
#undef int
int main() {
#define int long long
	iostream::sync_with_stdio(false);
	int n;
	cin >> n;
	REP(i, n-1) {
		int a, b;
		cin >> a >> b;
		vertexs[a].push_back(b);
		vertexs[b].push_back(a);
	}
	ans[1] = 1;
	for (auto x : vertexs[1]) {
		dfs(x, 1, -1);
	}
	for (int i = 2; i <= n; ++i) {
		if (i != 2) cout << " ";
		cout << ans[i]-1;
	}
	cout << endl;
}

Measured memory_bytes: 47744
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<vector>
#include<set>
#include<map>
#include<deque>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1010;
pii start,ed;
int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];
void bfs()
{
    memset(dist,0x3f,sizeof dist);
    deque<pii> q;
    dist[start.x][start.y]=0;
    q.push_front(start);
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    while(q.size())
    {
        auto t=q.front();q.pop_front();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y]=1;
        int d=dist[t.x][t.y];
        int a,b;
        for(int i=0;i<4;i++)
        {
            a=t.x+dx[i],b=t.y+dy[i];
            if(a<1||b<1||a>n||b>m||g[a][b]=='#'||dist[a][b]<=d) continue;
            dist[a][b]=d;
            q.push_front({a,b});
        }
        for(int i=t.x-2;i<=t.x+2;i++)   
        {
            if(i<1||i>n) continue;
            for(int j=t.y-2;j<=t.y+2;j++)
            {
                if(j<1||j>m||g[i][j]=='#'||dist[i][j]<=d+1) continue;
                dist[i][j]=d+1;
                q.push_back({i,j});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    cin>>start.x>>start.y;
    cin>>ed.x>>ed.y;
    for(int i=1;i<=n;i++) cin>>g[i]+1;
    bfs();
    if(dist[ed.x][ed.y]==0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dist[ed.x][ed.y]<<endl;
    return 0;
}

Measured memory_bytes: 9548
#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

int main(){
  	string S;
    cin >> S;
	int size = 4;
  	int kind = 0;
    char first_char = '0';
  	char second_char = '0';
    int first_count = 0;
  	int second_count = 0;
  
  	for (int i = 0; i < size; i++){
      if (i == 0){
        first_char = S[i];
        first_count++;
      }
      else{
        if (S[i] == first_char){
          first_count++;
        }
        else{
          if (second_char == '0'){
            second_char = S[i];
            second_count++;
          }
          else if (S[i] == second_char){
            second_count++;
          }
        }
      }
    }
  	
  	string res;
  	if (first_count == 2 && second_count == 2){
      res = "Yes";
    }
  	else {
      res = "No";
    }
    cout << res << endl;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==1:
  print(0)
  exit()
if k==1:
  tentou=0
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i]>a[j]:
        tentou+=1
  print(tentou)
  exit()

t=[0 for _ in range(n)]
tentou=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      tentou+=1
      t[i]+=1
    if a[j]>a[i]:
      t[j]+=1
coef=((k-1)*k//2)%1000000007
ti=sum(t)*coef%1000000007
te=tentou*k%1000000007
print((ti+te)%1000000007)

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

int max(int a,int b){
  if(a>b) return a;
  else return b;
}
double min(double a,double b){
  if(a<b) return a;
  else return b;
}
int absolute(int a,int b){
  if(a-b<0) return -(a-b);
  else return a-b;
}
int sum_keta(int n){
  if(n==0) return 0;
  return n%10 + sum_keta(n/10);
}
int main(void){
  int X,Y,Z; cin >> X >> Y >> Z;
  int ans;
  
  ans = X/(Y+Z);
  if(X-ans*(Y+Z) < Z) ans--;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 2e9;
 
int main(){
    int n, k;
    vector<int> h, dp;
    cin >> n >> k;
    h.resize(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    dp.resize(n);
    dp[0] = 0;
    for(int i=1; i<n; i++){
        dp[i] = INF;
        for(int j=i-k; j<i; j++){
            if(j<0) j=0;
            dp[i] = min(dp[i],abs(h[i]-h[j])+dp[j]);
        }
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int gc=0;
int pc=0;
int score=0;
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++){
		if(i%2==0){
			if(s[i]=='p'){
				score--;
			}
		}else{
			if(s[i]=='g'){
				score++;
			}
		}
	}
	cout<<max(0,score)<<endl;
}

Measured memory_bytes: 512