akhauriyash/Code-Regression huggingface dataset:
L, R = map(int,input().split())
L_mod = L%2019
if L_mod ==0:
  print(0)
else:
  R_mod = R%2019
  if R_mod ==0:
    print(0)
  else:
    if L_mod<R_mod:
      Ls = L//2019
      Rs = R//2019
      if Rs-Ls ==0:
        list =[]
        for i in range(L_mod,R_mod,1):
          mod_i = i%2019
          for j in range(i+1,R_mod+1,1):
            mod_j = j%2019
            mod = (mod_i *mod_j)%2019
            list.append(mod)

        print(min(list))
      else:
        print(0)
    else:
      print(0)

Measured memory_bytes: 75316
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}

int main() {
  int x,y;
  cin >> x >> y;
  string ans="No";
  if(2*x<=y&&y<=4*x&&y%2==0) ans="Yes";
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628
/// awoooooo

# include <bits/stdc++.h>

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

const int N = (int)1e6 + 5;
const int inf = (int)1e9 + 7;

int shift(int x, int len, int pos, int cf){
  int res = 0;
  for(int i = 0; i < len; ++i){
    if(cf == -1 && i == pos) continue;
    int to = (1 << (i + (i >= pos) * cf));
    res += ((x >> i) & 1) * to;
  }
  return res;
}

vector < int > solve(int n, int f, int s){
  if(n == 1){
    return {f, s};
  }
  int pos = -1;
  for(int i = 0; i < n; ++i){
    if(((f >> i) & 1) == ((s >> i) & 1)){
      continue;
    }
    pos = i;
    break;
  }
  int fx = shift(f, n, pos, -1);
  int sx = shift(s, n, pos, -1);
  vector < int > part1 = solve(n - 1, fx, fx ^ 1);
  vector < int > part2 = solve(n - 1, fx ^ 1, sx);
  vector < int > res;
  for(int i : part1){
    int val = shift(i, n - 1, pos, 1);
    if((f >> pos) & 1){
      val += (1 << pos);
    }
    res.push_back(val);
  }
  for(int i : part2){
    int val = shift(i, n - 1, pos, 1);
    if((s >> pos) & 1){
      val += (1 << pos);
    }
    res.push_back(val);
  }
  return res;
}

int n, a, b;

int main(){
  scanf("%d %d %d", &n, &a, &b);
  if(__builtin_popcount(a) % 2 == __builtin_popcount(b) % 2){
    printf("NO\n");
    return 0;
  }
  printf("YES\n");
  vector < int > ans = solve(n, a, b);
  for(int i = 0; i < (1 << n); ++i){
    printf("%d ", ans[i]);

  }
  return 0;
}


Measured memory_bytes: 1628
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
	int ret=0,f=0;char c=gc();
	while(!isdigit(c)){if(c=='-')f=1;c=gc();}
	while(isdigit(c)){ret=ret*10+c-48;c=gc();}
	if(f)return -ret;return ret;
}
int main()
{
	scanf("%1d%1d%1d%1d",&a,&b,&c,&d);
	int x=10*a+b,y=10*c+d;
	if(x<1||x>12)
	{
		if(y<1||y>12)puts("NA");
		else puts("YYMM");
	}
	else{
		if(y<1||y>12)puts("MMYY");
		else puts("AMBIGUOUS");
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define SORT(c) sort((c).begin(),(c).end())
#define MOD 1000000007
//S.size()
//配列名.Length()
using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<bool> VB;
typedef unsigned long long ll;


int main(void){
	int N,M; cin>>N>>M;
	int a[M],b[M];

	int jud[N];
	rep(t , N) jud[t] = 0;


	rep(i , M){
		cin>>a[i];
		cin>>b[i];
	}

	rep(j , N){
		for(auto x: a) if(x == j + 1)jud[j]++;
		for(auto y: b) if(y == j + 1)jud[j]++;
	}

	rep(l , N) cout<<jud[l]<<endl;
}


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

namespace _156_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            var N = int.Parse(s[0]);
            var R = int.Parse(s[1]);
            if (N < 10)
            {
                Console.WriteLine(R + 100 * (10 - N));
            }
            else
            {
                Console.WriteLine(R);
            }
        }
    }
}


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

int main() {
 ll n; cin >> n;
 if(n<=6){
   cout << 1 << endl;
  return 0;
 }
 n-=6;
 ll m=n/11;

 if(n%11==0){
   cout << 2*m+1 << endl;
   return 0;
 }

 if(m*11+1<=n && m*11+5>=n)cout << 2*m+2 << endl;
 else cout << 2*m+3 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  int n = s.length();
  s.insert(s.begin(), '$');
  vector<int> dp(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (i >= 2 && s[i - 1] == 'C' && s[i] == 'B') {
      dp[i] = dp[i - 2] + 1;
    }
    if (s[i] == 'A') {
      dp[i] = dp[i - 1];
    }
  }
  long long ret = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'A') ret += dp[i];
  }
  cout << ret << endl;
  return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-6;

int n, m;
char s[M + 5], t[M + 5];

