akhauriyash/Code-Regression huggingface dataset:
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
// -fsanitize=undefinedでオーバーフロー検出
#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};


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

    ll a,b,c,d,m,n,maxi=0,f=0,g=0,mini=INF,sum=0;
    ll k;
    string str,stra;
    
    cin>>a>>b;
    if(a+b==15) cout<<"+"<<endl;
    else if(a*b==15) cout<<"*"<<endl;
    else cout<<"x"<<endl;

    return 0;
}


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

using namespace std;

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    if (a + b + 1 >= c) {
        cout << b + c << endl;
    } else {
        cout << a + 2 * b + 1 << endl;
    }
    return 0;
}


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



from math import cos,sin,pi

x,y=[0,0]
rad = 0
for i in range(10000):
    x += cos(pi*rad*n/180)
    y += sin(pi*rad*n/180)
    rad+=1
    if abs(x) < 0.00001 and abs(y) < 0.00001:
        print(i+1)
        exit()

Measured memory_bytes: 9560
using System;
using System.Collections.Generic;
using System.Windows;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    public class Program
    {
        static void Main(string[] args)
        {
            var n = Read().Int();
            var now = 1;
            var l = new Dictionary<int, int>();
            while (100000 >= now)
            {
                if (!l.ContainsKey(now))
                {
                    l.Add(now, 1);
                }
                now *= 6;
            }
            now = 1;
            while (100000 >= now)
            {
                if (!l.ContainsKey(now))
                {
                    l.Add(now, 1);
                }
                now *= 9;
            }

            var dp = new int[100010];
            var INF = 1000000007;
            for (int i = 0; i < 100010; i++)
            {
                dp[i] = INF;
            }
            dp[0] = 0;
            for (int i = 1; i < 100010; i++)
            {
                foreach (var item in l)
                {
                    if (i - item.Key >= 0)
                    {
                        ChangeMin(ref dp[i], dp[i - item.Key] + 1);
                    }
                }
            }
            WriteRead(dp[n]);
        }

        public static string Read()
        {
            return Console.ReadLine();
        }

        public static string[] ReadSplit()
        {
            return Console.ReadLine().Split(' ');
        }

        public static void WriteRead(object str)
        {
            Console.WriteLine(str);
            Read();
        }

        public static void Write(object str)
        {
            Console.WriteLine(str);
        }

        private static bool ChangeMin<T>(ref T a, T b) where T : IComparable
        {
            if (a.CompareTo(b) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }

        private static bool ChangekMax<T>(ref T a, T b) where T : IComparable
        {
            if (b.CompareTo(a) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }
    }
}


public static class Extentions
{
    public static int Int(this object obj)
    {
        return int.Parse(obj.ToString());
    }

    public static long Long(this object obj)
    {
        return long.Parse(obj.ToString());
    }

    public static decimal Decimal(this object obj)
    {
        return decimal.Parse(obj.ToString());
    }

    public static double Double(this object obj)
    {
        return double.Parse(obj.ToString());
    }

    public static T2 GetValueZero<T1, T2>(this Dictionary<T1, T2> d, T1 key) where T2 : struct
    {
        T2 value;
        if (d.TryGetValue(key, out value))
        {
            return value;
        }
        return new T2();
    }
}



Measured memory_bytes: 17632
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

#define rep(i,x) for(int i = 0; i < x; i++)
#define rrep(i,x) for(int i = 1; i <= x; i++)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using ll = long long;
using namespace std;
const int INF = 1001001001;
const ll LINF = 1002003004005006007;

int main(){
    int n; cin >> n;
    vector<vector<int>> table(9, vector<int>(9, 0));
    rrep(i, n){
        string str = to_string(i);
        int s = str[0] - '0';
        int e = str[str.size() - 1] - '0';
        if (s != 0 and e != 0){
            table[s - 1][e - 1] += 1;
        }
    }
    int ans = 0;
    rep(i, 9)rep(j, 9){
        ans += (table[i][j] * table[j][i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
a,b,c,d=map(int,input().split())
x=abs(c-a)
y=abs(d-b)
if a<c and b<=d:
    f=d+x
    e=c-y
    g=e-x
    h=f-y
elif a>=c and b<d:
    f=d-x
    e=c-y
    g=e+x
    h=f-y
elif a>c and b>=d:
    f=d-x
    e=c+y
    g=e+x
    h=f+y
else:
    f=d+x
    e=c+y
    g=e-x
    h=f+y
print(e,f,g,h)


Measured memory_bytes: 9028
"""
計数ソートを実装する
計算量はO(n+k)
"""
def countingSort(A, B, k):
    global n
    C = [0]*(k+1) #kは最大値

    for i in range(n):
        C[A[i]] += 1 #要素数を記録する
    
    for i in range(1, k+1):
        C[i] = C[i-1] + C[i]
    
    for i in range(n-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]
    
    
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
k = max(a)

countingSort(a, b, k)
b = map(str, b)
print(' '.join(b))



Measured memory_bytes: 231848
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

using ll = long long;

ll N;
ll A[100010];
std::vector<ll> cs[2];

// /\/\ (b-a)+(b-c)+(d-c)+(d-e) = -a+2b-2c+2d-e
// \/\/ (a-b)+(c-b)+(c-d)+(e-d) = a-2b+2c-2d+e

int main()
{
  scanf( "%lld", &N );
  rep( i, N )
    scanf( "%lld", A+i );

  std::sort( A, A+N );

  rep( i, N )
  {
    ll ret = 1;

    if( i >= 1 && i < N-1 )
      ret *= 2;

    cs[0].push_back( (i&1?1:-1)*ret );
  }

  rep( i, N )
  {
    ll ret = 1;

    if( i >= 1 && i < N-1 )
      ret *= 2;

    cs[1].push_back( (i&1?-1:1)*ret );
  }

  rep( i, 2 )
    std::sort( all( cs[i] ) );

  ll ans = 0;
  rep( i, 2 )
  {
    ll ret = 0;

    rep( k, N )
      ret += A[k]*cs[i][k];

    ans = std::max( ans, ret );
  }

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

  return 0;
}

Measured memory_bytes: 3316
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

class Knapsack {
    typedef long long LL;
    struct item { 
        LL v, w; 
    };

    LL W;
    vector<item> items;
    LL lv;

    LL solve_rec(size_t k, LL v, LL w) {
        if (w + items[k].w > W) return solve_rec(k+1, v, w);
        LL cv = v, cw = w;
        for (size_t i = k; i < items.size(); ++i) {
            if (cw + items[i].w <= W) {
                cw += items[i].w;
                cv += items[i].v;
            }
        }
        if (lv < cv) lv = cv;
        double fv = v, fw = w;
        for (size_t i = k; i < items.size(); ++i) {
            if (fw + items[i].w <= W) {
                fw += items[i].w;
                fv += items[i].v;
            } else {
                fv += items[i].v * (W - fw) / items[i].w;
                break;
            }
        }
        if (fv - lv < 1 || fv < lv) return lv;
        solve_rec(k+1, v+items[k].v, w+items[k].w);
        return solve_rec(k+1, v, w);
    }

    public:
    // 価値v, 重みwのアイテムを追加
    void add_item(LL v, LL w) {
        items.push_back({v, w});
    }

    // 重みの合計がW以下になるようにアイテムを選んだときの価値の和の最大値を返す．
    LL solve(LL W_) {
        if(items.empty()) return 0;
        W = W_;
        sort(items.begin(), items.end(), [](const item &a, const item &b) { 
                return a.v * b.w > a.w * b.v;
                });
        lv = 0;
        return solve_rec(0, 0, 0);
    };
};
int main(){
    iostream_init();

    Knapsack s;
    int N, W;
    cin >> N >> W;
    REP(i, N) {
        int w, v;
        cin >> w >> v;
        s.add_item(v, w);
    }
    cout << s.solve(W) << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int k = 0; k < n; k++) {
		cout << a[k];
		if (k != n - 1) {
			cout << " ";
		}
		else {
			cout << endl;
		}
	}
	for (int i = 1; i < n; i++) {
		int v = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
		for (int k = 0; k < n; k++) {
			cout << a[k];
			if (k != n - 1) {
				cout << " ";
			}
			else {
				cout << endl;
			}
		}
	}

}




Measured memory_bytes: 3092
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main(void){
    int sx,sy,gx,gy;
    cin>>sx>>sy>>gx>>gy;
    gx-=sx;
    gy-=sy;
    if(gx>=0&&gy>=0){
        for(int i=0;i<gx;i++){
            cout<<"R";
        }
        for(int i=0;i<gy;i++){
            cout<<"U";
        }
        for(int i=0;i<gx;i++){
            cout<<"L";
        }
        for(int i=0;i<gy;i++){
            cout<<"D";
        }
        cout<<"D";
        for(int i=0;i<=gx;i++){
            cout<<"R";
        }
        for(int i=0;i<=gy;i++){
            cout<<"U";
        }
        cout<<"LU";
        for(int i=0;i<=gx;i++){
            cout<<"L";
        }
        for(int i=0;i<=gy;i++){
            cout<<"D";
        }
        cout<<"R";
    }
    else if(gx<=0&&gy>=0){
        gx*=-1;
        for(int i=0;i<gx;i++){
            cout<<"L";
        }
        for(int i=0;i<gy;i++){
            cout<<"U";
        }
        for(int i=0;i<gx;i++){
            cout<<"R";
        }
        for(int i=0;i<gy;i++){
            cout<<"D";
        }
        cout<<"D";
        for(int i=0;i<=gx;i++){
            cout<<"L";
        }
        for(int i=0;i<=gy;i++){
            cout<<"U";
        }
        cout<<"RU";
        for(int i=0;i<=gx;i++){
            cout<<"R";
        }
        for(int i=0;i<=gy;i++){
            cout<<"D";
        }
        cout<<"L";
    }
    else if(gx<=0&&gy<=0){
        gx*=-1;
        gy*=-1;
        for(int i=0;i<gx;i++){
            cout<<"L";
        }
        for(int i=0;i<gy;i++){
            cout<<"D";
        }
        for(int i=0;i<gx;i++){
            cout<<"R";
        }
        for(int i=0;i<gy;i++){
            cout<<"U";
        }
        cout<<"U";
        for(int i=0;i<=gx;i++){
            cout<<"L";
        }
        for(int i=0;i<=gy;i++){
            cout<<"D";
        }
        cout<<"RD";
        for(int i=0;i<=gx;i++){
            cout<<"R";
        }
        for(int i=0;i<=gy;i++){
            cout<<"U";
        }
        cout<<"L";
    }
    else if(gx>=0&&gy<=0){
        for(int i=0;i<gx;i++){
            cout<<"R";
        }
        for(int i=0;i<gy;i++){
            cout<<"D";
        }
        for(int i=0;i<gx;i++){
            cout<<"L";
        }
        for(int i=0;i<gy;i++){
            cout<<"U";
        }
        cout<<"U";
        for(int i=0;i<=gx;i++){
            cout<<"R";
        }
        for(int i=0;i<=gy;i++){
            cout<<"D";
        }
        cout<<"DL";
        for(int i=0;i<=gx;i++){
            cout<<"L";
        }
        for(int i=0;i<=gy;i++){
            cout<<"U";
        }
        cout<<"R";
    }    
    return 0;
}


Measured memory_bytes: 256
#include"iostream"
#include"cmath"
#include"vector"
#include"algorithm"
#include"list"
#include"set"
#include"unordered_set"
#include"map"
#include"unordered_map"
#include"string"
#include"cstring"
#include"iomanip"
#include"assert.h"
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
const ll mo=1e9+7;
ll posn[maxn];

ll gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    else
    {
        ll g=gcd(b,a%b,x,y);
        ll x1=x,y1=y;
        x=y1;
        y=x1-(a/b)*y1;
        return g;
    }
}
ll inv(ll a,ll b)
{
    ll x,y;
    ll g=gcd(a,b,x,y);
    assert(g==1);
    return (x%b+b)%b;
}
ll ans[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;cin>>n;
    memset(posn,-1,sizeof posn);
    ll p1,p2,x,y;
    for(ll i=0;i<=n;++i)
    {
        ll x;cin>>x;
        if(posn[x]==-1)
            posn[x]=i;
        else
        {
            p1=posn[x];
            p2=i;
        }
    }
    x=p1;
    y=n-p2;
    ll n1=x+y;
    ll ans1=n+1,ans2=1;
    memset(ans,-1,sizeof ans);
    for(int k=1;k<=n+1;++k)
    {
        if(k==n+1)
        {
            cout<<"1\n";
            return 0;
        }
        if(k==1)
        {
            ans1=n+1;ans2=1;
        }
        else
        {
            ans1=((ans1*(n+1-k+1))%mo*inv(k,mo))%mo;
            ans[k]=ans1;
            ans2=((ans2*(n1-(k-1)+1))%mo*inv(k-1,mo))%mo;
        }
        /*
        if(ans[n+1-k]>-1)
        {
            ans1=ans[n+1-k];
        }
        */
        if(k-1>n1)ans2=0;
        cout<<(ans1-ans2+mo)%mo<<'\n';
    }
}





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

int main() {
	int c=2, f=1;
  	int x;
  	for (int i=0; i<3; i++) {
    	cin >> x;
      	if (x == 5) c--;
        if (x == 7) f--;
    }
  	if (f==0 && c==0) cout << "YES\n";
  	else cout << "NO\n";
	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  long long sum = 0;
  vector<int> A(M);
  for(int i = 0; i < M; i++) {
    cin >> A.at(i);
  }
  for(int i = 0; i < M; i++) {
    sum += A.at(i);
  }
  if(sum > N) {
    cout << "-1";
  }
  else {
    cout << N - sum;
  }
}



Measured memory_bytes: 3668
n,k = map(int,input().split())
a = list(map(int,input().split()))

ans = 0
ans2 = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i < j:    
                ans += 1
            elif i > j:
                ans2 += 1
count1 = k*(k+1)//2
count2 = (k-1)*k//2

ans = ans * count1 + ans2 * count2

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

Measured memory_bytes: 41964
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
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 (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

template<typename flow_t>
struct Dinic{
    const flow_t INF_flow_t = INF;   // WRITE HERE

    struct edge{
        int to;
        flow_t cap;
        int rev;
    };
    using WeightedGraph = vector<vector<edge>>;
    int V;
    WeightedGraph G;
    vector<int> itr, level;

    Dinic(int n){
        V = n;
        G.assign(V, vector<edge>());
    }

    void add_edge(int from, int to, int cap) {
        G[from].push_back((edge){to, cap, (int)G[to].size()});
        G[to].push_back((edge){from, 0, (int)G[from].size()-1});
    }

    void bfs(int s) {
        level.assign(V, -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for(auto &&e: G[v]){
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    flow_t dfs(int v, int t, flow_t f) {
        if(v == t) return f;
        for(int &i = itr[v]; i < (int)G[v].size(); i++) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                flow_t d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    flow_t max_flow(int s, int t) {
        flow_t res = 0, f;
        while(bfs(s), level[t] >= 0) {
            itr.assign(V, 0);
            while((f = dfs(s, t, INF_flow_t)) > 0) res += f;
        }
        return res;
    }
};

int main(){
    int v, e;
    cin >> v >> e;
    Dinic<int> G(v);
    rep(i, e){
        int u, v, c;
        cin >> u >> v >> c;
        G.add_edge(u, v, c);
    }
    cout << G.max_flow(0, v-1) << endl;
}



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

int main() {
  int n, m; cin >> n >> m;
  vector<int> p(n+1,0);
  vector<bool> ac(n+1);
  int ac_cnt = 0, pe_cnt = 0;
  rep(i,m) {
    int pi; string si; cin >> pi >> si;
    if (!ac[pi]) {
      if (si == "WA") {
        p[pi]++;
      } else {
        ac_cnt++;
        pe_cnt += p[pi];
        ac[pi] = true;
      }
    }
  }
  cout << ac_cnt << " " << pe_cnt << endl;
  return 0;
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<" "<<b<<" "<<c;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}

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

using namespace std;

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;

    while(s.find('/') != std::string::npos){
        s.erase(s.begin()+s.find('/'));
    }
    if (s<="20190430") {
        cout << "Heisei" << endl;
    }
    else {
        cout << "TBD" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}

int main() {
	run();
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a;
		cin >> a;
		n -= a;
	}
	cout << max(n, -1) << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }

class Segment_tree
{
    using data_type = int;

public:

    vector<data_type> dat;
    int N;
    data_type id;

    data_type func(data_type u, data_type v){
        return max(u, v);
    }

    Segment_tree(int n, data_type id): id(id) {
        N = 1;
        while(n > N) N = N << 1;
        dat = vector<data_type>(2 * N - 1, id);
    }

    Segment_tree(int n, data_type id, vector<data_type> v): id(id) {
        N = 1;
        while(n > N) N = N << 1;
        dat = vector<data_type>(2 * N - 1, id);
        REP(i, n) dat[i + N - 1] = v[i];
        IREP(i, N - 1) dat[i] = func(dat[i * 2 + 1], dat[i * 2 + 2]); 
    }

    //k番目の値をaに更新
    void update(int k, data_type a){
        k += N - 1;
        dat[k] = a;
        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    data_type query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return id;
        if(a <= l && r <= b) return dat[k];
        else{
            data_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            data_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }

    //[a, b)の演算結果
    data_type query(int a, int b){
        return query(a, b, 0, 0, N);
    }

    data_type getdat(int k){
        return dat[k + N - 1];
    }
};

signed main(){

    int N; cin >> N;
    vec b(N); readv(b);
    int Q; cin >> Q;
    vector<Pii> lr(Q);
    REP(i, Q){
        cin >> lr[i].first >> lr[i].second;
        //lr[i].first--; lr[i].second--;
    }
    SORT(lr);

    vec s0(N + 1), s1(N + 1);
    s0[0] = 0; s1[0] = 0;
    REP(i, N){
        s0[i + 1] = s0[i];
        s1[i + 1] = s1[i];
        if(b[i] == 0) s0[i + 1]++;
        else s1[i + 1]++;
    }

    Segment_tree T0(N + 1, -1), T1(N + 1, -1);
    T0.update(0, s0[N]);
    T1.update(0, s1[N]);

    REP(i, Q){
        int l = lr[i].first, r = lr[i].second;
        int v1 = T0.query(0, l) - (s0[N] - s0[l - 1]) + (s1[r] - s1[l - 1]);
        int v2 = T1.query(l, r + 1) - (s1[N] - s1[r]);
        int v = max(v1, v2);
        T0.update(r, v + s0[N] - s0[r]);
        T1.update(r, v + s1[N] - s1[r]);
    }

    int ans = 0;
    REP(i, N + 1) ans = max(ans, T0.getdat(i));
    cout << N - ans << endl;
    
    return 0;
}

Measured memory_bytes: 16256
using System;
using static System.Console;

namespace abc176
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadLine();
            var total = 0;
            for (var i = 0; i < n.Length; ++i)
            {
                total += n[i] - '0';
            }
            WriteLine((total % 9 == 0) ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 26664
N, M = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    UF.union(x, y)
UF.all_find()


print(len(set(UF.par)))


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

int main() {
	int i, n = 1, w = 1, e = 1, s = 1;
	string str;
	cin >> str;
	for (i = 0; i<str.length(); i++) {
		if (str[i] == 'N') {
			n = 0;
		}
		else if (str[i] == 'W') {
			w = 0;
		}
		else if (str[i] == 'S') {
			s = 0;
		}
		else {
			e = 0;
		}
	}
	if (n^s || w ^ e) {
		cout << "No";
	}
	else {
		cout << "Yes";
	}
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> vote(N);
  for (int i=0; i < vote.size(); i++){
    cin >> vote.at(i);
  }
  double sum = 0.0;
  for (int i=0; i < vote.size(); i++){
    sum += vote.at(i);
  }
  sort(vote.begin(), vote.end());
  reverse(vote.begin(), vote.end());
  if (vote.at(M-1) >= sum/(4*M)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

void scoring()
{
	int D;
	vector<int> cs(26);
	cin >> D;
	for (auto &&c : cs)
	{
		cin >> c;
	}
	vector<vector<int>> sss(D, vector<int>(26));
	vector<int> ts(D);
	for (auto &&ss : sss)
	{
		for (auto &&s : ss)
		{
			cin >> s;
		}
	}
	for (auto &&t : ts)
	{
		cin >> t;
		t--;
	}

	vector<int> last(26, -1);

	int score = 0;

	for (int d = 0; d < D; d++)
	{
		score += sss[d][ts[d]];

		last[ts[d]] = d;

		for (int i = 0; i < 26; i++)
		{
			score -= cs[i] * (d - last[i]);
		}

		cout << score << endl;
	}
}

void incremental_scoring()
{
	int D;
	vector<int> cs(26);
	cin >> D;
	for (auto &&c : cs)
	{
		cin >> c;
	}
	vector<vector<int>> sss(D, vector<int>(26));
	vector<int> ts(D);
	for (auto &&ss : sss)
	{
		for (auto &&s : ss)
		{
			cin >> s;
		}
	}
	for (auto &&t : ts)
	{
		cin >> t;
		t--;
	}
	int M;
	cin >> M;
	vector<int> ds(M), qs(M);
	for (int i = 0; i < M; i++)
	{
		cin >> ds[i] >> qs[i];
		ds[i]--;
		qs[i]--;
	}

	auto calc_score = [&] {
		vector<int> last(26, -1);

		int score = 0;

		for (int d = 0; d < D; d++)
		{
			score += sss[d][ts[d]];

			last[ts[d]] = d;

			for (int i = 0; i < 26; i++)
			{
				score -= cs[i] * (d - last[i]);
			}

			// cout << score << endl;
		}

		return score;
	};

	for (int i = 0; i < M; i++)
	{
		ts[ds[i]] = qs[i];

		cout << calc_score() << endl;
	}
}

int main()
{
	incremental_scoring();

	return 0;
}

Measured memory_bytes: 3972
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define REP(i, a) for (int i(0), _##i(a); i < _##i; ++i)
#define FOR(i, a, b) for (int i(a), _##i(b); i <= _##i; ++i)

#ifdef LOCAL
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define _FE_6(_CALL, x, ...) _CALL(x) _FE_5(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(__VA_ARGS__, _FE_6, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1)              \
  (MACRO, __VA_ARGS__)
#define watch(x) cerr << "\033[1;32m" #x " = \033[1;34m" << (x) << "\033[0m; ";
#define debug(...)                                                             \
  cerr << "\033[2;31mLine " << __LINE__ << ": \033[0m";                        \
  FOR_EACH_MACRO(watch, __VA_ARGS__)                                           \
  cerr << endl
#else
#define debug(...)
#endif

using namespace std;

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

template <class T, class = decltype(begin(declval<T>())),
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = begin(c); it != end(c); ++it)
    os << (it == begin(c) ? "" : ", ") << *it;
  return os << ']';
}
using ll = long long;

using M = vector<vector<int>>;

const int MOD = 1e9 + 7;

M operator*(const M &a, const M &b) {
  assert(a[0].size() == b.size());
  int n = a.size();
  int m = b[0].size();
  vector<vector<int>> c(n, vector<int>(m));
  REP(i, n) REP(j, m) REP(k, m) { 
    c[i][j] = ((ll)c[i][j] + 1ll * a[i][k] * b[k][j]) % MOD; 
  }
  return c;
}

M base(int n){
  M res(n, vector<int>(n));
  REP(i, n) res[i][i] = 1;
  return res;
}

M operator^(M a, ll p) {
  M res = base(a.size());
  while (p > 0){
    if (p & 1) res = res * a;
    p >>= 1;
    a = a * a;
  }
  return res;
}

void solve() {
  ll n, k;
  cin >> n >> k;
  vector<vector<int>> a(n, vector<int>(n));
  REP(i, n) REP(j, n) cin >> a[i][j];
  auto c = a ^ k;
  ll ans = 0;
  REP(i, n) REP(j, n) {
    ans = (ans + c[i][j]) % MOD;
  }
  cout << ans << "\n";
}

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

  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }
}


Measured memory_bytes: 256
n = int(input())
A = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1
        # A[int(j)-1][int(u)-1] = 1

for row in A:
    msg = ' '.join(map(str, row))
    # print(msg)

d = [-1] * n
f = [-1] * n

t = 0

# # recursive
# def dfs(u):
#     global t
#     # print('visit:', str(u), str(t))
#     t += 1
#     d[u] = t
#     for i in range(len(A[u])):
#         if A[u][i] == 1 and d[i] == -1:
#             dfs(i)
#     t += 1
#     f[u] = t
            

def get_next(u):
    for i in range(len(A[u])):
        if A[u][i] == 1 and d[i] == -1:
            return i
    return None

def dfs(u):
    global t
    s = []
    s.append(u)
    d[u] = t
    while len(s) > 0:
        p = s[-1]
        v = get_next(p)
        # print(p, 'next:', v)
        # t += 1
        # d[p] = t
        # print('poped:', p)
        
        if v is not None:
            
            if d[v] == -1:
                t += 1
                d[v] = t
                s.append(v)
                # print('[append:', v, 'at', t)
        else:
            t += 1
            # print('complete:', p, 'at', t)
            s.pop()
            f[p] = t


# def dfs(u):
#     s = []
#     t = 0
#     s.append(u)
    
#     while len(s) > 0:
#         p = s.pop()
#         print('init', str(p), d[p], t)
#         if d[p] > -1:
#             print('完了')
#             t += 1
#             f[p] = t
#         else:
#             t += 1
#             d[p] = t
#             print('---visit:', str(p), str(t), 'at', t)
#             has_node = False
#             for i in range(len(A[p])):
#                 if A[p][i] == 1 and d[i] == -1:
#                     print('reserve:', str(i))
#                     has_node = True
#                     s.append(i)
#                     break
#             if not has_node:
#                 t += 1
#                 f[p] = t
#         # print('H_complete:', str(p), str(t))
            


t = 0
for i in range(n):
    if d[i] == -1:
        t += 1
        # print('start from:', str(i))
        dfs(i)


for i in range(n):
    print(str(i+1), str(d[i]), str(f[i]))


Measured memory_bytes: 5748
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 200010
string s[N],x;
int t[N],n;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    rep(i,n)cin>>s[i]>>t[i];
    cin>>x;
    rep(i,n)if(s[i]==x){
	ll ans=0;
	for(int j=i+1;j<n;j++)ans+=t[j];
	cout<<ans<<endl;
    }
}


Measured memory_bytes: 1792
def main():
    A, B, C = map(int, input().split())

    if B <= C:
        count = 0

        count += B * 2
        C -= B

        if C >= 1:
            count += 1
            C -= 1

        if A < C:
            count += A
        else:
            count += C

        print(count)
    else:
        print(B+C)


main()


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

int main() {
  // input
  long n, m;
  long long ans;
  cin >> n >> m;
  if (n > m) {
    cout << 0 << endl;
    return 0;
  }
  vector<long> x(m);
  vector<long> y(m - 1);
  for (int i = 0; i < m; i++) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  for (int i = 0; i < m - 1; i++) {
    y[i] = x[i + 1] - x[i];
  }
  sort(y.begin(), y.end(), greater<int>());
  ans = x[m - 1] - x[0];
  for (int i = 0; i < n - 1; i++) {
    ans -= y[i];
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
	int i, j ,k;
	int count[4][3][10] = {0};
	int n;
	int b, f, r, v;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> b >> f >> r >> v;
		count[b - 1][f - 1][r - 1] += v;
	}

	for (i = 0; i < 4; i++) {
		if (i) {
			cout << "####################" << endl;
		}
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 10; k++) {
				cout << " " << count[i][j][k];
			}
			cout << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  string s, t;
  cin >> s >> t;
  cout << t + s << endl;
  return 0;
}

Measured memory_bytes: 3616
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

N,M = map(int,input().split())
p = list(map(int,input().split()))
xy = [list(map(int,input().split())) for i in range(M)]
un = UnionFind(N)
ans = 0
for i in range(M):
    un.union(xy[i][0]-1,xy[i][1]-1)
for i in range(N):
    if un.same_group_or_no(i,p[i]-1):
        ans += 1

print(ans)

Measured memory_bytes: 36172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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; }
const ll INF=1LL<<60;
const int mod=1e9+7;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w,K;cin >> h >> w >> K;
    char s[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> s[i][j];
        }
    }
    int ans=h+w-2;
    for(int i=0;i<(1<<(h-1));i++){
        int cnt=0;
        vector<int> b(h);
        b[0]=cnt;
        for(int j=0;j<h-1;j++){
            if(i&(1<<j)){
                cnt++;
            }
            b[j+1]=cnt;
        }
        bool q=true;
        int res=cnt;
        vector<int> v(cnt+1),u(cnt+1);
        for(int j=0;j<w;j++){
            int t=0;
            for(int k=0;k<h;k++){
                if(s[k][j]=='1'){
                    u[b[k]]++;
                }
            }
            bool f=true;
            for(int k=0;k<cnt+1;k++){
                if(v[k]+u[k]>K){
                    f=false;
                }
                if(u[k]>K){
                    q=false;
                    break;
                }
            }
            if(!q){
                break;
            }
            if(f){
                for(int k=0;k<cnt+1;k++){
                    v[k]+=u[k];
                    u[k]=0;
                }
            }
            else{
                res++;
                for(int k=0;k<cnt+1;k++){
                    v[k]=u[k];
                    u[k]=0;
                }
            }
        }
        if(!q){
            continue;
        }
        chmin(ans,res);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a,b,i,n;
scanf("%d%d",&a,&b);
while(a!=0&&b!=0)
	{	
	
		
		
		for(n=0;n<a;n++)
		{
		for(i=0;i<b;i++)
		{
			printf("#");
		}
		puts("");
		}
		puts("");scanf("%d%d",&a,&b);
	}
return 0;

}

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

int main()
{
  long a, b, c, d;
  cin >> a >> b >> c >> d;
  long  x, y, xy;


  x = max(a*c , b*d);
  y = max(a*d , b*c);
  xy = max(x,y);

  cout << xy<<endl;
}


Measured memory_bytes: 3636
import java.util.*;
import java.io.*;
 
public class Main {
	public static void main(String args[] ) throws Exception {

		Scanner sc = new Scanner(System.in);
		String[] s00 = sc.nextLine().trim().split(" ") ; 
		int H = Integer.valueOf ( s00[0] ) ;
		int W = Integer.valueOf ( s00[1] ) ;
		int M = Integer.valueOf ( s00[2] ) ;
	

//		Set<List<Integer>> set = new HashSet<>() ;
		Set <Long> set1 = new HashSet<>() ;

		int[] arrx = new int[H+1] ;
		int[] arry = new int[W+1] ;
		for  ( int j=0 ; j<M ; j++ ) {
			s00 = sc.nextLine().trim().split(" ") ; 
			int x = Integer.valueOf ( s00[0] ) ;
			int y = Integer.valueOf ( s00[1] ) ;
			set1.add ( (long) y * ( H +1 ) + x ) ;
			arrx[x] += 1; 
			arry[y] += 1 ;
		}

		List<Integer> lx = new ArrayList<>() ;
		List<Integer> ly = new ArrayList<>() ;

		int maxx = -1 ;
		int maxy = -1 ;
		for ( int j=0 ; j<arrx.length ; j++ ) {
			if ( arrx[j] == maxx ) {
				lx.add ( j ) ;
			} else if ( arrx[j] > maxx ) {
				lx.clear() ; 
				lx.add ( j ) ;
				maxx = arrx[j] ;
			}
		}

		for ( int j=0 ; j<arry.length ; j++ ) {
			if ( arry[j] == maxy ) {
				ly.add ( j ) ;
			} else if ( arry[j] > maxy ) {
				ly.clear() ; 
				ly.add ( j ) ;
				maxy = arry[j] ;
			}
		}


		int t = 0 ;
		for ( int x : lx ) {
			for ( int y : ly ) {

				long v1 = (long) y * ( H + 1 ) + x ;
//				List<Integer> l0 = Arrays.asList ( x, y ) ; 
				int d =  set1.contains( v1 ) ? -1 : 0 ;
				t = Math.max ( t , maxx + maxy + d ) ;
				if ( t == maxx + maxy )
					break ;
			}
		}
		System.out.println( t ) ;
	}
}

Measured memory_bytes: 88072
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var score = new bool[10001];
        score[0] = true;
        for (int i = 0; i < n; i++)
        {
            var s = int.Parse(Console.ReadLine());
            for (int j = score.Length - 1; j >= s; j--)
            {
                if (score[j - s]) score[j] = true;
            }
        }
        for (int i = score.Length - 1; i >= 0; i--)
        {
            if (i % 10 != 0 && score[i])
            {
                Console.WriteLine(i);
                return;
            }
        }
        Console.WriteLine(0);
    }
}

Measured memory_bytes: 13120
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>

typedef long long ll;

using namespace std;

int main()
{
    int L;
    scanf("%d", &L);
    printf("%.12f\n", (double)L*L*L/27);
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i,n){
        cin >> a[i];
    }
    //j-i=a[i]+a[j];
    //j-a[j]=a[i]+i
    map<int,int>mp;
    ll ans = 0;
    rep(i,n){
        ans += mp[i-a[i]];
        mp[i+a[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 21144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int n;
	cin >> n;
	int x=1;
	int ans=0;
	for(int i=1;i<=n;i++){
		int t;
		cin >> t;
		if(t==x){
			x++;
		}
		else{
			ans++;
		}
	}
	if(ans<=n-1){
		cout << ans << endl;
	}
	else{
		cout << -1 << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
  int h,w,i,j;
  string s;
  cin >> h >> w;
  for(i=0;i<w+2;i++) cout << "#";
  cout<<endl;
  for(i=0;i<h;i++) {
    cin >> s;
    cout<<"#"<<s<<"#"<<endl;
  }
  for(i=0;i<w+2;i++) cout << "#";
}

Measured memory_bytes: 256
let lines = [];
let reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

// 標準入力の読み込み
reader.on('line', function(line) {
    lines.push(line);
});

reader.on('close', function() {
    // 処理の記述
    const str = lines[0];
    let result = 0;
    if (str === 'RRR') {
        result = 3;
    } else if (str === 'SSS') {
        result = 0;
    } else if (str === 'RRS' || str === 'SRR') {
        result = 2;
    } else {
        result = 1;
    }

    // 表示
    console.log(result);
});

Measured memory_bytes: 30180
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define lld long long
const int N = 20;
int n,m;
lld tot=1;
lld f[N][N*N],A[N];
int use[N],nn[N];
char s[N];
lld ans;
lld pow(int a,int b)
{
    lld te = 1;
    for(int i = 1; i <= b; i++) te *= a;
    return te;
}
void solve()
{
    for(int i = 0; i < 10; i++) nn[i] = use[i];
    for(int i = 1; i <= n; i++)
    {
        lld te = 0;
        for(int j = 0; j < s[i]-'0'; j++)
            te += nn[j];
        te *= A[n-i];
        for(int j = 0; j <= 9; j++) te /= A[nn[j]];
        ans += te;
        if(!nn[s[i]-'0']) break;
        nn[s[i]-'0']--;
    }
}
void dfs(int a,int b,lld c,int e)
{
    if(c>tot || e>m) return;
    if(c*pow(a+1,n-b)>tot||e+a*(n-b)>m) return;
    if(e+9*(n-b)<m) return;
    if(b==n) {
        if(e==m) {

           // lld te = 1;
           // for(int i )
           //printf("%d\n",A[n]);

            if(c<tot) {
                lld ta = A[n];
                for(int i = 0; i <= 9; i++) ta /= A[use[i]];
                ans += ta;

            }
            else if(c==tot) solve();
        }
        return;
    }
    if(a==10) return;
    for(int i = 0; i <= n-b; i++)
    {
        use[a] = i;
        dfs(a+1,b+i,c*pow(a+1,i),e+a*i);
        use[a] = 0;
    }
}
int main()
{

    scanf("%s",s+1);
    n = strlen(s+1);
    A[0] = 1;
    for(int i = 1; i <= n; i++) {

        A[i] = A[i-1] * i;
        m += s[i] - '0';
        tot *= s[i] - '0' + 1;
    }

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++)
    for(int k = 0; k <= min(j,9); k++)
        f[i][j] += f[i-1][j-k];
    for(int i = 0; i < m; i++) ans += f[n][i];
    dfs(0,0,1,0);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1204
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    String S = sc.next();

    sc.close();
    
    long result = dfs(S,0);

    System.out.println(result);

  }

  public static long dfs (String S, int depth) {

    if (depth == S.length() - 1) {

      // + 区切って配列に入れる
      String[] s = S.split("\\+");
      
      long sum = 0;

      for (int i = 0; i < s.length; i++) {
        sum += Long.parseLong(s[i]);
      }

      return sum;
    
    }

    long sum = 0;
    
    // +を入れない
    sum += dfs(S, depth + 1);

    // +を入れる
    S = S.substring(0, depth + 1) + "+" + S.substring(depth + 1);

    sum += dfs(S, depth + 2);

    return sum;

  }

}

Measured memory_bytes: 22356
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
N=int(input())
for i in range(N):
    a=q.get()
    b=a%10
    if b!=0:
        q.put(10*a+b-1)
    q.put(10*a+b)
    if b!=9:
        q.put(10*a+b+1)
print(a)

Measured memory_bytes: 12480
N = gets.to_i
dp = Array.new(N+1, N)
dp[0] = 0
(0...N).each do |n|
    dp[n+1] = [dp[n] + 1, dp[n+1]].min
    s = 1
    while n+s*6<=N
        s *= 6
        dp[n+s] = [dp[n] + 1, dp[n+s]].min
    end
    s = 1
    while n+s*9<=N
        s *= 9
        dp[n+s] = [dp[n] + 1, dp[n+s]].min
    end
end
p dp[N]


Measured memory_bytes: 2556
n = int(input())
b = list()
for _ in range(n):
    
    s = input()
    a = list()
    for i in range(len(s)):
        a.append(s[i])
    a.sort()
    s = ""
    s = s.join(a)
    
    b.append(s)
    
b.sort()
b.append("zzzzzzzzzzzzzzz")

ans = 0
cn  = 1
for i in range(0,len(b)-1):
    if(b[i]==b[i+1]):
        cn += 1
    else:
        ans += (cn*(cn-1))//2
        cn  = 1

print(ans)

Measured memory_bytes: 59608
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll n;;
	cin>>n;
	vector<ll> arr(n,0);
	for(ll i=0;i<n;i++) cin>>arr[i];
	
	vector<ll> dp(n,0);
	for(ll i=1;i<n;i++){
		if(i==1){
			dp[i]=dp[i-1]+abs(arr[i]-arr[i-1]);
		}
		else{
			dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]));
		}
	}
	cout<<dp[n-1]<<endl;
	
	
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int n;
    string s;
    cin >> n >> s;

    int s_len = s.length();
    string ans = "";
    rep(i, s_len)
    {
        ans += ((s[i] - 'A') + n) % 26 + 'A';
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int cnt1[210000] = {}, cnt2[210000] = {};

int main(){
    int N;
    cin >> N;
    string str;
    cin >> str;
    int cnt = 0;
    for(int i = 0; i < N; i++){
        if(str[i] == '#'){
            cnt += 1;
        }
        cnt1[i] = cnt;
    }
    cnt = 0;
    for(int i = N - 1; i >= 0; i--){
        if(str[i] == '.'){
            cnt += 1;
        }
        cnt2[i] = cnt;
    }
    long long int ans = min(cnt1[N - 1], cnt2[0]);
    for(int i = 0; i < N - 1; i++){
        ans = min(ans, cnt1[i] + cnt2[i + 1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3716