akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <string>
#include <set>

using namespace std;
typedef long long ll;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    vector<ll> arr(n),suff(n);
    for(int i = 0; i < n; ++i) cin >> arr[i];
    ll sum = 0;
    for(int i = n-1; i >= 0; --i) {
        sum += arr[i];
        suff[i] = sum;
    }
    

    ll ans = 0;
    for(int i = 0; i < n-1; ++i){
        ans += (arr[i]*suff[i+1]);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main (void){
	int r,g,b,n;
	while(scanf("%d%d%d",&r,&g,&b)!=EOF){
		n=r*100 + g*10 +b;
		if(n%4==0){
			printf("YES");}
		else printf("NO");
	}
	return 0;
}


Measured memory_bytes: 128
import java.util.*;

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

      String s=sc.next();

      char[] c = new char[4];
      for(int i=0;i<4;i++){
        c[i] = s.charAt(i);
      }

///////////////////////////////////////////////////////////
        if((c[0]==c[1]) || (c[1]==c[2]) || (c[2]==c[3])){
          System.out.println("Bad");
        }
        else{
          System.out.println("Good");
        }
///////////////////////////////////////////////////////////



    }
}


Measured memory_bytes: 21844
N, K = map(int, input().split())
ans = 0
for b in range(K+1, N+1):
    k = b-K
    n = int((N+1)/b)
    ans += k*n
    k2 = N%b
    if k2 >= K and (k2+1)%b != 0:
        ans += k2-K+1
if K == 0:
    ans -= N
print(ans)

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

    set<string> st;
    string now = "";
    rep(i, 50){
        cout << "?";
        if(i < 25){
            now.push_back('a');
            now.push_back('a' + i);
        }else{
            now.push_back('b');
            now.push_back('a' + i - 25);
        }
        now.push_back('a');
        cout << now << endl;
        string res;
        cin >> res;
        if(res[0] != 'a' || st.count(res)){
            cout << "!OUT" << endl;
            break;
        }
        st.insert(res);
        now.clear();
        now.push_back(res.back());
    }

    return 0;
}


Measured memory_bytes: 3268
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
typedef long long LL;
const LL mod = 1e9 + 7;
// head
const int maxn = 2e5 + 5;
int s[maxn], top, n;
char ch[maxn];

int main() {
	cin>>ch;
	n = strlen(ch);
	rep(i, 0, n - 1) {
		if(ch[i] == 'S') s[++top] = 0;
		else {
			if(s[top] == 0 && top) top--;
			else s[++top] = 1;
		}
	}
	cout<<top<<endl;
}

Measured memory_bytes: 4428
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if a%3 == 0 || b%3 == 0 || (a+b)%3 == 0 {
		fmt.Println("Possible")
		return
	}
	fmt.Println("Impossible")
}


Measured memory_bytes: 512
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}
#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
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

ll a,b;
char ch;

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

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> ch >> b;
    if(ch=='+') cout << a+b;
    else cout << a-b;
    return 0;
}
/* The judge is never wrong! Your code is buggy 
   Look for:
 * * Read the problem carefully.
 * * Don't forget to sort(), mod, ll!!!!
 * * Initial value = +/- infinity instead of zero!!!
 * * an easier and alternate approach
 * * read the problem statement carefully
 * * if concept is correct and still WA, try with a different implementation
 * * special cases (n=1?)
 * * if you have no idea just guess the appropriate well-known algorithm instead of doing nothing :/
 */

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;
const int MAX_N=1e5;

// Binary indexed Tree (Fenwick Tree)
template <typename T>
struct BIT {
    int n,p;
    vector<T> d;
    BIT(int n=0) :n(n), d(n+1) {
        p = 1;
        while(p < n)p *= 2;
    }
    //更新
    void add(int i,T x=1){
        for(i++;i <= n;i += i&-i) d[i] += x;
    }
    //[0,i)の和
    T sum(int i){
        T res = 0;
        for(;i;i -= i&-i) res += d[i];
        return res;
    }
    //[l,r)の和
    T sum(int l,int r){ return sum(r) - sum(l);}
    //v0+v1+…vx>=mを満たすmin(x)を返す
    int lower_bound(T w){
        if(w <= 0) return 0;
        T x = 0;
        for ( int i=p;i;i/=2){
            if(i+x <=n &&d[i+x] < w){
                w -= d[i+x];
                x += i;
            }
        }
        return x;
    }
};

