akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<set>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
typedef long long ll;

int main(){
    string s;
    cin>>s;
    cout<<s.substr(0,3)<<endl;
}

Measured memory_bytes: 3592
S = gets.chomp
N = S.size

l0 = S[0] == '0' ? 0 : 1
l1 = S[0] == '1' ? 0 : 1
1.upto(N-1) do |i|
  c0 = l1 + (S[i] == '0' ? 0 : 1)
  c1 = l0 + (S[i] == '1' ? 0 : 1)
  l0, l1 = c0, c1
end

p [l0, l1].min

Measured memory_bytes: 1916
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
 
int main(){
  int n,m,k,l;
  vector<int> t,p,x;
  cin >> n;
  REP(i,n){
    cin >> k;
    t.push_back(k);
  }
  cin >> m;
  REP(i,m){
    cin >> k >> l;
    p.push_back(k-1);
    x.push_back(l);
  }
  int totaltime = 0;
  REP(i,n){
    totaltime += t[i];
  }
  REP(i,m){
    cout << totaltime - t[p[i]] + x[i] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <map>
#include <stack>
#include <cmath>
#define LL long long 
using namespace std; 
 
int n,k;
long long a[1005]={0},b[1005]={0};  
vector <long long > v1;
vector <long long > v2;
 
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=b[i-1]+a[i];
	}
	for(int i=0;i<n;i++)
		for(int j=i+1;j<=n;j++)
			v1.push_back(b[j]-b[i]);
	long long ans=0;
	for(int i=62;i>=0;i--)
	{ 
		v2.clear();
		long long x=(LL)1<<i;
		for(int i=0;i<v1.size();i++)
			if(v1[i]&x)
				v2.push_back(v1[i]);
		if(v2.size()>=k)
			v1=v2,ans+=x;
	}
	cout<<ans<<endl;
}

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

#define F first
#define S second
#define pb push_back
#define ld  double
#define ll long long
#define int long long


using namespace std;

const int MAXN = 301 * 1001  , MOD = 1e9 + 7 , sq = 333  ;


int par[MAXN] , sz[MAXN] ;;

vector < int > v[MAXN] ;

int root(int x)
{
    return (par[x]==-1?x:par[x]=root(par[x]))  ;
}

bool mrg(int x , int y )
{
    x = root(x) , y = root(y) ;
    if(x==y)
        return 0;
    if(sz[y]>sz[x])
        swap(x,y);
    par[y] = x ;
    sz[x] += sz[y] ;
    return 1 ;
}

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

   memset(par,-1,sizeof par);
   memset(sz,1,sizeof sz ) ;
   int n , m ;
   cin >> n >> m ;
   for(int i = 0 ; i < n ; i ++ )
   {
       int k ;
       cin >> k ;
       int x ;
       for(int j = 0 ; j < k; j ++ )
        cin >> x , v[x].pb(i) ;
   }
   int ans = n ;
   for(int i = 1 ;i <= m ; i ++ )
   {
       int k = v[i].size() ;
       for(int j = 0 ;  j < k - 1 ; j ++ )
            ans -= mrg(v[i][j],v[i][j+1]);
   }
   cout<<(ans==1?"YES":"NO");

}


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

enum Block {BLANK, HOUSE, CHURCH};
enum {Y, X};
const int NEXT[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int m, n;
int map[10][10];
int cy, cx;

int dfs(int y, int x, int remain) {
  if(!remain) return (y == cy) || (x == cx);
  auto bak = map[y][x];
  map[y][x] = BLANK;
  int res = 0;
  for(auto d: NEXT) {
    int ny = y + d[Y];
    int nx = x + d[X];
    while(true) {
      if(ny < 0 || n <= ny) break;
      if(nx < 0 || m <= nx) break;
      if(map[ny][nx] == HOUSE) {
        res += dfs(ny, nx, remain - 1);
        break;
      }
      ny += d[Y];
      nx += d[X];
    }
  }
  map[y][x] = bak;
  return res;
}

int main() {
  while(cin >> m >> n, m | n) {
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) cin >> map[i][j];

    int all = 0;
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) {
      if(map[i][j] == HOUSE) ++all;
      if(map[i][j] == CHURCH) {
        cy = i;
        cx = j;
      }
    }
    cout << dfs(cy, cx, all) << endl;
  }
}

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

#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;
void insert(int);
void inorder(Node );
void preorder(Node );