int cal(int p)
{
    int c = 0;
    for(int i = 1; i <= m; ++i)
    {
        if(s[p + i - 1] != t[i]) ++c;
    }
    return c;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%s %s", s + 1, t + 1);
    int mi = inf;
    n = strlen(s + 1), m = strlen(t + 1);
    for(int i = 1; i + m - 1 <= n; ++i)
    {
        mi = min(mi, cal(i));
    }
    printf("%d\n", mi);
    return 0;
}


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

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var (X, Y) = Slice2<long>();
            var cnt = 0;
            for (long num = X; num <= Y; ++cnt, num *= 2) ;
            WriteLine(cnt);
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

Measured memory_bytes: 27520
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <set>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;
typedef long long LL;
#define ALL(a) (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#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 IFOR for(VI::iterator it = v_inhand(); it != v_inhand.end(); ++it) {}
#define INF 1000000000

int N;
VVI F; // f_i,j,k = f[i][j * 2 + k]
VVI P;
int solve(VI &open, int jk) {
  // jkまで決めた(0ならまだ何も決めてない、1なら月曜午前だけ。10まで決めたら終了)
  if (jk == 10) {
    bool opens = false;
    REP(j, 10) {
      if (open[j] == 1)
        opens = true;
    }
    if (!opens)
      return INF;
    int profit = 0;
    int c = 0;
    REP(i, N) {
      c = 0;
      REP(j, 5) {
        if (F[i][j * 2] == 1 && open[j * 2] == 1)
          ++c;
        if (F[i][j * 2 + 1] == 1 && open[j * 2 + 1] == 1)
          ++c;
      }
      profit += P[i][c];
    }
    return profit;
  }
  int res;
  open[jk] = 1;
  res = solve(open, jk + 1);
  open[jk] = 0;
  int res2 = solve(open, jk + 1);
  if (res2 != INF)
    res = max(res, res2);
  return res;
}
int main() {
  cin >> N;

  REP(i, N) {
    VI v;
    REP(j, 10) {
      int f;
      cin >> f; v.PB(f);
    }
    F.PB(v);
  }
  REP(i, N) {
    VI v;
    REP(j, 11) {
      int p;
      cin >> p; v.PB(p);
    }
    P.PB(v);
  }
  VI open(10, 0);
  cout << solve(open, 0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

int main(){

  int N, M; cin >> N >> M;

  vector <bool> bridge(N - 1);

  vector < pair <int, int> > BA(M);
  for (int i = 0; i < M; i++){
    int a, b; cin >> a >> b;
    a--; b--;
    BA[i].first = b;
    BA[i].second = a;
  }
  
  sort(BA.begin(), BA.end());

  int ans = 0, now = -1;
  for (int i = 0; i < M; i++){
    
    bool flag = false;

    int A = BA[i].second, B = BA[i].first;

    if (A <= now && now < B){
    }else{
      now = B - 1;
      ans++;
    }
  }
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
  		long ans=0;

  		int[] a=new int[n];
		for(int c=1;c<n+1;c++){
    		if(c%3!=0&&c%5!=0){
              ans+=c;
            }
    	}
    
 	

    	System.out.println(ans);
    }
}


Measured memory_bytes: 39500
#include<stdio.h>
int main(){
	double v=0.0,t=0.0,y=0.0;
	
	while(scanf("%lf",&v)!=EOF){
	t=v/9.8;
	y=4.9*t*t;
	printf("%.0f\n",(y/5+1)+0.5);
	}
return 0;
}

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

int main ()
{
	int a,b,c; cin>>a>>b>>c;
	
	 int s=a+b+c;
	 
	 if(s>=22)  cout<<"bust"<<endl;
	 
	 else 
	 cout<<"win"<<endl;
	


}



Measured memory_bytes: 3624
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		ArrayList<Edge> list=new ArrayList<>();
		int sum=0;
		for(int i=0; i<n-1; i++){
			list.add(new Edge(0,i+1));
			sum+=n-2-i;
		}
		if(sum<k){
			System.out.println(-1);
			return;
		}else if(sum>k){
			int a=sum-k;
			for(int i=1; i<n-1; i++){
				for(int j=i+1; j<n; j++){
					a--;
					list.add(new Edge(i,j));
					if(a==0){
						break;
					}
				}
				if(a==0){
					break;
				}
			}
		}
		System.out.println(n-1+sum-k);
		for(Edge i:list){
			System.out.println((i.u+1)+" "+(1+i.v));
		}
	}
	static class Edge{
		int u;
		int v;
		Edge(int u,int v){
			this.u=u;
			this.v=v;
		}
	}
}




Measured memory_bytes: 24532
N = int(input())

def ans(s):
    if int(s) > N:##Nより大きかったら終了
        return 0
    else:
        cnt = int(s.count("7") > 0 and s.count("5") > 0 and s.count("3") > 0) ##753数であるかどうか
        return ans(s+"3") + ans(s+"5") + ans(s+"7") + cnt ##その数に3,5,7をつけて753数になるものの数
    