signed main(){
    int n,k;cin>>n>>k;
    vector<int>a(n);
    REP(i,n)cin>>a[i];
    int sum[n+1];
    map<int,int>atu;
    REP(i,n+1){
        if(i==0)sum[i]=0;
        else sum[i]=sum[i-1]+a[i-1]-k;
        atu[sum[i]]++;
    }
    map<int,int>cha;
    int i=0;
    for(auto v:atu){
        cha[v.first]=i;
        i++;
    }
    REP(i,n+1)sum[i]=cha[sum[i]];
    BIT<int> bit(2e5+1);
    int ans=0;
    RREP(i,n+1){
        ans += bit.sum(sum[i],2e5+1);
        bit.add(sum[i]);
    }
    cout<<ans;
}

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

int main() {
	int m = 0 , f = 0 , r = 0 , t = 0 , i = 0 ;
	char box[50] = {} ;
	for ( i = 0 ; i < 50 ; i++)
	{
		cin >> m >> f >> r ;
		t = m + f ;
		if ( t + r == -3 ) break ;
		if ( t >= 80 ) box[i] = 'A' ;
		if ( t >= 65 && t <80) box[i] = 'B' ;
		if ( t >=50 && t < 65 ) box[i] = 'C' ;
		if ( t >= 30 && t < 50 ) box[i] = 'D' ;
		if ( 30 <= t && t < 50 && m != -1 && f != -1 && r >= 50 ) box[i] = 'C' ;
		else if ( 30 <= t && t < 50 && m != -1 && f != -1 ) box[i] = 'D' ;
		if ( m == -1 || f == -1 || t < 30 ) box[i] = 'F' ;
	}
	for ( int n = 0 ; n < i ; n++  )
	{
		cout << box[n] << endl ;
	}
	return 0;
}



Measured memory_bytes: 3120
# from pprint import pprint
# import math
# import collections

x = int(input())
# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))
# a = []
# for i in range(n):
#     a.append(int(input()))


if x >= 30:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9140
#include<bits/stdc++.h>
#define ll long long
#define loop(n) for(ll i = 0; i<n; i++)
#define sort(a) sort(a.begin(), a.end())
using namespace std;

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

    ll n, x; cin>>n;
    map<ll, ll> m;
    for(int i = 0; i<n-1; i++){
        cin>>x;
        m[x]++;
    }
    for(int i = 1; i<=n; i++) cout<<m[i]<<"\n";
    return 0;
}

Measured memory_bytes: 16156
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    X,Y,Z = list(map(int,_in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(Z,X,Y)

Measured memory_bytes: 38640
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res



n, k = LI()
A  = IR(n)
A = [0] + list(accumulate([a - k for a in A]))
D  = {v:i for i,v in enumerate(sorted(A))}
bit = BIT(len(A))
c = 0
for a in A:
    c += bit.sum(D[a])
    bit.add(D[a], 1)

print(c)






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

typedef long long LL;
const int MOD = 1e9+7;
const int maxN = 1e5+5;
LL P10[maxN], F[maxN][13];
int N;
string S;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> S;
    N = S.size();
    P10[0] = 1;
    for (int i=1; i<=N; i++) P10[i] = (10*P10[i-1])%13;
    S = '.'+S;
    vector<int> digits;
    for (int i=0; i<=N+1; i++)
        for (int k=0; k<13; k++) F[i][k] = 0;
    F[N+1][0] = 1;
    for (int i=N; i>0; i--) {
        digits.clear();
        if (S[i]!='?') digits.push_back(int(S[i]-'0'));
        else for (int d=0; d<=9; d++) digits.push_back(d);
        for (int j=0; j<digits.size(); j++) {
            int d = digits[j];
            int p = (d*P10[N-i])%13;
            for (int k=0; k<13; k++)
                F[i][(p+k)%13] += F[i+1][k],
                F[i][(p+k)%13] %= MOD;
        }
    }
    cout << F[1][5];
}


Measured memory_bytes: 11372
def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A
    
if __name__ == '__main__':
    H, N = InputToInt()
    A = InputToInt()
    if sum(A) >= H:
        print('Yes')
    else:
        print('No')


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/11  Problem: ABC 086 C / Link: http://abc086.contest.atcoder.jp/tasks/abc086_c  ----- */


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

	LL N;
	cin >> N;
	VL t(N + 1), x(N + 1), y(N + 1);
	FOR(i, 1, N+1) {
		cin >> t[i] >> x[i] >> y[i];
	}

	LL ans = 1;
	FOR(i, 0, N) {
		LL T = t[i + 1] - t[i];
		LL dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		ans &= (T % 2 == dist % 2 && T >= dist);
	}

	cout << (ans ? "Yes" : "No") << "\n";

	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
using namespace std;
int yg(int a,int b){
 int tmp;
 if(a<b){
  tmp=a;
  a=b;
  b=tmp;
}
 int r=a%b;
 while(r!=0){
  a=b;
  b=r;
  r=a%b;
}
 return b;
}
  int v[110000];
int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;++i){
    cin >> v[i];
    }
  for(int i=0;i<n-1;++i){
    v[i+1] = yg(v[i],v[i+1]);
    }
   cout << v[n-1] << endl;
}