int main(){
  int n, i, x;
  char s[10];
  scanf("%d",&n);

  for (i = 0;i < n;i++){
    scanf("%s",s);
    if (s[0] == 'i'){
      scanf("%d",&x);
      insert(x);
    } else if (s[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } 
  }
  return 0;
  
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  z = malloc(sizeof(struct 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 r){
  if(r == NIL){
    return;
      }
  inorder(r->left);
  printf(" %d",r->key);
  inorder(r->right);
}
void preorder(Node r){
  if(r == NIL){
    return;
      }
  printf(" %d",r->key);
  preorder(r->left);
  preorder(r->right);
}

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

int main() {
	int N;
	cin >> N;
	int B[N];
	for (int i = 0; i < N; i++)
		B[i] = 0;
	for (int i = 0; i < N - 1; i++) {
		int a;
		cin >> a;
		B[a - 1]++;
	}
	for (int i = 0; i < N; i++)
		cout << B[i] << endl;
	return 0;
}


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

using namespace std;

struct Edge {
  int t,next;
  Edge() {}
  Edge(int a,int b):t(a),next(b) {}
};

Edge e[200005];
int head[100005];
bool col[100005],d[100005];

bool vis[100005];

bool dfs(int x) {
  vis[x]=1;
  bool s=d[x];
  for(int i=head[x];i;i=e[i].next)
    if (!vis[e[i].t]) {
    	bool v=dfs(e[i].t);
    	s^=v;
    	if (v) col[(i+1)>>1]^=1;
	}
  return s;
}

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  if (m&1) {
  	puts("-1");
  	return 0;
  }
  for(int i=1;i<=m;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[2*i-1]=Edge(y,head[x]);
  	head[x]=2*i-1;
  	e[2*i]=Edge(x,head[y]);
  	head[y]=2*i;
  	d[x]^=1;
  }
  dfs(1);
  for(int i=1;i<=m;i++)
    if (!col[i]) printf("%d %d\n",e[2*i].t,e[2*i-1].t);
    else printf("%d %d\n",e[2*i-1].t,e[2*i].t);
  return 0;
}

Measured memory_bytes: 6784
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if(b & 1) ans = ans * a;
		b >>= 1; a = a * a;
	}
	return ans;
}
int power_mod(int a, int b, int mod) {
	a %= mod;
	int ans = 1;
	while (b) {
		if(b & 1) ans = (ans * a) % mod;
		b >>= 1, a = (a * a) % mod;
	}
	return ans;
}
LL powerl(LL a, LL b) {
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = ans * a;
		b >>= 1ll;a = a * a;
	}
	return ans;
}
LL power_modl(LL a, LL b, LL mod) {
	a %= mod;
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = (ans * a) % mod;
		b >>= 1ll, a = (a * a) % mod;
	}
	return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
int n, p[105], ans = 0;
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	for (int i = 2; i < n; ++i)  {
		if (p[i - 1] < p[i] && p[i] < p[i + 1]) ++ans;
		else if (p[i + 1] < p[i] && p[i] < p[i - 1]) ++ans;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner vd = new Scanner(System.in);
		int a = vd.nextInt();
		int b = vd.nextInt();
		vd.close();
		int i = (a+b)/2;
		if((a+b)%2==1)System.out.println(i+1);
		else System.out.println(i);

	}

}


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


using namespace std;


const int MAXN = 100 * 1000 + 23;




int n;
vector<int> g[MAXN];


bool dfs(int, int);


int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[--u].push_back(--v), g[v].push_back(u); 
    }
    if (dfs(0, -1))
        cout << "First";
    else
        cout << "Second";
    return 0;
}
bool dfs(int v, int p) {
    int cnt = 0;
    for (auto u : g[v])
        if (u != p)
            cnt += (dfs(u, v)? 1: 0);
    if (cnt > 1) {
        cout << "First";
        exit(0);
    }
    return cnt < 1;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
#include <queue>
#define NUM 1000
using namespace std;
int main(){
    int n, q, query, x, t;
    priority_queue<int> s[NUM];
    scanf("%d %d", &n, &q);
    for(int i = 0; i < q; i++){
        scanf("%d %d", &query, &t);
        switch(query){
            case(0):
                scanf("%d", &x);
                s[t].push(x);
                break;
            case(1):
                if(!s[t].empty()) printf("%d\n", s[t].top());
                break;
            case(2):
                if(!s[t].empty()) s[t].pop();
                break;
        }
    }
}


Measured memory_bytes: 4128
import sys
input = sys.stdin.readline
Q = int(input())
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


for i in range(Q):
    l, r = map(int, input().split())
    print(numberlist[r]-numberlist[l-1])


Measured memory_bytes: 51504
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    S = read().split()
    S = list(map(lambda x: sorted(x.decode('UTF-8')), S))

    A = defaultdict(int)
    for i in range(N):
        s = ''.join(S[i])
        A[s] += 1

    cnt = 0
    for i in A.values():
        cnt += i*(i-1)//2
    print(round(int(cnt)))


main()


Measured memory_bytes: 41220
fun main(args: Array<String>) {
    val input: List<Int> = readLine()!!.split(" ").map{it.toInt()}
    val a: Int = input[0]
    val b: Int = input[1]
    val c: Int = input[2]
    val answer:Int
    answer = if (a > b){
        if (a > c){
            a * 10 + b + c
        } else{
            c * 10 + b + a
        }
    }else if (b > c){
        b * 10 + a + c
    }else{
        c * 10 + a + b
    }
    print(answer)
    return
}


Measured memory_bytes: 37764
import sys
input = sys.stdin.readline

n = int(input())
s = input().rstrip()
count = 0
for i in range(1, n-1):
  left = s[:i]
  right = s[i:]
  c = len(set(left) & set(right))
  if count < c:
    count = c
print(count)     


Measured memory_bytes: 3060
use std::io::*;

fn main() {
  let stdin = stdin();
  let mut lines = stdin.lock().lines();

  loop {
    let mut str = lines.next().unwrap().unwrap();
    if str == "-" { break; }

    let m = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
    let h: usize = lines.by_ref().take(m).map(|l| l.unwrap().parse::<usize>().unwrap()).sum();

    let (a, b) = str.split_at(h % str.len());
    println!("{}{}", b, a);
  }
}



Measured memory_bytes: 5028
#include<bits/stdc++.h>
#define INF (1e9)
#define MAX_V 305
using namespace std;
typedef pair<int,int> P;
//????????¨????§???????(???????????????????????????)
struct edge{int to, cap, rev;};

vector<edge> G[MAX_V]; //??°???????????£??\?????????
bool used[MAX_V];      //DFS??§?????§??????????????????????????°

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

//?¢?????????????DFS??§??¢???
int dfs(int v,int t,int f){
  if(v == t)return f;
  used[v]=true;
  for(int i=0; i<G[v].size() ;i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int 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;
}

//s??????t???????????§???????±???????
int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s, t, INF);
    if(f == 0)return flow;
    flow += f;
  }
}