print(ans("0"))##最初の状態は空文字ではなく0.一桁で753数になるものはないため

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(ll, N);
    CIN(ll, M);

    ll ans = 0;
    if ( N == 1 && M == 1 ) {
        ans = 1;
    } else if ( N == 1 || M == 1 ) {
        ans = max(N, M) - 2;
    } else {
        ans = (N - 2) * (M - 2);
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s,t;cin>>s>>t;
    ll n=s.length(),m=t.length();
    ll dp[n+1][m+1];
    for(int i=0;i<=n;++i)
    {
        dp[i][0]=0;
    }
    for(int i=0;i<=m;++i)
    {
        dp[0][i]=0;
    }
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<=m;++j)
        {
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(s[i-1]!=t[j-1])
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
            else
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
        }
    }
    //cout<<dp[n][m]<<endl;
    if(dp[n][m]==0)
    {
        cout<<"\n";
        return 0;
    }
    string ans="";
    int ti=n,tj=m;
    while(ti>0 && tj>0)
    {
        
        if(s[ti-1]==t[tj-1])
        {
            ans+=s[ti-1];
            ti--;tj--;
        }
        else if(dp[ti][tj-1]>=dp[ti-1][tj])
        {
            tj--;
        }
        else
        {
            ti--;
        }
        
        
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    
    return 0;
}

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