Measured memory_bytes: 640
import collections

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

T=sum(A)
D=collections.Counter(A)

for i in range(Q):
  b,c=map(int,input().split())
  if b in D:
    if c in D:
      D[c]+=D[b]
    else:
      D[c]=D[b]
    T+=(c-b)*D[b]
    D[b]=0
  print(T)


Measured memory_bytes: 21240
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;

int main()
{
    int a,b;
    cin>>a>>b;
    int ans=max(a-2*b,0);
    cout<<ans<<endl;    
}


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

vector<long long> divisor(long long n) {
    vector<long long> v;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            if (i * i != n) {
                v.push_back(n / i);
            }
        }
    }
    return v;
}

int main() {
    long long n;
    cin >> n;

    long long t = 0;
    vector<long long> v = divisor(n);
    for (long long x : v) {
        if (x != 1 && n / (x - 1) == n % (x - 1)) {
            t += x - 1;
        }
    }
    cout << t << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include<string>
using namespace std;
int a[100000];
int main(void){
    int i,n,t,min=0,max=0,p=0,m=1;
    cin>>n>>t;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=n-1;i>=0;i--){
        if(a[i]>max){
            max=a[i];
            min=max;
        }
        if(a[i]<min){
            min=a[i];
            if(p<max-min){
                p=max-min;
                m=1;
            }else{
                if(p==max-min)m++;
                //if(t<m)m=t;
            }
        }
        //cout<<min<<max<<p<<m<<endl;
    }
    cout<<m;
}


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