map<P,int> A;

int main(){
  int n,m,a,b,s,t;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>a>>b;
    a--,b--;
    add_edge(a,b,1);
    A[P(a,b)]=i;
  }
  cin>>s>>t;
  s--,t--;
  int ans=max_flow(s,t);
  vector<int> ans2;
  for(int i=0;i<n;i++)
    for(int j=0;j<G[i].size();j++){
      int from=i,to=G[i][j].to;
      if(A.count(P(from,to))&&G[i][j].cap==2)
	ans2.push_back(A[P(from,to)]);
    }
  cout<<ans<<endl;
  sort(ans2.begin(),ans2.end());
  cout<<ans2.size()<<endl;
  for(int i=0;i<ans2.size();i++)cout<<ans2[i]+1<<endl;
  return 0;
}

Measured memory_bytes: 3264
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

const int MR = 310;

char S[MR];

int dp[MR][MR][MR];

// key observation - max subsequence of S and rev(S) is the length of the longest palindromic subsequence of S
int go(int b, int e, int k)
{
	if (dp[b][e][k])
		return dp[b][e][k];
	if (b >= e)
		return 0;
	if (b == e - 1)
		return dp[b][e][k] = 1;

	if (b == e - 2)
	{
		if (S[b] == S[b + 1] || k)
			return dp[b][e][k] = 2;
		else
			return dp[b][e][k] = 1;
	}

	if (S[b] == S[e - 1])
		return 2 + go(b + 1, e - 1, k);

	return dp[b][e][k] = max(max(go(b + 1, e, k), go(b, e - 1, k)), k ? 2 + go(b + 1, e - 1, k - 1) : 0);
}

int main()
{
	int K;
	scanf("%s%d", S, &K);

	printf("%d\n", go(0, strlen(S), K));

	return 0;
}

Measured memory_bytes: 112768
#include <iostream>
using namespace std;
int n,s;
int dp[12][2 << 10];
void dfs(int bit, int d, int s){
  dp[d][s]++;
  for (int i = 0; i < 10; i++){
    if (bit & (1 << i)){
	dfs(bit - (1 << i), d + 1, s + i * (d + 1));
      }
  }

  return ;
}
int main(){
  for (int i = 0; i < 12; i++){
    for (int j = 0; j < 1024; j++){
      dp[i][j] = 0;
    }
  }
  dfs((2 << 10) - 1, 0, 0);
  while (cin >> n >> s){
    if (s > 1023){
      cout << 0 << endl;
    }else{
      cout << dp[n][s] << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1252
def show(A):
    N = len(A)
    for i in range(N):
        if i :
            print(' ', end = '')
        print(A[i], end = '')
    print()

def insertionSort(A, N):
    show(A)
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j] 
            j = j - 1
        A[j+1] = v
        show(A)

N = int(input())
A = [int(i) for i in input().split()]

insertionSort(A, N)



Measured memory_bytes: 6316
let rec sum (n,k,ma,mi,s,x) =
  let ma = if ma<x then x else ma in
    let mi = if mi>x then x else mi in
      if k==0 then (s+x-ma-mi)/(n-2) else sum(n,k-1,ma,mi,s+x,read_int());;

while true do
  let n = read_int() in
    if n==0 then exit(0) else (print_int(sum(n,n-1,0,1000,0,read_int())); print_string "\n") done;;

Measured memory_bytes: 2052
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int H, W; cin >> H >> W;
  vector<vector<char>> S(H, vector<char> (W));
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < S.at(i).size(); j++) {
      cin >> S.at(i).at(j);
    }
  }
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < S.at(i).size(); j++) {
      if(S.at(i).at(j) == '#') cout << '#';
      else {
        int t = 0;
        for(int k = i - 1; k < i + 2; k++) {
          for(int l = j - 1; l < j + 2; l++) {
            if(k >= 0 && k < H && l >= 0 && l < W && S.at(k).at(l) == '#') t++;
          }
        }
        cout << t;
      }
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System;
using System.Numerics;
using static System.Math;
using static System.Console;

class E { static void Main() => new J(); }
class J
{
	int F() => int.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	int MOD = 1000000007;
	public J()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G();
		var N = I[0];
		var M = I[1];
		var dp = new long[M + 1, N + 1, 2];
		dp[0, 0, 0] = 1;
		for (var a = 0; a <= N; a++) dp[0, a, 1] = 1;
		for (var m = 1; m <= M; m++)
		{
			dp[m, 0, 1] = (dp[m - 1, 0, 1] + dp[m - 1, 1, 1]) % MOD;
			for (var a = 1; a < N; a++) dp[m, a, 1] = (dp[m - 1, a - 1, 1] + 2 * dp[m - 1, a, 1] + dp[m - 1, a + 1, 1]) % MOD;
			dp[m, N, 1] = (dp[m - 1, N, 1] + dp[m - 1, N - 1, 1]) % MOD;
			dp[m, 0, 0] = (dp[m - 1, 0, 1] + dp[m - 1, 1, 1]) % MOD;
			if (N == 1) dp[m, N, 0] = (dp[m - 1, 0, 1] + dp[m - 1, 1, 1]) % MOD;
			else
			{
				dp[m, 1, 0] = (dp[m - 1, 0, 1] + dp[m - 1, 1, 1] + dp[m - 1, 1, 0] + dp[m - 1, 2, 0]) % MOD;
				dp[m, N, 0] = (dp[m - 1, N, 0] + dp[m - 1, N - 1, 0]) % MOD;
			}
			for (var a = 2; a < N; a++) dp[m, a, 0] = (dp[m - 1, a - 1, 0] + 2 * dp[m - 1, a, 0] + dp[m - 1, a + 1, 0]) % MOD;
		}
		var ans = 0L;
		for (var a = 0; a <= N; a++) ans += dp[M, a, 0];
		Console.WriteLine(ans % MOD);
	}
}