int gcd(int x, int y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}
signed main(void)
{
	int a, b, k;
	int g, j;
	cin >> a >> b >> k;
	g = gcd(a, b);
	j = 0;
	for (int i = g; i >= 1; i--)
	{
		if (g % i == 0)
		{
			j++;
			if (j == k)
			{
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}


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

int main(){
  int w,h,n;
  cin>>w>>h>>n;
  int area[4]={0,w,0,h}; //{xの下限,ｘの上限,yの下限,yの上限}
  int x,y,a;
  for(int i=0;i<n;i++){
    cin>>x>>y>>a;
    if(a==1 || a==3) area[a-1]=max(area[a-1],a<3?x:y);
    else area[a-1]=min(area[a-1],a<3?x:y);
  }
  int t=max(0,(area[1]-area[0]));
  int p=max(0,(area[3]-area[2]));
  cout<<t*p;

}


Measured memory_bytes: 256
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

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

  s = s + s;
  bool found = false;
  rep(i, s.size() - p.size()) if (s.substr(i, p.size()) == p) found = true;

  if (found)
    puts("Yes");
  else
    puts("No");
}


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

using namespace std;

const int N = 200000 + 5, M = 200000 + 5;
int stk[N], top;
int fr[M], to[M], h[N], tot, n, m, rd[N];
inline void adde (int u, int v)
{
	tot++;
	fr[tot] = h[u];
	to[tot] = v;
	h[u] = tot;
	rd[v]++;
}

queue<int> Q;
inline bool judge ()
{
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (!rd[i])
		{
			Q.push (i);
			++cnt;
		}
	while (Q.size ())
	{
		int k = Q.front();
		Q.pop();
		for (int i = h[k]; i; i = fr[i])
		{
			rd[ to[i] ]--;
			if (!rd[to[i]])
			{
				++cnt;
				Q.push (to[i]);
			}
		}
	}
	return cnt == n;
}

bool flag = true;
bool ins[N], vis[N];
int num[N], pos[N];
vector<int> c;
bool inq[N];
inline void dfs (int u)
{
	vis[u] = 1;
	if (ins[u])
	{
		flag = false;
		for (int i = num[u]; i <= top; ++i)
		{
			c.push_back (stk[i]);
			inq[ stk[i] ] = 1;
			pos[ stk[i] ] = i - num[u] + 1;
		}
		for (int p = 1; p <= n; ++p)
		{
			for (int i = h[p]; i; i = fr[i])
			{
				int x = p, y = to[i];
				if ((!inq[x]) || (!inq[y])) continue;
				if (pos[y] == pos[x] + 1) continue;
				if (pos[x] == (signed)c.size () && pos[y] == 1) continue;
				if (pos[x] < pos[y])
				{
					vector<int> tmp;
					tmp.clear ();
					for (int k = 0; k < (signed)c.size (); ++k)
					{
						if (k + 1 <= pos[x] || k + 1 >= pos[y])
						{
							tmp.push_back (c[k]);
						}
						else inq[ c[k] ] = 0;
					}
					for (int k = 0; k < (signed)tmp.size (); ++k)
						pos[ tmp[k] ] = k + 1;
					c = tmp;
				}
				else
				{
					vector<int> tmp;
					tmp.clear ();
					swap (x, y);
					for (int k = 0; k < (signed)c.size (); ++k)
					{
						if (k + 1 >= pos[x] && k + 1 <= pos[y])
						{
							tmp.push_back (c[k]);
						}
						else inq[ c[k] ] = 0;
					}
					for (int k = 0; k < (signed)tmp.size (); ++k)
						pos[ tmp[k] ] = k + 1;
					c = tmp;
				}
			}
		}
		sort (c.begin (), c.end());
		printf ("%d\n", (signed)c.size ());
		for (int i = 0; i < (signed)c.size (); ++i)
			printf ("%d\n", c[i]);
	}
	else
	{
		ins[u] = 1;
		num[u] = ++top;
		stk[top] = u;
	}
	for (int i = h[u]; i && flag; i = fr[i])
	{
		dfs (to[i]);
	}
	ins[u] = 0;
	--top;
}


int main ()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		scanf ("%d%d", &x, &y);
		adde (x, y);
	}
	if (judge())
	{
		printf ("-1\n");
		return 0;
	}
	for (int i = 1; i <= n && flag; ++i)
	{
		if (!vis[i])
			dfs (i);
	}
	return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define se set<ll>
#define vec vector<ll>
#define inf 10000000000000000
bool mark[100005];
vec adj[100005];
ll counter;
vec cnt;
vector<string> forsubs;
ll b;
ll a;
ll ans=1000000000000;
ll n;


int main()
{    
 

	#ifdef APNA_IO
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
		    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 


ll n,x;
cin>>n>>x;
ll l[n+1];

for(ll i=1;i<=n;i++)
	{
		cin>>l[i];
	}


ll d[n+2];
d[1]=0;	

for(ll i=2;i<=n+1;i++)
	{
		d[i]=d[i-1]+l[i-1];

	if(d[i]==x)
		{
			ans=i;
			break;
		}
		if(d[i]>x)
		{
			ans=i-1;
			break;
		}
	}

	if(d[n+1]<x)
		ans=n+1;

	/*for(ll i=1;i<=n;i++)
	{
		cout<<l[i]<<" "<<d[i]<<endl;
	}*/

	cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000;
long long primal_dual(vector<map<int, pair<long long, int>>> &E, int s, int t, long long F){
	int V = E.size();
	for (int i = 0; i < V; i++){
		for (auto edge : E[i]){
			if (!E[edge.first].count(i)){
				E[edge.first][i] = make_pair(0, -edge.second.second);
			}
		}
	}
	long long ans = 0;
	vector<long long> h(V, 0);
	while (F > 0){
		vector<long long> d(V, INF);
		vector<long long> m(V, INF);
		vector<int> prev(V, -1);
		d[s] = 0;
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
		Q.push(make_pair(0, s));
		while (!Q.empty()){
			long long c = Q.top().first;
			int v = Q.top().second;
			Q.pop();
			if(d[v] >= c){
				for (auto P : E[v]){
					int w = P.first;
					long long cap = P.second.first;
					int cost = P.second.second;
					if (cap > 0 && d[w] > d[v] + cost + h[v] - h[w]){
						d[w] = d[v] + cost + h[v] - h[w];
						prev[w] = v;
						m[w] = min(m[v], cap);
						Q.push(make_pair(d[w], w));
					}
				}
			}
		}
		if (d[t] == INF){
			return -1;
		}
		for (int i = 0; i < V; i++){
			h[i] += d[i];
		}
		int f = min(m[t], F);
		int c = t;
		while (c != s){
			E[prev[c]][c].first -= f;
			E[c][prev[c]].first += f;
			c = prev[c];
		}
		F -= f;
		ans += f * h[t];
	}
	return ans;
}
int main(){
  int N, M, F;
  cin >> N >> M >> F;
  vector<map<int, pair<long long , int>>> E(N);
  for (int i = 0; i < M; i++){
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    E[u][v] = make_pair(c, d);
  }
  cout << primal_dual(E, 0, N - 1, F) << endl;
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int dp[100010];

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	vector<int> h(n); {
		rep(i, n) cin >> h[i];
	}

	rep(i, 100010) dp[i] = INF;
	dp[0] = 0;

	rep(i, n) rep(k, 2) {
		int j = i + k + 1;
		int cost = abs(h[i] - h[j]);
		// printf("cost %d\n", dp[i] + co.st);
		dp[j] = min(dp[i] + cost, dp[j]);
	}

	printf("%d\n", dp[n - 1]);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main(){
ll i,j,n,no;
cin>>n;
for(i=n;i>0;i--){
	no=abs(sqrt(i));
	//cout<<no-sqrt(i)<<endl;
	if(no-sqrt(i)==0)
	break;
}
cout<<i<<endl;

return 0;}



Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d",$n);
fscanf(STDIN, "%d",$a);
fscanf(STDIN, "%d",$b);
fscanf(STDIN, "%d",$c);
fscanf(STDIN, "%d",$d);
fscanf(STDIN, "%d",$e);
$min=min($a,$b,$c,$d,$e);
printf("%d", ceil($n / $min) + 4);

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

int main(){
  int a;
  cin>>a;
  int ans=0;
  if(a<10)ans=a;
  else if(a<100)ans=9;
  else if(a<1000)ans=9+a-99;
  else if(a<10000)ans=909;
  else if(a<100000)ans=909+a-9999;
  else ans=90909;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8
N, K, S = map(int, input().split())
if S != 10**9:
    ans = []
    for i in range(N):
        if i < K:
            ans.append(S)
        else:
            ans.append(S+1)
else:
    ans = []
    for i in range(N):
        if i < K:
            ans.append(S)
        else:
            ans.append(1)
print(*ans)

Measured memory_bytes: 9580
#include <bits/stdc++.h>
using namespace std;
 
/*** Template Begins ***/
 
typedef long long   ll;
typedef pair<ll,ll> pll;
typedef long double ld; 
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb           push_back
#define F            first
#define S            second
#define ios          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define hell   1000000007LL
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p){ ll res = 1;x = x % p;while (y > 0) {if (y & 1) res = (res*x) % p;y = y>>1;
  x = (x*x) % p;} return res;} 

const long double PI = acos(-1);
// Debug //
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
ll euclid(ll x,ll y,ll a,ll b){
  return (a-x)*(a-x)+(b-y)*(b-y);
}
void solve()
{
  vector<ll> v(5);
  ll i;
  rep(i,0,5)
    cin>>v[i];
  // sort(all(v));
  rep(i,0,5)
  {
    if(!v[i])
    {
      cout<<i+1;
      return;
    }
  }
}
int main()
{ 
  ios;
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  ll t=1,i=1;
  // cin>>t;
  while(i<=t)
  {
    solve();
    i++;
  }
  return 0;
}


Measured memory_bytes: 3640
/*  -*- coding: utf-8 -*-
 *
 * 2798.cc: Taking a Seat
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 100;
const int MAX_W = 100;

const int dxs[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
const int dys[] = { 0, -1, -1, -1, 0, 1, 1, 1 };

/* typedef */

/* global variables */

char flds[MAX_H][MAX_W + 4];

/* subroutines */

/* main */

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

  for (int y = 0; y < h; y++) scanf("%s", flds[y]);

  int cnt = 0;
  for (int y = 1; y < h; y++)
    for (int x = 0; x < w; x++)
      if (flds[y][x] == '-') {
	bool ok = true;
	if ((x > 0 && flds[y][x - 1] != '-') ||
	    (x < w - 1 && flds[y][x + 1] != '-')) ok = false;
	for (int di = 0; ok && di < 8; di++) {
	  int vx = x + dxs[di], vy = y + dys[di];
	  if (vx >= 0 && vx < w && vy >= 0 && vy < h &&
	      flds[vy][vx] == 'x') ok = false;
	}

	if (ok) cnt++;
      }

  printf("%d\n", cnt);
  return 0;
}



Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0};
const int dy[]={0,1};
const int mod=1e9+7;
int n,m;
char c[1005][1005];
int f[1005][1005];
bool ok(int nx,int ny){
	return nx>=0&&nx<n&&ny>=0&&ny<m&&c[nx][ny]!='#';
}
int DFS(int x,int y){
	if(f[x][y]!=-1){
		return f[x][y];
	}
	if(x==n-1&&y==m-1){
		return f[x][y]=1;
	}
	f[x][y]=0;
	for(int i=0;i<2;++i){
		int nx=x+dx[i],ny=y+dy[i];
		if(ok(nx,ny)){
			f[x][y]=(f[x][y]+DFS(nx,ny))%mod;
		}
	}
	return f[x][y];
}
int main(){
	memset(f,-1,sizeof(f));
	cin>>n>>m;
	for(int i=0;i<n;++i){
		cin>>c[i];
	}
	cout<<DFS(0,0)<<'\n';
	return 0;
} 

Measured memory_bytes: 5376
#include<cstdio>
typedef long long ll;
const int mod=998244353;
int N,M;
ll fac[1<<20],ifac[1<<20];
ll inv(int a,int p=mod){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
ll C(int n,int m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
	scanf("%d%d",&N,&M);
	for(int i=*fac=1;i<=N+M;i++)fac[i]=fac[i-1]*i%mod;
	ifac[N+M]=inv(fac[N+M]);
	for(int i=N+M;i;i--)ifac[i-1]=ifac[i]*i%mod;
	int ans=C(N+M,N)*(N>M?N:M)%mod;
	for(int x=1;x<=N&&x<=M;x++)ans=(ans+C(x*2-1,x)*C(N+M-x*2,N-x))%mod;
	ans=ans*inv(C(N+M,N))%mod;
	printf("%d\n",ans);
}

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

int main(){
	ll n,k;
	cin >> n >> k;
	ll h[n];
	for(ll i=0;i<n;i++)
		cin >> h[i];

	ll dp[n];
	fill(dp,dp+n,INT_MAX);
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(ll i=2;i<n;i++){
		ll j;
		if(i<k)
			j = i;
		else
			j = k;
		while(j>0){
			dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
			j--;
		}
		//cout << dp[i] << " ";
	}	
	//cout << endl;
	cout << dp[n-1];
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1000000007;
ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

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

    if(N%2 == 0){
        for(int i=1; i<=N-1; i+=2) if(a[i] != 2){
            cout << 0 << endl;
            return 0;
        }
    } else {
        if(a[0] != 1){
            cout << 0 << endl;
            return 0;
        }

        for(int i=2; i<=N-1; i+=2) if(a[i] != 2){
            cout << 0 << endl;
            return 0;
        }
    }

    cout << modpow(2, N/2) << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int K = Integer.parseInt(scan.next()); 
        int X = Integer.parseInt(scan.next()); 
        scan.close();

        String result = "";
        for (int i = X - K + 1; i < X + K; i++) {
            result += String.valueOf(i) + " ";
        }

        System.out.println(result);
    }
}

Measured memory_bytes: 22612
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int N = s.length;
		
		for(int i=1; i<=N; i++) {
			HashSet<Character> set = new HashSet<>();
			for(int j=0; j<=N-i; j++) {
				HashSet<Character> next = new HashSet<>();
				for(int k=0; k<i; k++) {
					if(j==0 || set.contains(s[j+k]))
						next.add(s[j+k]);
				}
				set = next;
			}
			if(!set.isEmpty()) {
				System.out.println(i-1);
				break;
			}
		}
		
		sc.close();
	}
}