int main(){
    list<int> l;
    
    int n, m, q;
    cin >> n >> m >> q;

    for(int i = 0; i < n; i++)  l.push_back(i);

    auto it = l.begin();

    int a;
    for(int i = 0; i < m; i++){
        cin >> a;
        if(a%2 == 0){
            while(a-- > 0){
                it++;
                if(it == l.end())   it = l.begin();
            }
            it = l.erase(it);
            if(it == l.end())   it = l.begin();
        }else{
            while(a-- > 0){
                if(it == l.begin()) it = l.end();
                it--;
            }
            it = l.erase(it);
            if(it == l.end())   it = l.begin();
        }
    }

    for(int i = 0; i < q; i++){
        cin >> a;
        auto x = lower_bound(l.begin(), l.end(), a);
        cout << (x != l.end() && *x == a) << endl;
    }

    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

#define INF 1000000001
#define MOD 998244353
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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

  vector<int>A;
  for(int i=0;i<N;i++){
    for(int j=0;j<a[i];j++){
      A.push_back(i+1);
    }
  }
  vector<vector<int>>ans(W,vector<int>(H));
  for(int y=0;y<H;y++){
    if(y%2){
      for(int x=W-1;x>=0;x--){
        ans[x][y]=A[y*W+W-1-x];
      }
    }
    else{
      for(int x=0;x<W;x++){
        ans[x][y]=A[y*W+x];
      }
    }
  }

  for(int y=0;y<H;y++){
    for(int x=0;x<W;x++){
      cout<<ans[x][y]<<" ";
    }
    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <string>

char BIG_small(char a) {
	switch (a) {
	case 'a':
		a = 'A';
		break;
	case 'A':
		a = 'a';
		break;
	case 'b':
		a = 'B';
		break;
	case 'B':
		a = 'b';
		break;
	case 'c':
		a = 'C';
		break;
	case 'C':
		a = 'c';
		break;
	case 'd':
		a = 'D';
		break;
	case 'D':
		a = 'd';
		break;
	case 'e':
		a = 'E';
		break;
	case 'E':
		a = 'e';
		break;
	case 'f':
		a = 'F';
		break;
	case 'F':
		a = 'f';
		break;
	case 'g':
		a = 'G';
		break;
	case 'G':
		a = 'g';
		break;
	case 'h':
		a = 'H';
		break;
	case 'H':
		a = 'h';
		break;
	case 'i':
		a = 'I';
		break;
	case 'I':
		a = 'i';
		break;
	case 'j':
		a = 'J';
		break;
	case 'J':
		a = 'j';
		break;
	case 'k':
		a = 'K';
		break;
	case 'K':
		a = 'k';
		break;
	case 'l':
		a = 'L';
		break;
	case 'L':
		a = 'l';
		break;
	case 'm':
		a = 'M';
		break;
	case 'M':
		a = 'm';
		break;
	case 'n':
		a = 'N';
		break;
	case 'N':
		a = 'n';
		break;
	case 'o':
		a = 'O';
		break;
	case 'O':
		a = 'o';
		break;
	case 'p':
		a = 'P';
		break;
	case 'P':
		a = 'p';
		break;
	case 'q':
		a = 'Q';
		break;
	case 'Q':
		a = 'q';
		break;
	case 'r':
		a = 'R';
		break;
	case 'R':
		a = 'r';
		break;
	case 's':
		a = 'S';
		break;
	case 'S':
		a = 's';
		break;
	case 't':
		a = 'T';
		break;
	case 'T':
		a = 't';
		break;
	case 'u':
		a = 'U';
		break;
	case 'U':
		a = 'u';
		break;
	case 'v':
		a = 'V';
		break;
	case 'V':
		a = 'v';
		break;
	case 'w':
		a = 'W';
		break;
	case 'W':
		a = 'w';
		break;
	case 'x':
		a = 'X';
		break;
	case 'X':
		a = 'x';
		break;
	case 'y':
		a = 'Y';
		break;
	case 'Y':
		a = 'y';
		break;
	case 'z':
		a = 'Z';
		break;
	case 'Z':
		a = 'z';
		break;
	}
	return a;
}

int main() {
	std::string str;
	getline(std::cin, str);

	for (std::string::iterator i = str.begin(); i != str.end(); ++i) {
		*i = BIG_small(*i);
	}

	std::cout << str << std::endl;

	return 0;
}

Measured memory_bytes: 3172
#include "bits/stdc++.h"

using namespace std;

void Main() {
    int K, X;
    cin >> K >> X;
    cout << (500 * K >= X ? "Yes" : "No") << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3528
//g++ -std=gnu++14 a.cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main() {
  string S;
  cin >> S;
  int l = S.size();
  bool hantei = false;
  rep(i,l){
    if(i%2 == 0){
      if(S.at(i) == 'R' || S.at(i) == 'U' || S.at(i) == 'D'){
        hantei = true;
        //cout << i <<endl;
      }
      else{
        hantei = false;
      }
    }
    else{
      if(S.at(i) == 'L' || S.at(i) == 'U' || S.at(i) == 'D'){
        hantei = true;
        //cout << i <<endl;
      }
      else{
        hantei = false;
      }
    }
    if(!hantei) break;
  }
  if(hantei){
    cout << "Yes" <<endl;
  }
  else{
    cout << "No" <<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
ll f(string s ){
    int n =s.length();
    ll res =0;
    ll sum =0;
    rep(i,n){
        if(s[i]=='+'){
            res+=sum;
            sum=0;
            continue;
        }
        if(sum==0)sum+=s[i]-'0';
        else {
            sum*=10;
            sum+=s[i]-'0';
        }
        //cout<<sum<<endl;
    }
    res+=sum;
    return res;
}
int main(){
    string s;cin>>s;
    int n =s.length();
    ll ans =0;
    rep(i,(1<<n-1)){
        string count;
        rep(j,n){
            count+=s[j];
            if(i&(1<<j)){
                count+="+";
            }
        }
        ans+=f(count);
        //cout<<ans<<endl;
    }
    
    cout<<ans<<endl;

}

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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
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;
}

void solve(long long N, long long X, std::vector<long long> L) {
  ll d = 0;
  ll ans = 1;
  for(int i = 0 ; i < N ; i++){
    d += L[i];
    if( d <= X ){
      ans++;
    }
  }
  cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long X;
  scanf("%lld", &X);
  std::vector<long long> L(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &L[i]);
  }
  solve(N, X, std::move(L));
  return 0;
}


Measured memory_bytes: 256
void main()
{
    long[] tmp = readln.split.to!(long[]);
    long n = tmp[0], x = tmp[1];
    long[] a = readln.split.to!(long[]);

    long cnt;
    foreach (i; 1 .. n)
    {
        long diff = a[i] + a[i-1] - x;
        if (diff > 0)
        {
            a[i] = max(0, a[i]-diff);
            cnt += diff;
        }
    }

    cnt.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 4220
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

ans = 1
palace = abs(T - H[0]*0.006 -A)
for i,h in enumerate(H):
    t = T - h*0.006
    if abs(A - t) <= palace:
        ans = i+1
        palace = abs(A-t)
        
print(ans)

Measured memory_bytes: 3064
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 1 << 30

int MOD = 1000000007;


int main(){
    std::ios_base::sync_with_stdio(false);

    int n; cin >> n;
    std::vector<ll> a(n); REP(i,n) cin >> a[i];
    ll ans = a[0]/2LL; a[0] %= 2LL;
    for(int i=0;i<n-1;i++){
        ans += a[i]/2LL; a[i] %= 2LL;
        if(a[i] == 1LL && a[i+1]>=1LL){
            ans++;
            a[i]=0LL;
            a[i+1]--;
        }
    }

    ans+=a[n-1]/2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100005;
int n,v;
int f[N];
int a[N];
int main()
{
	scanf("%d",&n);
	for (int u=1;u<=n;u++) scanf("%d",&a[u]);
	int ans=n;
	memset(f,0,sizeof(f));
	for (int u=1;u<=n;u+=2)	f[a[u]]++;
	int mx=0,mx1=0;
	int id=0;
	for (int u=1;u<=100000;u++)
	{
		if (f[u]>mx)	{mx1=mx;mx=f[u];id=u;}
		else if (f[u]>mx1) mx1=f[u];
	}
	memset(f,0,sizeof(f));
	for (int u=2;u<=n;u+=2)	f[a[u]]++;
	int Mx=0,Mx1=0;
	int Id=0;
	for (int u=1;u<=100000;u++)	
	{
		if (f[u]>Mx)	{Mx1=Mx;Mx=f[u];Id=u;}
		else if (f[u]>Mx1) 	Mx1=f[u];
	}
	if (id!=Id) ans=ans-mx-Mx;
	else ans=ans-max(mx+Mx1,Mx+mx1);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef unsigned long long int ullint;
std::string YesNo[] = {"No","Yes"};
#define loop(i,N) for(int i=0; i<(N); i++)
template<typename T>
auto sort_all(T& v) { return std::sort(v.begin(),v.end()); }
template<typename T>
auto sum_all(const T& v) { auto z = v[0]; z = 0;
    return std::accumulate(v.begin(),v.end(),z); }
template<typename T>
auto input(int N) {
    std::vector<T> v(N);
    loop(i,N) std::cin >> v[i];
    return std::move(v);
}

typedef llint Int;

int main(void)
{
    int N, K;
    cin >> N >> K;
    if (N % K == 0) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
// B - Roller Coaster
#include <bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<(n);++i)

int main(){
	int N,K; cin>>N>>K;
	int c = 0;
	rp(i, N){
		int h; cin>>h;
		if(h >= K) c++;
	}
	cout<< c <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define DEC(i, a, b) for (int i = (a); i > (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
typedef long long ll;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
const ll LINF = (int)1e18;
const double EPS = 1e-9;

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n,k;
  cin >> n >> k;

  int ans = 0;
  int ans_ = 0;
  vector<int> v;
  REP(i,n) {
    int a_;
    cin >> a_;
    for(auto e: v) {
      if (e > a_) ++ans_;
    }
    v.pb(a_);
  }
  ans += (ans_ * k) % MOD;

  if (k > 1) {
    int rec = 0;
    for (auto e: v) {
      for (auto f: v) {
        if (f > e) ++rec;
      }
    }

    if (k > 2) ans += rec * ((k-1)*(k)/2 %MOD) %MOD;
    else ans += rec %MOD;
  }
  ans %= MOD;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

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

  if (n[1] != n[2]) {
    cout << "No" << endl;
    return 0;
  }

  int count = 0;
  char base = n[0];
  for (int i = 1; i != n.size(); ++i) {
    if (n[i] == base) ++count;
    else {
      base = n[i];
    }
  }

  if (count >= 2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;


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

    vi v(9);
    v[0]=0;
    v[1]=399;
    v[2]=799;
    v[3]=1199;
    v[4]=1599;
    v[5]=1999;
    v[6]=2399;
    v[7]=2799;
    v[8]=3199;

    int n;
    cin>>n;
    vi a(n);
    vi co(9,0);
    rep(i,n)cin>>a[i];
    for(int i=0;i<n;i++){
        decltype(v)::iterator it=lower_bound(v.begin(),v.end(),a[i]);
        int pos = distance(v.begin(), it);
        pos--;
        co[pos]++;
        // cout<<"pos:"<<pos<<endl;
    }

    ll ans=0;
    for(int i=0;i<8;i++){
        if(co[i]>0){
            ans++;
            // cout<<"co["<<i<<endl;
        }
    }
    
    if(ans>0)cout<<ans<<" ";
    else cout<<"1 ";
    cout<<ans+co[8]<<endl;

//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<ll,ll>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,q,k,a,b,c;
ll min_cost[100010];
vector<P> g[100010];

int dijkstra(){
	pq<P, vector<P>, greater<P>> que;
	REP(i,0,n) min_cost[i]=LINF;
	que.emplace(0,k-1);
	min_cost[k-1]=0;

	while(!que.empty()){
		auto p=que.top(); que.pop();
		if(p.first>min_cost[p.second]) continue;

		for(auto e:g[p.second]){
			if(p.first+e.second>=min_cost[e.first]) continue;
			min_cost[e.first]=p.first+e.second;
			que.emplace(min_cost[e.first], e.first);
		}
	}

	return 0;
}

int main(){
	cin >> n;
	REP(i,0,n-1) cin >> a >> b >> c,g[a-1].push_back(P(b-1,c)),g[b-1].push_back(P(a-1,c));
	cin >> q >> k; dijkstra();
	REP(i,0,q){
		cin >> a >> b;
		cout << min_cost[a-1]+min_cost[b-1] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,m;
    scanf("%d",&n);
    scanf("%d",&m);
    int t;
    scanf("%d",&t);
    int i;
    if(n>m)
        i=n;
    else
        i=m;
    if(t%i==0)
        printf("%d",t/i);
    else
        printf("%d",t/i+1);

    return 0;
}


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

int main(void) {
  int n, m;
  cin >> n >> m;
  vector<int> x(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    x[--a]++;
    x[--b]++;
  }
  for (int i = 0; i < n; i++) {
    cout << x[i] << endl;
  }

  return 0;
}

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

 int main() {
string s;
   cin >> s;
 if(s == "SUN") {
  cout << 7;
  } else if(s == "MON") {
  cout << 6;
  } else if(s == "TUE") {
  cout <<5 ;} else if(s == "WED") {
  cout << 4;}else if(s == "THU") {
  cout << 3;}else if(s == "FRI") {
  cout << 2;}else if(s == "SAT") {
  cout << 1;}
  
 }


Measured memory_bytes: 3584
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <vector>
#include <queue>
#include <unordered_map> 
#include <iomanip>
#include <random>
#include <future>
#include <thread>
#include <utility>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF (INT_MAX/3)
#define PSB push_back
#define PN 1000000007
typedef long long LL;
//#define int long long


//booooooooooooost
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/multiprecision/cpp_dec_float.hpp>
//namespace mp = boost::multiprecision;	//多倍長整数(mp::cpp_int), 多倍長小数(mp::cpp_dec_float_100)



LL inv_mod(LL a, LL m)
{
	LL b, x, u, q, tmp;

	b = m; x = 1; u = 0;
	while (b > 0) {
		q = a / b;
		tmp = u; u = x - q * u; x = tmp;
		tmp = b; b = a - q * b; a = tmp;
	}

	return (x < 0) ? m + x : x;
}



signed main() {

	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a <= c && c <= b) ? "Yes" : "No") << endl;


	return 0;
}

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

int main(void) {
    i64 n, ans = 114514;
    cin >> n;
    vector<i64> w(n);
    for (i64 i = 0; i < n; i++) cin >> w[i];
    for (auto it = w.begin() + 1; it != w.end(); it++) {
        ans = min(ans, abs(accumulate(w.begin(), it, 0LL)
            - accumulate(it, w.end(), 0LL)));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 100005
#define eps 1e-8
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    	if(c == '-') f = -1;
    	c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 + c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    	out(x / 10);
    }
    putchar('0' + x % 10);
}
int64 X,Y;
int64 gcd(int64 a,int64 b) {
    return b == 0 ? a : gcd(b,a % b);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    read(X);read(Y);
    if(X % Y == 0) {puts("-1");return 0;}
    int64 t = Y / gcd(X,Y);
    out(X * (t - 1));enter;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>

using namespace std;

int main()
{
  int N;
  int K;
  vector<double> p;

  cin >> N >> K;
  p.resize(N);
  for (int i = 0; i < N; i++) {
    int input_p;
    cin >> input_p;
    p[i] = (input_p + 1) / 2.0;
  }

  double sum = 0;
  double sum_max = 0;
  for (int i = 0; i < p.size(); i++) {
    sum += p[i];
    if (i < K - 1) {
    }
    else {
      sum_max = max(sum_max, sum);
      sum -= p[i - (K - 1)];
    }
  }

  cout << fixed << setprecision(8)
       << sum_max << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
char res[16];
int N;
void gen(int n, char c) {
        if (n == N) {
                cout<<res<<'\n';
                return;
        }
        for(char i='a'; i<=c+1; ++i) {
                res[n] = i;
                gen(n+1, max(i,c));
        }
}
int main() {
        cin>>N;
        gen(0, 'a'-1);
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <queue>
#include <map>

#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;

int main()
{
	int N;
	cin >> N;
	map<int, int> a;
	rep(i, N) { int tmp; cin >> tmp; a[tmp]++; }
	int ma1 = 0, ma2 = 0;
	for (auto x : a) 
	{
		if (x.second >= 2)
		{
			if (x.first > ma1)
			{
				ma2 = ma1;
				ma1 = x.first;
			}
			else if (x.first > ma2)
			{
				ma2 = x.first;
			}
		}
	}
	if (a[ma1] >= 4)ma2 = ma1;
	ll ans = (ll)ma1 * (ll)ma2;
	co(ans);
	return 0;
}

Measured memory_bytes: 4992
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int a[300100];
int mi[300100],le[300100];
int rm[300100];
vector<int> num,len;
vector<pint> p;
vector<int> v;
vector<lint> zyo,rz;
lint mo=998244353;
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
lint calp(int a,int b){
	//cout<<a<<' '<<b<<endl;
	if(a<b) return 0;
	return (zyo[a]*rz[a-b])%mo;
}
int main()
{
	zyo.pb(1);rep(i,300200) zyo.pb((zyo[i]*(i+1))%mo);
	rep(i,300200) rz.pb(invMod(zyo[i],mo));
	
	int n;
	cin>>n;
	rep(i,n){
		cin>>a[i];a[i]--;
	}
	rep(i,n) mi[i]=n+10;
	rep(i,n) mi[a[i]]=min(mi[a[i]],i);
	rep(i,n){
		if(mi[i]!=0) continue;
		int t=n-1;
		while(t>=0 && a[t]==i) t--;
		mi[i]=(t+1)%n;
	}
	rep(i,n){
		rm[mi[i]]=i;
		le[i]=0;
		if(mi[i]>n){
			continue;
		}
		while(le[i]<n && a[(mi[i]+le[i])%n]==i) le[i]++;
	}
	
	//rep(i,n) cout<<mi[i]<<' '<<le[i]<<endl;
	//rep(i,n) mi[i]+le[i];
	
	int sl=0;
	rep(i,n) sl+=le[i];
	if(sl!=n){
		cout<<0<<endl;return 0;
	}
	if(mi[0]>n){
		cout<<0<<endl;return 0;
	}
	if(le[0]==n){
		cout<<zyo[n]<<endl;return 0;
	}
	int now=0;
	while(1){
		num.pb(now);len.pb(le[now]);
		now=rm[(mi[now]+le[now])%n];
		if(now==0) break;
	}
	int m=num.size();lint out=1;
	//rep(i,m) cout<<num[i]<<' '<<len[i]<<endl;
	REP(i,1,m){
		if(num[i]>0 && len[i]>len[0]){
			cout<<0<<endl;return 0;
		}
		if(len[i]<len[0]){
			if(num[i]<num[i-1] && i<m-1 && num[i]<num[i+1]){
				cout<<0<<endl;return 0;
			}
			else if(num[i]>num[i-1] && (i>=m-1 || num[i]>num[i+1])){
				out*=len[0]-len[i]+1;out%=mo;
			}
		}
	}
	int tu=len[0];
	rep(i,m-1){
		if(len[i+1]<tu){
			if(num[i+1]>num[i]) len[i]=len[i+1],len[i+1]=tu;
			//if(num[i+1]>num[i] && (i>=m-2 || num[i+1]>num[i+2]))
		}
	}
	rep(i,m){
		int bo=num[i];
		if(i<m-1) bo=max(bo,num[i+1]);
		p.pb(mp(bo,len[i]-1));
		v.pb(num[i]);
	}
	sort(All(p));reverse(All(p));
	sort(All(v));reverse(All(v));
	//rep(i,m) cout<<p[i].fi<<' '<<p[i].se<<endl;
	int used=0,i1=0,i2=0;
	while(i1<m){
		while(i2<m && v[i2]>p[i1].fi){
			i2++;used++;
		}
		out*=calp(n-p[i1].fi-used-1,p[i1].se);
		out%=mo;
		used+=p[i1].se;
		i1++;
	}
	cout<<out<<endl;
}


Measured memory_bytes: 22508
#include "bits/stdc++.h"
#define ll long long int
#define F first
#define S second
const ll mod = 1e9 + 7;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

//ll gcd(ll a, ll b)
//{
//    if (a == 0)
//        return b;
//    else
//        return gcd(b % a, a);
//}
 
//ll modexp(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;
//}
 
//ll sub_mod(ll a, ll b, ll m)
//{
//    if (a >= b)
//        return a - b;
//    else
//        return m - b + a;
//}
 
// ll add_mod(ll a, ll b)
// {
//    if (0 == b) 
//        return a;
 
//    b = mod - b;
//    if (a >= b)
//        return a - b;
//    else
//        return mod - b + a;
// }

int main()
{
	fastio;
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	//#endif
	ll n=0;
	cin>>n;
	string s;
	cin>>s;
	ll c=0;
	for(ll i=0;i<n-2;++i)
	{
		if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
			++c;
	}
	cout<<c;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cmath>
#include <ctype.h>
using namespace std;
string s;
int main() {
    cin >> s;
    cout << s.substr(0,5) << " " << s.substr(6, 7) << " " << s.substr(14, 5) << endl;
    return 0;
}

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

int main()
{   
    int w, h, n;
    cin >> w >> h >> n;
    int x0 = 0;
    int x1 = w;
    int y0 = 0;
    int y1 = h;
    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            x0 = max(x0, x);
        } else if (a == 2) {
            x1 = min(x1, x);
        } else if (a == 3) {
            y0 = max(y0, y);
        } else {
            y1 = min(y1, y);
        }
    }
    int ww = max(x1-x0, 0);
    int hh = max(y1-y0, 0);
    cout << ww*hh << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define MO 1000000007
using namespace std;
vector<lli>fact(2001,1);
int main()
{
    string str;
    lli k,x;
    cin >> k >> x;
    if(k*500>=x)	cout << "Yes" << endl;
    else	cout << "No" << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
{-
solve :: String -> String
solve s = show (gcd x y) ++ " " ++ show (lcm x y)
    where ns = map read (words s)
          x  = ns !! 0
          y  = ns !! 1
-}

mygcd :: Integer -> Integer -> Integer
mygcd x y
    | r == 0    = y
    | otherwise = mygcd y r
        where r = x `mod` y

mylcm :: Integer -> Integer -> Integer
mylcm x y = x * y `div` mygcd x y

solve :: String -> String
solve s = show (mygcd x y) ++ " " ++ show (mylcm x y)
    where ns = map read (words s)
          x  = ns !! 0
          y  = ns !! 1

main :: IO ()
main = interact (unlines . map solve . lines)

Measured memory_bytes: 3952
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 87;
LL a[MAXN];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%lld", &a[i]);
    LL ans = 0;
    bool OK = false;
    while (!OK) {
        OK = true;
        LL sum = 0;
        for (int i = 0; i < N; i++) {
            LL tmp = (a[i] / N);
            a[i] %= N;
            ans += tmp;
            a[i] -= tmp;
            sum += tmp;
        }
        for (int i = 0; i < N; i++) {
            a[i] += sum;
            //printf("i = %d a[i] = %lld\n", i, a[i]);
        }
        for (int i = 0; i < N; i++)
            if (a[i] >= N) OK = false;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);

double w[100000];
double v[100000];
typedef pair<double,int> pdi;
double a[100000];
const double EPS = 1e-8;

int main() {
  int N;
  double W;
  cin >> N >> W;  
  
  vector<pdi> vec1, vec2;
  double ans = 0;
  REP(i, N) {
    cin >> w[i] >> v[i];
    if (w[i]>0 && v[i]>0) {
      vec1.push_back(pdi((double)v[i]/w[i], i));
    } else if (w[i]<0 && v[i]<0) {
      w[i] = abs(w[i]);
      v[i] = abs(v[i]);
      vec2.push_back(pdi((double)v[i]/w[i], i));
    } else if (w[i]>0 && v[i]<=0) {
    } else if (w[i]<=0 && v[i]>=0) { 
      ans += v[i];
      W += abs(w[i]);
    }
  }
  sort(ALL(vec1), greater<pdi>());
  sort(ALL(vec2));
  memset(a,0,sizeof(a));
  int j = 0;
  for (int i=0; i<vec1.size(); ++i) {
    int idx = vec1[i].second;
    if (w[idx]<=W) {		// 1 wariate
      ans += v[idx];
      W -= w[idx];
    } else {
      ans += v[idx] * W/w[idx];
      a[idx] = W/w[idx];
      W = 0;
      while(a[idx] < 1) {
      //while(w[idx]>W+EPS) {
	if (j >= vec2.size() || vec2[j].first >= vec1[i].first) {
	  break;
	}
	int jdx = vec2[j].second;
	double hoge = min(w[idx]*(1-a[idx])/w[jdx], 1-a[jdx]);
	a[jdx] += hoge;
	double hoge2 = (w[jdx]*hoge)/w[idx];
	//cout << "hoge = " << hoge << endl;
	//cout << "hoge2 = " << hoge2 << endl;
	a[idx] += hoge2;
	ans += v[idx] * hoge2;
	//cout << "ans1 = " << ans  << endl;
	ans -= v[jdx] * hoge;
	//cout << "ans2 = " << ans << endl;
	if (a[jdx] > 1-EPS) j++;
      }
      //cout << "!!" << 1-a[idx] << endl;
    }
    //cout << W << ":  " << ans << endl;
  }
  printf("%.10f\n", ans);
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<math.h>
using namespace std;

int main(){
    
    int N, M;
    map<int, string> s{}, t{};
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> s[i];
    }
    cin >> M;
    for(int i=1; i<=M; i++){
        cin >> t[i];
    }
    
    int moneymax=0, money=0;
    for(int i=1; i<=N; i++){
        for(int j=i; j<=N; j++){
            if(s[i]==s[j]){
                money++;
            }
        }
        for(int j=1; j<=M; j++){
            if(s[i]==t[j]){
                money--;
            }
        }
        if(moneymax<money){
            moneymax=money;
        }
        money=0;
    }
    
    cout << moneymax << endl;
    
    return 0;
}


Measured memory_bytes: 256