Measured memory_bytes: 153824
import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
import copy
ans=copy.deepcopy(sosu)

for i in range(n):
  if gu>1:
    pflag=False
  if ans[a[i]]==0:
    ai = set(prime_factorize(a[i]))
    for j in ai:
      if ans[j]==0:
        pflag=False
        break
      else:
        ans[j]=0
  else:
    ans[a[i]]=0
  if a[i]%2==0:
    gu+=1
  ans[a[i]]=0
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')


Measured memory_bytes: 208884
#include <iostream>

int n;

int turn(int a[])
{
    int max = a[0];
    int id = 0;
    for(int ii = 0; ii < n; ++ii)
    {
        if (max < a[ii])
        {
            max = a[ii];
            id = ii;
        }
    }

    for (int ii = id; ii < n-1; ++ii)
    {
        a[ii] = a[ii+1];
    }

    --n;
    return max;
}

int main()
{
    std::cin >> n;
    int a[n];
    for (int ii = 0; ii < n; ++ ii)
    {
        std::cin >> a[ii];
    }

    int sum_alice = 0;
    int sum_bob = 0;
    int counter = 0;
    while (n > 0)
    {
        int num = turn(a);
        if (counter % 2 == 0)
        {
            sum_alice += num;
        }
        else
        {
            sum_bob += num;
        }
        ++counter;
    }

    std::cout << sum_alice - sum_bob;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
double i[114514];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	double b,c,d=0,e,f;
	int a;
	string s[114514],u;
	cin >>a;
	for(int n=0;n<a;n++) cin >>i[n];
	sort(i,i+a);
	b=(i[0]+i[1])/2;
	for(int n=2;n<a;n++){
		b=(b+i[n])/2;
	}
	cout <<fixed<<b<<'\n';
	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>
#define NOT_FOUND 0
int A[10000];
int n;
int linearSearch(int key){
  int i=0;
  A[n]=key;
  while(A[i]!=key){
    i++;
    if(i==n){
      return NOT_FOUND;
    }
  }
  return 1;
}
int main(){
  int i,key,a,cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%d",&key);
    if(linearSearch(key)) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 636
let n = int (stdin.ReadLine())
let h = stdin.ReadLine().Split() |> Array.map int64
let mutable ans = "Yes"
for i in 1..n - 1 do
     let sa = h.[i] - h.[i - 1] 
     if sa > 0L then h.[i] <- h.[i] - 1L
     elif sa < 0L then ans <- "No"
printfn "%s" ans

Measured memory_bytes: 28248
import java.util.Scanner;

   class Main{
      public static void main(String args[]){
       Scanner scan = new Scanner(System.in);

       String str = scan.nextLine();
       String str2 = scan.nextLine();
       boolean a = false;

       for(int i=0;i<str.length();i++){

          str =str.charAt(str.length()-1)+str.substring(0,str.length()-1);

          String str3 =str.substring(0,str2.length());

             if(str3.equals(str2)){

                a = true;

             }

       }

       if(a){
          System.out.println("Yes");
       }else{
          System.out.println("No");
       }

       }
   }


Measured memory_bytes: 26468
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int N, Q;
	std::cin >> N >> Q;
	
	std::vector<int> c(N);
	for (auto&& e : c)
		std::cin >> e;

	std::sort(c.begin(), c.end());

	for (int i = 0; i < Q; ++i) {
		int q;
		std::cin >> q;

		int ans = 0;
		for (int j = q; j - q <= c.back(); j += q) {
			ans = std::max(
				ans,
				*(std::lower_bound(c.begin(), c.end(), j) - 1) % q
			);
		}

		std::cout << ans << std::endl;
	}
}

Measured memory_bytes: 3760
#include <stdio.h>
#include <math.h>

double max, D1, D2, D3;
   
int main(void)
{
double x[100], y;
int n, i;
   
scanf("%d", &n);
   
for (i = 0; i < n; i++) {
scanf("%lf", &x[i]);
}
   
for (i = 0; i < n; i++) {
scanf("%lf", &y);
x[i] = x[i] - y;
if (x[i] < 0) x[i] = -x[i];
if (x[i] > max) max = x[i];
}
   
for (i = 0; i < n; i++) {
D1 += y = x[i];
D2 += y *= y;
D3 += x[i] * y;
}
printf("%lf\n", D1);
printf("%lf\n", sqrt(D2));
printf("%lf\n", cbrt(D3));
printf("%lf\n", max);
   
return 0;
}

Measured memory_bytes: 672
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
	long long x,k,d,c;
	long long a=-10000000000000000,b,i=0,f=0;
	cin >> x >> k >> d;
	b=abs(x);
	while(i<k){
		if(x>0){
			if(d>0){
				c=min(max(x/d,1ll),k-i);
				x-=c*abs(d);
			}
			else{
				c=min(max(x/abs(d),1ll),k-i);
				x+=c*abs(d);
			}
			if(x<=0){
				f=1;
			}
		}
		else{
			if(d>0){
				c=min(max(abs(x)/d,1ll),k-i);
				x+=c*d;
				if(x>=0){
					f=1;
				}
			}
			else{
				c=min(max(abs(x)/abs(d),1ll),k-i);
				x-=c*abs(d);
				if(x>=0){
					f=1;
				}
			}
		}
		i+=c;
		if(i%2==1 && abs(x)<abs(a)){
			a=abs(x);
		}
		if(i%2==0 && abs(x)<abs(b)){
			b=abs(x);
		}
		if(f){
			break;
		}
	}
	if(k%2==1){
		cout << a << endl;
	}
	else{
		cout << b << endl;
	}
	return 0;
}


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