Measured memory_bytes: 21844
#!/usr/bin/env python3
#ABC144 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a,b,x = LI()

if x > b*a*a/2:
    c = 2*x/a**2 - b
    print(math.degrees(math.atan2(b-c,a)))
else:
    c = 2*x/a/b
    print(math.degrees(math.atan2(b,c)))


Measured memory_bytes: 38256
//xtwakioi! xtwddYnoi(双重含义)!
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=110;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
int n;
string s[N],ot;
signed main()
{
    cin>>n;
    for(ri int i=1;i<=n;i++) cin>>s[i];
    for(ri char i='a';i<='z';i++)
    {
        int qwq=1;
        for(ri int j=1;j<=n;j++) if(s[j].find(i)==-1) { qwq=0; break; }
        if(!qwq) continue;
        int pp=1e18;
        for(ri int j=1;j<=n;j++)
        {
            int cnt=0;
            for(ri int k=0;k<(int)s[j].size();k++)
                cnt+=(s[j][k]==i);
            pp=min(pp,cnt);
        }
        for(ri int j=1;j<=pp;j++) ot+=i;
    }
    cout<<ot<<endl;
    return 0;
}

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

int main() {
  vector<int> a(5);
  vector<int> b(5);
  int s,t  = 0,ans = 0;
  rep(i,5) { 
    cin >> a.at(i);
    b.at(i) = (a.at(i)+9)/10*10;
    ans += b.at(i);
    int d = b.at(i) - a.at(i);
    if(d  > t) {
      t = d;
      s = i;
    }
  }
  ans -= b.at(s) - a.at(s);
  cout << ans << endl;
}
  


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

if N%2==0:
    print(N,N,int(N/2))
    quit()

for i in range(1,3501):
    for j in range(1,3501):
        if(4*i*j-N*(i+j)<=0):continue
        n=N*i*j/(4*i*j-N*(i+j))
        if(n==int(n)):
            print(i,j,int(n))
            quit()


quit()

Measured memory_bytes: 3064
// 解説を見た
//
// 解説でわからなかったのが、
// 直前の文字が "3 2 7 2"で、つぎ3がくると"5 7 5"が完成してしまうのを
// どうやって検知するかということ。
// 検知には、右から5, 12, 17番目のビットを見ればよい。
//
// 例えば、10010100000010 に 100 を結合すると、
// 10010100000010100。これの右から5, 12, 17番目は1なので
// 575が完成してしまっていることがわかる

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

ll dp[41][300000];
ll MOD = ll(1e9) + 7;

string bin(ll i) {
    string ret;
    while(i) {
        ret += '0' + (i % 2);
        i /= 2;
    }
    reverse(ALL(ret));
    return ret;
}

int main(void)
{
    cin.sync_with_stdio(false);
    ll N, X, Y, Z;
    cin >> N >> X >> Y >> Z;

    auto MAX_DIGIT = 10;
    auto MAX = X + Y + Z;
    dp[0][0] = 1;
    FOR(n, 1, N + 1) {
        REP(i, 1 << (MAX + 1)) {
            FOR(j, 1, MAX_DIGIT + 1) {
                auto next_i = i << j;
                next_i |= (1 << (j - 1));
                if ((next_i & (1 << (X + Y + Z - 1)))
                    && (next_i & (1 << (Y + Z - 1)))
                    && (next_i & (1 << (Z - 1)))) {
                    
                    //if (n == 4 && dp[n - 1][i]) {
                    //    cout << bin(next_i) << " " << dp[n - 1][i] << endl;
                    //}

                    continue;
                }
                next_i &= ((1 << (MAX + 1)) - 1);
                dp[n][next_i] += dp[n - 1][i];
                dp[n][next_i] %= MOD;
            }
        }
    }



    ll ans1 = 0;
    REP(i, 1 << (MAX + 1)) {
        ans1 += dp[N][i];
        ans1 %= MOD;
    }

    ll ans2 = 1;
    REP(i, N) {
        ans2 *= MAX_DIGIT;
        ans2 %= MOD;
    }

    ll ans = ((ans2 - ans1) + MOD) % MOD;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 94080
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i,n) cin >> a[i];
    vector<int> b;
    int cnt = 0;
    rep(i,n) {
        if(a[i] == 1 && i < n-1) cnt++;
        else {
            if(a[i] == 1) cnt++;
            b.push_back(cnt);
            cnt = 0;
        }
    }
    if((int)b.size() == 0) b.push_back(n);
    sort(b.rbegin(),b.rend());
    int ans = b.at(0) + 1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String s = scan.next();
        char[] x1 = s.toCharArray();
        Arrays.sort(x1);
        String s1 = String.valueOf(x1);
        String t = scan.next();
        char[] x2 = t.toCharArray();
        Arrays.sort(x2);
        String t2 = new StringBuilder().append(x2).reverse().toString();
        if (s1.compareTo(t2) < 0 ) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=6e5+10,inf=0x3f3f3f3f,mod=998244353;