int main() {
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int rel = 0;

    for (int i = 0; i <= A; i++) {
        for (int j = 0; j <= B; j++) {
            for (int k = 0; k <= C; k++) {
                if (500*i + 100*j + 50*k == X) rel++;
            }
        }
    }

    cout << rel << endl;
}

Measured memory_bytes: 3572
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

  vector<int> id;
  rep(i, s.size()) {
    if (s[i] != 'x') {
      id.push_back(i);
    }
  }

  if (id.size() == 0) {
    cout << 0 << endl;
    return 0;
  }

  queue<char> q1, q2;
  if (id.size() % 2 != 0) {
    int M = id.size() / 2;
    rrep(i, id[M]) { q1.push(s[i]); }
    for (int i = id[M] + 1; i < s.size(); i++) {
      q2.push(s[i]);
    }
  } else {
    int M = id.size() / 2;
    for (int i = id[M - 1]; i >= 0; i--) {
      q1.push(s[i]);
    }
    for (int i = id[M]; i < s.size(); i++) {
      q2.push(s[i]);
    }
  }
  q1.push('$');
  q2.push('$');

  int result = 0;
  while (!q1.empty() || !q2.empty()) {
    if (q1.front() == q2.front()) {
      q1.pop();
      q2.pop();
    } else if (q1.front() == 'x') {
      q1.pop();
      result++;
    } else if (q2.front() == 'x') {
      q2.pop();
      result++;
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 1020
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <queue>
#include <sstream>
#include <utility>
#include <vector>

using namespace std;

typedef long long Long;
#define whole(xs) xs.begin(), xs.end()

struct RangeSumQuery {
    int N;
    int* v;
    static int FindPow2(int x) {
        int x1 = 1;
        while (x1 < x) {
            x1 *= 2;
        }
        return x1;
    }
    RangeSumQuery(int N_, int init = 0) : N(FindPow2(N_)) {
        v = new int[N * 2];
        fill(v, v + N * 2, init);
    }
    ~RangeSumQuery() {
        delete[] v;
    }
    int dfs(int s, int t, int a, int b, int k) {
        if (s <= a && b <= t) return v[k];
        if (t <= a || b <= s) return 0;
        int m = (a + b) / 2;
        return dfs(s, t, a, m, k * 2) + dfs(s, t, m, b, k * 2 + 1);
    }
    // 半開区間[s, t)の和を返す
    int query(int s, int t) {
        return dfs(s, t, 0, N, 1);
    }
    // 要素iにxを加える
    void add(int i, int x) {
        i += N;
        while (i > 0) {
            v[i] += x;
            i /= 2;
        }
    }
};

int main() {
    int n, q; cin >> n >> q;
    RangeSumQuery rsq(n + 1, 0);
    for (int i = 0; i < q; i++) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            rsq.add(x, y);
        } else {
            cout << rsq.query(x, y + 1) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2060
import java.util.*;

public class Main {    
    
   public static void main(String[] args){
       
       Scanner sc = new Scanner(System.in);
    
       StringBuilder sb = new StringBuilder();
       
       String S = sc.next();
       
       for(int i = 0;i < S.length();i++){
           char ch = S.charAt(i);
           if(ch == '0')
               sb.append(ch);
           if(ch == '1')
               sb.append(ch);
           if(ch == 'B'){
               if(sb.length() == 0){
                 continue;
               }else{
                  sb.deleteCharAt(sb.length() - 1);
               }
           }
       }
       
       System.out.println(sb.toString());
    
   }   
}
        
        
        

Measured memory_bytes: 21844
using System;
using System.Linq;
class p
{
  static void Main()
  {
    int N = int.Parse(Console.ReadLine());
    string[] arr = new string[N];
    bool result = true;
    for (int i = 0; i < N; i++) {
      string s = Console.ReadLine();
      if (0 < i) {
        if (arr.Contains(s) || s[0] != arr[i-1][arr[i-1].Length-1]) {
          result = false;
          break;
        }
      }
      arr[i] = s;
    }
    Console.WriteLine(result ? "Yes" : "No");
  }
}

Measured memory_bytes: 11220
from collections import deque
from bisect import bisect_left

N = int(input())
d = deque([])
l = [int(input()) for _ in range(N)]

d.append(l[0])

for i in l[1:]:
    v = bisect_left(d, i)
    if v == 0:
        d.appendleft(i)
    else:
        d[v-1] = i

print(len(d))

Measured memory_bytes: 8828
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n],sum=0;
  rep(i,n){
    int t;
    cin>>t;
    sum+=t;
    a[i]=t;
  }
  sort(a,a+n);
  rep(i,n) {
    if (sum%10!=0){
      cout<<sum<<endl;
      return 0;
    }
    if (a[i]%10!=0)sum-=a[i];
  }
  if(sum%10!=0) cout<<sum<<endl;
  else cout<<0<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int seiza[200][2],star[1000][2],dx,dy,x,y,n,m,cou;
int main(){
    for(;;){
        cin>>n;
        if(n==0)break;
        for(int i=0;i<n;i++){
            cin>>seiza[i][0]>>seiza[i][1];
        }
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>star[i][0]>>star[i][1];
        }
        for(int i=0;i<m;i++){
            cou=0;
            dx=star[i][0]-seiza[0][0];
            dy=star[i][1]-seiza[0][1];
            for(int j=1;j<n;j++){
                    x=seiza[j][0]+dx;
                    y=seiza[j][1]+dy;
                for(int k=0;k<m;k++){
                    if(star[k][0]==x&&star[k][1]==y){
                        cou++;
                        break;
                    }
                }
                if(cou==n-1)break;
            }
            if(cou==n-1)break;
        }
        cout<<dx<<" "<<dy<<endl;
    }
return 0;
}

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

int main(){
    int n;
    while(cin >> n, n){
        int a[26] = {};
        char c[n];
        for(int i = 0; i < n; i++)  cin >> c[i];
        int ans = -1, x, y;
        for(int i = 0; i < n; i++){
            int tmp = c[i]-'A';
            a[tmp]++;
            x = y = 0;
            for(int j = 0; j < 26; j++){
                if(a[j] > x)    y = x, x = a[j];
                else if(a[j] > y)   y = a[j];
            }

            if(y+(n-1-i) < x){
                ans = i;
                break;
            }
        }

        if(ans != -1){
            char can = ' ';
            for(int i = 0; i < 26; i++)  if(a[i] == x) can = 'A' + i;
            cout << can << " " << ans+1 << endl;
        }else{
            cout << "TIE" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3104
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    left = 0
    right = n - 1
    print(left)
    first = input()
    second = 'Male' if first == 'Female' else 'Female'
    p = 0
    while True:
        p = (left + right) // 2
        print(p)
        status = input()
        if status == 'Vacant':
            break
        if p % 2 == 0:
            if status == first:
                left = p + 1
            else:
                right = p
        else:
            if status == second:
                left = p + 1
            else:
                right = p


if __name__ == '__main__':
    main()


Measured memory_bytes: 9204
from itertools import permutations
n = int(input())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
lis = permutations(range(1, n + 1))
a = 0
b = 0
for i, l in enumerate(lis):
    if p == list(l):
        a = i + 1
    if q == list(l):
        b = i + 1
print(abs(a - b))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; ++i) cin >> h[i];
  int first = 0;
  int ans = 0;
  while(true){
    for(int i = first; i < n; ++i){
      if(h[i] > 0) h[i]--;
      else {
        if(i == first) ++first;
        else break;
      }
    }
    if(first == n) break;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(ll i=(begin);i<=(end);i++)
#define REP(i, n) FOR(i,1,n)
#define IFOR(i, begin, end) for(ll i=(end);i>=(begin);i--)
#define IREP(i, n) IFOR(i,1,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())

#define ll long long
using namespace std;

bool is_prime(int k)
{
    for(int j=2;j*j<=k;j++){
        if(k%j==0) {
            return false;
        }
    }
    return true;
}

int main()
{
	stringstream ss;
    // 入力
    ll N,M;
    cin>>N>>M;
    ll Nor=N;
    ll Mor=M;
    ll ans=1;
    FOR(i,N,M){
        // cout<<M%i<<endl;
        if(M%i==0) {
            ans=M/i;
            break;
        }

        else if(i>100000000) {
            if(N<=10){
                IFOR(j,10,2){
                    if(M%j==0 && N==j) {
                        ans=j;
                        break;
                    }
                }
            } else{
                ans=1;
                break;
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}

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

int main(){
   /*int n;
   cin >> n;
   int a = (n/5)%6;
   int b = n%5;
   char s = '';
   int c = 1;
   for(int i = 6-a; i<6;i++){
       s = s + (char)c; 
   }
   for(int i = 0;i<6-a)
   */
   int n;
   cin >> n;
   int a[n];
   for(int i =0;i<n;i++){
       int ai;
       cin >> ai;
       a[i] = ai -i-1;
   }
   sort(a,a+n);
   int t;
   if(n % 2 == 0){
       t = (a[n/2 -1] + a[n/2])/2;
   }else{
       t = a[n/2 ];
   }
   long long  m = 0;
   for(int i = 0;i<n;i++){
       m += abs(a[i]-t);
   }
   cout << m << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
    int a,b,c,x;cin>>a>>b>>c>>x;
    int cnt=0;
    for(int i=0;i<=a;++i){
        for(int j=0;j<=b;++j){
            for(int k=0;k<=c;++k){
                if(i*500+j*100+k*50==x)cnt++;
            }
        }
    }
    cout<<cnt<<endl;
}

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

const int INF=1e9;

int main()
{
   int N,K; cin>>N>>K;
   vector<int> h(N);
   for(int i=0;i<N;i++) cin>>h[i];

   vector<int> dp(N,INF);
   dp[0]=0;
   for(int i=0;i<N;i++){
      for(int j=1;j<=K;j++) if(i+j<N){
         if(i+j<N) dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
      }
   }
   cout<<dp[N-1]<<endl;
   return 0;
}


Measured memory_bytes: 1024
import java.util.*;



class Main {
	Scanner sc = new Scanner(System.in);


	String[] block;
	public void run() {
		while(sc.hasNext()){
			block=new String[8];
			for(int i=0;i<8;i++){
				block[i]=sc.next();
			}
			Loop:for(int i=0;i<8;i++)
				for(int j=0;j<8;j++){
					if(block[i].charAt(j)=='1'){
						if(j+1<8 && block[i].charAt(j+1)=='1'){
							if(j+2<8 && block[i].charAt(j+2)=='1'){
								ln("C");
							}else{
								if(j>=1 && block[i+1].charAt(j-1)=='1'){
									ln("G");
								}else{
									if(i+1<8 &&j+1<8 && block[i].charAt(j+1)=='1' && block[i+1].charAt(j)=='1'){
										ln("A");
									}else{
										ln("E");
									}
								}
							}
						}else{
							if(i+2<8 &&block[i+2].charAt(j)=='1'){
								ln("B");
							}else{
								if(i+1<8 && j+1<8 && block[i+1].charAt(j+1)=='1'){
									ln("F");
								}else{
									ln("D");
								}
							}
						}
						break Loop;
					}
				}
		}
	}

	public boolean isA(){

		return false;
	}




	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

class P{
	double x;
	double y;
	P(double _x,double _y){
		x=_x;
		y=_y;
	}

	public static double dot(P a,P b){
			return a.x*b.x+a.y*b.y;
	}
	public static  double cross(P a,P b){
		return a.x*b.y-a.y*b.x;
	}
	public P a(P a){
		return new P(x+a.x,y+a.y);
	}
	public P s(P a){
		return new P(x-a.x,y-a.y);
	}

	public double norm(){
		return Math.sqrt(x*x+y*y);
	}

	public static int ccw(P a,P b,P c){
		if(P.cross(b.s(a),c.s(a))>Double.MIN_NORMAL){
			return 1;
		}
		if(P.cross(b.s(a),c.s(a))<-Double.MIN_NORMAL){
			return -1;
		}
		if(P.dot(b,c)<-Double.MIN_NORMAL)return 2;
		if(b.norm()<c.norm()-Double.MIN_NORMAL)return -2;
		return 0;
	}
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
  }
  vector<int> v = {-1, -1, -1};
  ll ans = 1;
  for(int i=0;i<n;++i) {
    int cnt = 0;
    for(int j=0;j<3;++j) {
      if(v[j] + 1 == a[i]) {
        cnt++;
      }
    }

    if(cnt == 0) {
      cout << "0" << endl;
      return 0;
    }

    if(a[i] != 0 && cnt == 3) {
      ans *= 3;
      ans %= MOD;
    } else if(a[i] != 0 && cnt == 2) {
      ans *= 2;
      ans %= MOD;
    }

    for(int j=0;j<3;++j) {
      if(v[j] + 1 == a[i]) {
        v[j] = a[i];
        break;
      }
    }
    sort(v.begin(), v.end());
  }
  int cnt = 0;
  for(int i=0;i<3;++i) {
    if(v[i] == -1) {
      cnt++;
    }
  }
  if(cnt < 2) {
    ans *= 6;
    ans %= MOD;
  } else {
    ans *= 3;
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int main() {
    int n, m, x, lans=0, rans=0, now=0;
    cin >> n >>m >> x;
    vector<int> a(m);
    rep(i, m)cin >> a.at(i);
    for(int i = 0; i <= x; i++){
        if(now >= m)break;
        if(a.at(now) == i){
            lans++;
            now++;
        }
    }
    for(int i = x; i <= n; i++){
        if(now >= m)break;
        if(a.at(now) == i){
            rans++;
            now++;
        }
    } 
    cout << min(lans, rans);
}

Measured memory_bytes: 256
n = int(input())
moneys = []
for i in range(n):
    tmp = input().split()
    x = float(tmp[0])
    y = tmp[1]
    moneys.append([x,y])


sum = 0
for i in moneys:
    if i[1] == "JPY":
        sum = sum + i[0]
    else:
        sum = sum + i[0] * 380000.0

print(sum)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, pair<int, int> > p;
 
#define MOD 1000000007

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

    string S;
    cin >> S;

    int a = 0;
    int c = 0;

    for(int i = 0; i < S.length(); i++) {
        if(S[i] == 'R') {
            c++;
            a = c;
        } else {
            c = 0;
        }
    }

    cout << a << endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

int main() {
    init();

    int n;
    cin >> n;

    vector<VI> c(n);
    FOR(i, 0, n) {
        int m;
        cin >> m;
        c[i].resize(m);
        FOR(j, 0, m)cin >> c[i][j];
    }

    ll ans = 0;
    priority_queue<int> q;
    rFOR(i, 0, n) {
        for (int j : c[i])q.push(j);
        ans += q.top(); q.pop();
    }
    cout << ans << "\n";
}



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

vector<int> ans;
int main(){
  int n;

  cin >> n;
  for(int i=0; i<n; ++i){
    int i_num,i_max,i_min;
    string num;
    string max;
    string min;

    cin >> num;
    min = num;
    max = num;

    sort(begin(min),end(min));
    sort(begin(max),end(max),greater<char>());
    //cout << "min = " << min << endl;
    //cout << "max = " << max << endl;
    i_min = stoi(min);
    i_max = stoi(max);
    i_num = i_max - i_min;
    ans.push_back(i_num);
  }
  
  for(auto i: ans){
    cout << i <<endl;
  }
  return 0;
}

Measured memory_bytes: 3228
import numpy as np

N=int(input())

A=np.array(input().split(" "),dtype=np.int64)

step=[0]
Max=A[0]
for i in range(1,N):
    if(Max>A[i]):
        step.append(Max-A[i])
    else:
        Max=A[i]
        step.append(0)

print(sum(step))

Measured memory_bytes: 53228
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define ll long long int
using namespace std;
int main()
{
    int n;
  cin>>n;
  float j=2*3.141592653589793238*n;
  cout<<j;
 }


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

int main(){
    ll h, w, n;
    cin >> h >> w >> n;
    map<P,ll> m;
    rep(i,n){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        for(ll x = -2; x <= 0; x++){
            for(ll y = -2; y <= 0; y++){
                ll c = a + x, d = b + y;
                if(c >= 0 && c < h-2 && d >= 0 && d < w-2) m[P(c,d)]++;
            }
        }
    }
    ll ans[10] = {};
    ans[0] = (h-2)*(w-2);
    for(auto x : m) {
        ans[x.second]++;
        ans[0]--;
    }
    rep(i,10) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 56448
#include<bits/stdc++.h>
// #include"myfile.h"

#define int long long
#define pb push_back
#define range(v) v.begin(),v.end()
#define mod (int)(1e9 + 7)
#define inf (int)(1e15)
#define N (int)(2e5 + 10)

using namespace std;


void solve() {
	int n;
	cin >> n;
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		int noTerms = n / i;
		int val = (noTerms * (noTerms + 1)) / 2 * i;
		tot += val;
	}


	cout << tot << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cin.tie(nullptr);
	int t_c = 1;
//	cin >> t_c;
	while (t_c--)
		solve();
}

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N, K;
    cin >> N >> K;
    int res = 1;
    REP(i, N) {
        res = min(res + K, res*2);
    }
    cout << res << endl;
    return 0;
}



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

using namespace std;

#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define For(i, s, n) for(int i = s; i < (int)(n); ++i)

int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;

  vector<int> distances(n);

  Rep(a, n) {
    For(b, a + 1, n) {
      int d = min(b - a, abs(a - x) + abs(b - y) + 1);
      distances[d]++;
    }
  }

  For(i, 1, n) {
    cout << distances[i] << endl;
  }
  return 0;
}


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

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

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

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

    int n;
    cin >> n;
    int a[n];
    ll top = 1;
    rep(i,n){
        cin >> a[i];
        top = lcm(top, a[i]);
    }
    
    long double bottom = 0;
    rep(i,n){
        bottom += (long double) top / a[i];
    }
    
    printf("%.6Lf\n", top / bottom);

    return 0;
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))
csum = []
s = 0

for i in range(N):
    s += a[i]
    csum.append(s)

if N == 2:
    print(abs(a[0] - a[1]))
    exit()

s = sum(a)
ans = 1e10
for i in range(1,N-1):
    ans = min(ans,abs(2*csum[i]-s))

print(ans)

Measured memory_bytes: 24832