struct Segment_tree{
	int Min[maxn<<2];
	void update(int x,int L,int R,int ql,int qr,int v){
		if(ql<=L && R<=qr){
			chkmax(Min[x],v);
			return;
		}
		int Mid=(L+R)>>1;
		if(ql<=Mid) update(x<<1,L,Mid,ql,qr,v);
		if(qr>Mid) update(x<<1|1,Mid+1,R,ql,qr,v);
	}
	int query(int x,int L,int R,int q){
		if(L==R) return Min[x];
		int Mid=(L+R)>>1,res=Min[x];
		if(q<=Mid) chkmax(res,query(x<<1,L,Mid,q));
		else chkmax(res,query(x<<1|1,Mid+1,R,q));
		return res;
	}
}Seg;
int n,a[maxn<<1],sum[maxn],Max[maxn];
struct szsz{
	int c[maxn];
	inline int lowbit(int x){
		return x&(-x);
	}
	int sum(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
	void add(int x,int y){
		while(x<=n){
			c[x]+=y;
			x+=lowbit(x);
		}
	}
	int query(int l,int r){
		if(l<=0) l+=n;
		if(r>n) r-=n;
		if(l<=r) return sum(r)-sum(l-1);
		return sum(r)+sum(n)-sum(l-1);
	}
}bit;
int l[maxn],r[maxn],tmp;
int L[maxn],R[maxn];
vector<int> ve[maxn];
int main(){
	n=read();
	REP(i,1,n) a[i]=read(),sum[a[i]]++,a[i+n]=a[i];
	int Nw=1,lst=1;
	REP(i,2,n<<1|1)
		if(a[i]!=a[i-1]) l[++tmp]=lst,r[tmp]=i-1,chkmax(Max[a[i-1]],Nw),Nw=1,lst=i;
		else ++Nw;
	REP(i,1,n) if(Max[i]<sum[i]) return printf("0\n"),0;
	if(sum[1]==0) return printf("0\n"),0;
	int Times=sum[1]-1;
	if(Times==n-1){
		int fac=1;
		REP(i,1,n) fac=(ll)fac*i%mod;
		return printf("%d\n",fac),0;
	}
	REP(i,2,tmp){
		if(r[i]-Times>l[i]) return printf("0\n"),0;
		L[a[r[i]]]=r[i]-Times,R[a[r[i]]]=l[i];
		int u=l[i]-Times,v=r[i];
//		cerr<<u<<' '<<v<<endl;
		if(v-u+1>=n) Seg.update(1,1,n,1,n,a[r[i]]);
		if(v>n) v-=n;
		if(u<=0) u+=n;
		if(u<=v) Seg.update(1,1,n,u,v,a[r[i]]);
		else Seg.update(1,1,n,u,n,a[r[i]]),Seg.update(1,1,n,1,v,a[r[i]]);
		if(r[i]>n) break;
	}
	REP(i,1,n) ve[Seg.query(1,1,n,i)].push_back(i);
	int ans=1;
	REP(i,1,n){
		for(auto v:ve[i]) bit.add(v,1);
//		cerr<<i<<' '<<L[i]<<' '<<R[i]<<endl;
		if(R[i]){
			int u=bit.query(L[i],R[i]);
			if(u==0) return printf("0\n"),0;
			ans=(ll)ans*u%mod;
		}
		else{
			int u=bit.sum(n);
			if(u<i) return printf("0\n"),0;
			ans=(ll)ans*(u-(i-1))%mod;
		}
	}
	assert(bit.sum(n)==n);
	printf("%d\n",ans);
	return 0;
}


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

typedef long long ll;
const ll INF = 1LL << 60;

inline bool chmin(ll& a, ll b) { if (a > b) { a = b; return true; } return false; }
inline bool chmax(ll& a, ll b) { if (a < b) { a = b; return true; } return false; }

int N;
vector<vector<ll>> happiness;
vector<vector<ll>> sum;

int main() {

  cin >> N;
  happiness = vector<vector<ll>>(N+10,vector<ll>(3, 0));
  sum = vector<vector<ll>>(N+10,vector<ll>(3,0));

  for (ll i=0; i<N; i++){
    for (ll j=0; j<3; j++){
      cin >> happiness.at(i).at(j);
    }
  }

  for (ll i=0; i<N; i++){
    for (ll j=0; j<3; j++){
      for (ll k=0; k<3; k++){
        if (j==k) continue;
        chmax(sum.at(i+1).at(k), sum.at(i).at(j)+happiness.at(i).at(k));
      }
    }
  }
  ll ans = 0;
  for (int j=0; j<3; j++) {
    chmax(ans, sum.at(N).at(j));
  }
  cout << ans << endl;
}

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

#define int long long

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

int c[3][3];
signed main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[i][j];
        }
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 0; k <= 100; k++) {
                int b1 = c[0][0] - i, b2 = c[0][1] - i, b3 = c[0][2] - i;
                if (b1 < 0 || b2 < 0 || b3 < 0) {
                    continue;
                }
                if (j + b1 == c[1][0] && k + b1 == c[2][0] &&
                    j + b2 == c[1][1] && k + b2 == c[2][1] &&
                    j + b3 == c[1][2] && k + b3 == c[2][2]) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
	return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
	assert(__gcd(a, m) == 1);
	ll m0 = m;
	ll y = 0, x = 1;

	if (m == 1)
		return 0;

	while (a > 1)
	{
		ll q = a / m;
		ll t = m;

		m = a % m, a = t;
		t = y;

		y = x - q * y;
		x = t;
	}

	if (x < 0)
		x += m0;

	return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
	if (y == 0)
		return 1LL;
	else if (y == 1)
		return x;
	else
	{
		ll ans = modPow(x, y / 2, m) % m;
		if (y & 1)
		{
			return (((ans * ans) % m) * x) % m;
		}
		else
		{
			return (ans * ans) % m;
		}
	}
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	VII num(n,-1);
	bool win=true;
	while(m--)
	{
		int g,v;
		cin>>g>>v;
		g--;
		if(num[g]==-1)
		num[g]=v;
		else if(num[g]!=v)
		win=false;
		
	}
	//cout<<win<<endl;
	if(num[0]==0 && n!=1)win=false;
	else if(num[0]==-1){
		if(n==1)
		num[0]=0;
		else
		num[0]=1;
	}
	for(int i=1;i<n;++i)
	if(num[i]==-1)num[i]=0;

	if(win)
	{
		for(auto x:num)cout<<x;
	}
	else cout<<-1;

	return 0;
}

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> t(n + 1), x(n + 1), y(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> t[i] >> x[i] >> y[i];
    }
    for(int i = 1; i <= n; i++){
        int dt, dd;
        dt = t[i] - t[i - 1];
        dd = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
        if(dd > dt || dd % 2 != dt % 2){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1408
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

int main() {
	IOS();
	ll n, k;
	string s;
	cin >> n >> k >> s;
	bool is0 = false;
	vector<ll> sum(n + 1);
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') {
			sum[i + 1] = sum[i];
			is0		   = false;
		} else {
			if (!is0) {
				sum[i + 1] = sum[i] + 1;
			} else {

				sum[i + 1] = sum[i];
			}

			is0 = true;
		}
		//dump(sum[i + 1]);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i - 1] == '1') {
			ll leng = upper_bound(sum.begin(), sum.end(), max(sum[i] + k, 0ll)) - sum.begin();
			leng	= leng - i;
			ans		= max(ans, leng);
		} else {
			ll leng = upper_bound(sum.begin(), sum.end(), max(sum[i] + k - 1, 0ll)) - sum.begin();
			leng	= leng - i;
			//dump(leng);
			ans = max(ans, leng);
		}
		//dump(ans);
	}
	dump(ans);
	return 0;
}

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

using namespace std;
typedef long long ll;

const ll LIMIT = 1000000000000000000;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    sort(a.begin(), a.end());
    if (a[0] == 0)cout << 0 << endl;
    else {
        ll ret = 1;
        for (int i = 0; i < n; i++) {
            if (ret > LIMIT / a[i] + 1) ret = -1;
            if (ret > 0)ret *= a[i];
        }
        cout << (ret > LIMIT ? -1 : ret) << endl;
    }
    return 0;
}

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

using namespace std;

int main(void) {
  map<string, int> mp;
  string s, max_len = "";
  while (cin >> s) {
    mp[s]++;
    if (s.size() > max_len.size()) {
      max_len = s;
    }
  }

  string max_cnt = "";
  for (auto i : mp) {
    if (i.second > mp[max_cnt]) {
      max_cnt = i.first;
    }
  }

  cout << max_cnt << " " << max_len << endl;

  return 0;
}


Measured memory_bytes: 3052
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll MOD = 1000000007;
const ll INF = 10000000000000;
#define all(v) v.begin(), v.end()


int main(){
  ll K,S,ans=0;
  cin >> K >> S;
  rep(i,K+1){
    rep(j,K+1){
      if(S-i-j<=K&&S-i-j>=0){
        ans++;
      }
    }
  }
  cout << ans << endl;
}
  

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

using namespace std;

typedef long long ll;

const ll INF = 1e12;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<ll> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];

	ll ans = INF;
	for (int i = 0; i < (1 << N); i++) {
		vector<bool> used(N, false);
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) used[j] = true;
		}

		ll pre = 0;
		int cnt = 0;
		ll tmp = 0;
		for (int j = 0; j < N; j++) {
			if (used[j]) {
				pre++;
				pre = max(pre, a[j]);
				tmp += pre - a[j];
				cnt++;
			} else {
				cnt += (pre < a[j]);
				pre = max(pre, a[j]);
			}
		}
		if (cnt >= K) ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    string s;
    int n;
    cin>>n>>s;
    for(int i=0;i<s.length();i++){
        char ch=s[i];
        if(ch >= 'A' && ch <= 'Z'){
			ch = ch + n;
			
			if(ch > 'Z'){
				ch = ch - 'Z' + 'A' - 1;
			}
			
			s[i] = ch;
        }
    }
    cout<<s;
	return 0;
}


Measured memory_bytes: 256