akhauriyash/Code-Regression huggingface dataset:
//naveen mall
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb               push_back
#define sz(c)            (int)c.size()
#define len(c)           (int)c.length()
#define vec              vector
#define int              long long int
#define all(c)           c.begin(), c.end()
#define rall(c)          c.rbegin(), c.rend()
#define trav(a,i)        for(auto i: a)
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define invect(v,n)       for(int i=0;i<n;i++ ){int arb;cin>>arb;v.pb(arb);}
#define inset(s,n)        fl(i,0,n){int aset;cin>>aset;s.insert(aset);}
#define display(c)        trav(c,i) cout<<i<<" ";cout<<"\n";
#define F                 first
#define S                 second
#define pii               pair<int,int>
#define PB                pop_back
#define endl              "\n"
#define what(x) cerr << #x << " is " << x << endl;
int sum() { return 0; }template<typename T,typename... Args>T sum(T a, Args... args) { return a + sum(args...); }


void solve()
{ 


int n;
cin>>n;
int a[n];
int cnt[n+1]={0};

rep(i,0,n)
  {
    cin>>a[i];
    cnt[a[i]]++;


  }
int ans=0;
rep(i,1,n+1)
   {   // cout<<ans<<" ";
     ans+=(cnt[i]*(cnt[i]-1))/2;


   }
   //cout<<ans<<" ";
   rep(i,0,n)
     {  
        int an=ans-(cnt[a[i]]*(cnt[a[i]]-1)/2) + max(0LL,((cnt[a[i]]-1)*(cnt[a[i]]-2)/2));

     cout<<an<<endl;



     }







}
signed main()
{fast
  int t;
  //cin>>t;
  t=1;
  while(t--)
    {solve();}
  
}












Measured memory_bytes: 5760
#include <stdio.h>

int main(void) {
	int n;
	int a[1024];
	int q;
	int i;
	if (scanf("%d", &n) != 1) return 1;
	for (i = 0; i < n; i++) {
		if (scanf("%d", &a[i]) != 1) return 1;
	}
	if (scanf("%d", &q) != 1) return 1;
	for (i = 0; i < q; i++) {
		int b, e, k;
		int count = 0;
		int j;
		if (scanf("%d%d%d", &b, &e, &k) != 3) return 1;
		for (j = b; j < e; j++) {
			if (a[j] == k) count++;
		}
		printf("%d\n", count);
	}
	return 0;
}



Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define pii pair<int,int>
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf 10000000000000000 //10^16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
  string s;
  cin>>s;
  int a=0,b=0,c=0;
  rep(i,s.size()) {
    if(i==0) a+=(s[i]-'0')*1000;
    else if(i==1) a+=(s[i]-'0')*100;
    else if(i==2) a+=(s[i]-'0')*10;
    else if(i==3) a+=(s[i]-'0');
    else if(i==5) b+=(s[i]-'0')*10;
    else if(i==6) b+=(s[i]-'0');
    else if(i==8) c+=(s[i]-'0')*10;
    else if(i==9) c+=(s[i]-'0');
  }
  if(a<=2019&&b<=4&&c<=30) cout<<"Heisei"<<endl;
  else cout<<"TBD"<<endl;
}

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

int main()
{
	int N, D, X;
	cin >> N >> D >> X;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	int ans = X;
	for (int i = 0; i < N; i++)
	{
		int k = 0;
		while (k*A[i] + 1 <= D)
		{
			ans++;
			k++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <deque>

int main(){
  int H, W, A, B;
  scanf("%d", &H);
  scanf("%d", &W);
  scanf("%d", &A);
  scanf("%d", &B);
  std::queue<char > queue;
  for (int i=0; i<B; i++){
    for (int j=0; j<A; j++){
      queue.push('1');
    }
    for (int j=A; j<W; j++){
      queue.push('0');
    }
  }
  for (int i=B; i<H; i++){
    for (int j=0; j<A; j++){
      queue.push('0');
    }
    for (int j=A; j<W; j++){
      queue.push('1');
    }    
  }
  while(queue.size()>0){
    std::string s;
    for (int i=0; i<W; i++){
      s+=queue.front();
      queue.pop();
    }
    std::cout << s << std::endl;
  }
  return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int n, m;
    int l[100010], r[100010];
    int imos[100010] = {};
    long long int ans = 0;

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i];
        imos[l[i]]++;
        imos[r[i]+1]--;
    }

    for (int i = 0; i <= n; i++) {
        imos[i+1] += imos[i];
    }

    for (int i = 1; i <= n; i++) {
        if (imos[i] == m) {
            ans++;
        }
    }

    cout << ans << endl;
}



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

/*
使う色を選ぶのに
2^20=1048576


*/

int main(){
	int n,m;
	cin>>n>>m;
	double r[20],g[20],b[20];
	for(int i=0;i<n;i++)cin>>r[i]>>g[i]>>b[i];
	double ans=0;
	
	for(int i=0;i<(1<<n);i++){
		if(__builtin_popcount(i)==m){
			double tmp=0;
			for(int j=0;j<n;j++){
				if(i>>j & 1){
					for(int k=j+1;k<n;k++){
						if(i>>k & 1){
							tmp+=(r[j]-r[k])*(r[j]-r[k]) + (g[j]-g[k])*(g[j]-g[k]) + (b[j]-b[k])*(b[j]-b[k]);
						}
					}
				}
			}
			
			
			ans=max(ans,tmp);
		}
	}
	
	
	printf("%.20f\n",ans);
	return 0;
}


Measured memory_bytes: 1252
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int main(){
  string s;
  cin >> s;
  int n = s.length();
  for (int i=0; i<n; i++){
    s.replace(i, i+1, "x");
  }
  dunk(s);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define max 1e12

using namespace std;
int main(){
    long long int n;
    cin >> n;
    long long count=0;
    long long min=max;
    long long j=0;
    for(long long i=1;i*i<=n;i++){
        if(n%i==0){
            j=n/i;
            count=i+j-2;
            if(min>count) min=count;
        }
    }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256
S=input()
T=input()
k = len(T)
ans=k
lim=0
for i in range(len(S)-len(T)+1):
  for j in range(k):
    #print(i, j, S[i+j],T[j])
    if S[i+j]!=T[j]:
      lim+=1
  if lim<=ans:
    ans=lim
  lim=0
print(ans)

Measured memory_bytes: 9088
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

string correctJ(string st){
	int len = st.size();
	string cst = st.substr(len-1,1);
	cst += st.substr(0,len-1);
	return cst;
}

string correctC(string st){
	int len = st.size();
	string cst = st.substr(1);
	cst += st.substr(0,1);
	return cst;
}

string correctE(string st){
	int len = st.size();
	string cst = st.substr(len - (len)/2);
	if(len % 2 != 0){
		cst += st.substr(len/2,1);
	}
	cst += st.substr(0,len/2);
	return cst;
}

string correctA(string st){
	string cst = st;
	reverse(cst.begin(),cst.end());
	return cst;
}

string correctP(string st){
	string cst = st;
	for(int i = 0;i < cst.size();i++){
		if(cst[i] - '0' < 10 && cst[i] != '0'){
			cst[i] = cst[i] - 1;
		}else if(cst[i] == '0'){
			cst[i] = '9';
		}
	}
	return cst;
}

string correctM(string st){
	string cst = st;
	for(int i = 0;i < cst.size();i++){
		if(cst[i] - '0' < 9){
			cst[i] = cst[i] + 1;
		}else if(cst[i] == '9'){
			cst[i] = '0';
		}
	}
	return cst;
}

int main(){
	vector<string> ans;
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		string ser;
		cin >> ser;
		string mes;
		cin >> mes;
		string cmes = mes;
		for(int j = ser.size()-1;j >= 0;j--){
			if(ser[j] == 'J'){
				cmes = correctJ(cmes);
			}else if(ser[j] == 'C'){
				cmes = correctC(cmes);
			}else if(ser[j] == 'E'){
				cmes = correctE(cmes);
			}else if(ser[j] == 'A'){
				cmes = correctA(cmes);
			}else if(ser[j] == 'P'){
				cmes = correctP(cmes);
			}else if(ser[j] == 'M'){
				cmes = correctM(cmes);
			}
		}
		ans.push_back(cmes);
	}
	
	for(int i = 0;i < ans.size();i++){
		cout << ans[i] << endl;
	}
	return 0;
}




Measured memory_bytes: 3012
L, R = map(int, input().split())

ret = 2019 ** 2
flag = False
for l in range(L, R):
    for r in range(l + 1, R + 1):
        temp = (l % 2019) * (r % 2019) % 2019
        if ret > temp:
            ret = temp
            if ret == 0:
                print(0)
                exit()

print(ret)


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

using namespace std;
using ll = long long;
const int mod = 1e9+7;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint operator-() const { return mint(-x); }

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const { return mint(*this) += a; }

    mint operator-(const mint a) const { return mint(*this) -= a; }

    mint operator*(const mint a) const { return mint(*this) *= a; }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }

    mint &operator/=(const mint a) { return *this *= a.inv(); }

    mint operator/(const mint a) const { return mint(*this) /= a; }
};

istream &operator>>(istream &is, const mint &a) { return is >> a.x; }

ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

struct combination {
    vector<mint> fact, ifact;

    combination(int n) : fact(n + 1), ifact(n + 1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};

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

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

vector<int> A[100];
int ans[100], C[100], D[100];
map<pair<int, int>, pair<int, int>> M;

void dfs(int from, int cu, int co, int c, int d) {
    if (c / d > C[from] / D[from]) {
        c = C[from];
        d = D[from];
    }
    for (int i = 0; i < A[from].size(); ++i) {
        int to = A[from][i];
        auto k = M[make_pair(from, to)];
        int a = k.first, b = k.second;
        if (cu - a < 0) {
            int l = abs(cu - a) / c + (abs(cu - a) % c ? 1 : 0);
            cu = cu - a + c * l;
            co = co + b + d * l;
        } else {
            cu -= a;
            co += b;
        }
        if (ans[to] > co) {
            ans[to] = co;
            printf("from = %d to = %d cost = %d \n", from, to, co);
            dfs(to, cu, co, c, d);
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    mint ans = 0;
    mint one = mint(k).pow(n);
    vector<mint> D(k + 1);
    for (int i = k; i >= 2; --i) {
        mint sum = mint(k / i).pow(n);
        for (int j = i; j <= k; j += i) {
            sum -= D[j];
        }
        D[i] = sum;
        ans += mint(i) * sum;
        one -= sum;
    }
    ans += one;
    cout << ans << endl;
    return 0;
}


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

int main(){
    int N, K, R, S, P;
    cin >> N >> K;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    vector<int> scores = {R, S, P};
    vector<int> Tlist(N);
    for (int i=0; i<N; i++){
        if (T[i] == 'r') Tlist[i] = 2; //グーに勝つのはパーなのでパーを出すことで score[2] 点が手に入る
        if (T[i] == 's') Tlist[i] = 0;
        if (T[i] == 'p') Tlist[i] = 1;
    }

    int ans=0;
    for (int i=0; i<K; i++){
        // i, i+K, i+2K, ... の列について考える
        // i+K と　i は同じ手を出してはいけないということは、どちらかでは負ける必要がある
        int j = i;
        int flag = 0;
        while(j < N){
            if (j < K){
                // 制約がないので勝てる
                // printf("%d\n", scores[Tlist[j]]);
                ans += scores[Tlist[j]];
            } else{
                if (T[j] == T[j - K] && flag == 0){
                    // printf("%c\n", T[j]);
                    flag = 1;
                } else{
                    // 前と同じ手を出せる
                    ans += scores[Tlist[j]];
                    // printf("%d\n", scores[Tlist[j]]);
                    flag = 0;
                }
            }
            j += K;
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
#include <stdio.h>

int main(void)
{
  int w,h,x,y,r;

  scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);

  if(r <= x && x <= w - r)
    {
      if(r <= y && y <= h - r)
	{
	  printf("Yes\n");
	}
      else
	printf("No\n");
    }
  else
    printf("No\n");


  return 0;

}



Measured memory_bytes: 2128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main(){
	int n, q;
	ll sum = 0;
	cin >> n;
	vector<int> a(100001);
	rep(i, n){
		int in;
		cin >> in;
		a[in]++;
		sum += in;
	}
	cin >> q;
	vector<ll> ans(q);
	rep(i, q){
		int b, c;
		cin >> b >> c;
		sum -= a[b]*(b-c);
		a[c] += a[b];
		a[b] = 0;
		ans[i] = sum;
//		cout << sum << endl;
	}
	rep(i, q){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 4544
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,w,ans,p;
    cin>>a;
    if(a%2==1) cout<<"0";
    else{
        a/=2;
        while(a!=0){
            ans=ans+a/5;
            a=a/5;
        };
        cout<<ans;
    }
};

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


#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define pb push_back
#define inf 1e9+11
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

void pre(){
}

void solve(){
	ll n;
	cin >> n;
	ll a[n],h[n];
	rep(i,n) cin >> h[i];
	ll dp[n];
	memset(dp, inf, sizeof(dp));
	dp[0] = 0;
	rep(i,n-1){
		repA(j,i+1,i+2){
			if(j <= n-1){
				dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j])); 
			}
		}
	}
	cout << dp[n-1] << endl;

}
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	// int n;cin>>n;
	// rep(i,1) 
	solve();	
	return 0;
}




Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
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; }
using ll = long long;
const ll MOD = 1e9+7; int INF=INT_MAX; ll LLINF = 1LL << 60;
const vector<int> d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vector<int> d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vector<int> d4x = {1, 0, -1, 0}; vector<int> d4y = {0, 1, 0, -1};

//

int main(){
    int n,w; cin>>n>>w;
    vector<ll> weight(n);
    vector<ll> value(n);
    rep(i,n){
        cin>>weight[i]>>value[i];
    }

    vector<vector<ll>> dp(n,vector<ll>(w+1, 0));
    for (ll i = weight[0]; i < w+1; i++)
    {
        dp[0][i]=value[0];
    }
    for (ll i = 1; i <= n-1; i++)
    {
        for(ll j=0; j<=w; j++){
            chmax(dp[i][j],dp[i-1][j]);
            if(j+weight[i]<=w) chmax(dp[i][j+weight[i]], dp[i-1][j]+value[i]);
        }
    }
    cout<<dp[n-1][w]<<endl;
}

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

int main(){
	int N;
	cin >> N;
	vector<int> a(N);
	for(int i=0 ; i < N ; i++ ){
		cin >> a[i];
	}
	
	int f[2] = {0};
	vector<int> v;
	for(int i=0 ; i < N ; i++ ){
		if( a[i] >= 2 ){
			v.push_back( a[i] );
		}else{
			f[a[i]]++;
		}
	}
	// 0 が奇数個のみのケース
	if( f[0] == N && v.size() == 0 ){
		for(int i=0 ; i < f[0] ; i++ ){
			cout << 0 << endl;
		}
		return 0;
	}
	
	sort( v.begin() , v.end() );
	if( v.size() >= 2 && v[v.size()-2] == 2 && v[v.size()-1] == 3 ){
		swap(v[v.size()-2],v[v.size()-1]);
	}
	
	if( f[0] % 2 == 1 && f[1] == 0 ){
		int m = *min_element(v.begin(),v.end());
		for(int i=0 ; i < v.size() ; i++ ){
			if( v[i] == m ){
				v[i] = -1;
				break;
			}
		}
		int x = m;
		for( ; f[0] ; f[0]-- ){
			if( f[0] == 1 ){
				v.push_back( x );
			}
			v.push_back( 0 );
		}
	}else{
		int one, zero;
		one = f[1];
		zero = f[0];
		for( ; f[0] ; f[0]-- ){
			v.push_back( 0 );
		}
		for( ; f[1] ; f[1]-- ){
			v.push_back( 1 );
		}
		if( one && zero && zero % 2 == 1 ){
			for(int i=1 ; i < v.size() ; i++ ){
				if( v[i-1] == 0 && v[i] == 1 ){
					swap( v[i-1] , v[i] );
					break;
				}
			}
		}
	}
	for(int i=0 ; i < v.size() ; i++ ){
		if( v[i] == -1 ) continue;
		cout << v[i] << endl;
	}
}

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

using namespace std;

int n, ans(0);
int a[110];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            for (int k = j + 1; k <= n; k++)
                if (a[i] + a[j] > a[k] && a[i] != a[j] && a[j] != a[k])
                    ans++;
    cout << ans << endl;

    return 0;
}

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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

signed main(){
	int N=read();
	int a[N],b[N];
	int check[100050]={0};
	REP(i,N){
		a[i]=read();
		b[i]=read();
	}
	
	REP(i,N){
		check[a[i]] += 1;
		check[b[i]+1] -=1;
	}
	
	int sum=1;
	int ans=0;
	REP(i,N+2){
		sum += check[i];
		if(sum>=i) ans=i;
	}
	cout << ans-1 << endl;
}

Measured memory_bytes: 5588
k=int(input())
mod7 = 7%k
mod10= 10%k

mod = mod7
mod10times = mod7

if mod%k==0:
    print(1)
else:

    for i in range(2,2000000):
        mod10times = mod10times*mod10%k
        mod = mod10times+mod%k

        if  mod%k==0:
            break

    if i==1999999:
        print(-1)
    else:
        print(i)
        

Measured memory_bytes: 9012
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define  all(v)     (v).begin(),(v).end()
#define  rall(v)    (v).rbegin(),(v).rend()
#define  pb         push_back
#define  eb         emplace_back
#define  mp         make_pair
#define  ff         first
#define  ss         second
#define  pf         push_front
#define  bs         binary_search
#define  lb         lower_bound
#define  ub         upper_bound
#define  dec(x)   fixed<<setprecision(x)
#define  lcm(a,b)   (a*b/__gcd(a,b))
const ll inf=LLONG_MAX;
const ll mod=1e9+7;
const ld pi=acos(-1);
                    
void solution(){
   ll n;
   cin>>n;
   ll a[n];
   ll sum=0;
   for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
   ll ans=0;
   for(int i=0;i<n;i++){
       ans+=((a[i]%mod)*((sum-a[i])%mod))%mod;
       sum-=a[i];
   }
   ans%=mod;
   cout<<ans;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 5212
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define READ(a) int a; cin >> a;
#define READARR(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define READMAT(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define print(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
    char ch;
    cin >> ch;
    cout << (char)(ch + 1);
}

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

using namespace std;
int main(void){
    int n,m,sum=0;

    cin >> n;
    m=n;
    while(m>0){
        sum+=m%10;
        m-=m%10;
        m/=10;
    }
    if(n%sum==0)cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

namespace AtCoder.Abc
{
    class Question3
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            long n = long.Parse(Console.ReadLine());


            var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            var list = inputLongArray;

            var result = list.Min(x =>
            {
                var c = 0;
                while(x % 2 == 0 && x > 0){ x >>= 1;c++; }
                return c;
            });
                                 
            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}



Measured memory_bytes: 13396
S = input()
count = 0
koremade = 0
for i in range(0,len(S)):
    if S[i] in 'ACGT':
        count += 1
        if i == len(S)-1:
           if koremade <= count:
               koremade = count 
    else:
        if koremade <= count:
            koremade = count
        count = 0
print(koremade)

Measured memory_bytes: 61764
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int main() {

	char str1[205], str2[200];

	char p[105];
	cin >> str1 >> p;

	strcpy(str2, str1);
	strcat(str1, str2);
	if (strstr(str1, p) == NULL)cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;

}



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

int main() {
  int N, K;
  cin >> N >> K;
  double ans = 0;
  for (int i = 1; i < N + 1; i++) {
    int a = i, b = 0;
    while(a < K) {
      a *= 2;
      b++;
    }
    ans += pow(0.5, b);
  }
  ans /= N;
  cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#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 revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int dist(int K, int x)
{
    if (x < K - x) return x;
    else return K - x;
}

int main()
{
    int N, K; cin >> N >> K;
    int ans = 0;
    rep (i, 0, N) {
        int x; cin >> x;
        ans += dist(K, x) * 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
marks = ['S', 'H', 'C', 'D']
m = int(input())

cards = []
for _ in range(m):
    cards.append(input())
    
for mark in marks:
    for number in range(1, 14):
        if f'{mark} {number}' not in cards:
            print(f'{mark} {number}')



Measured memory_bytes: 5608
#include<cstdio>
int ks[6]={500,100,50,10,5,1};
int main(){
    for(;;){
        int ins;
        scanf("%d",&ins);
        if(ins==0)break;
        ins=1000-ins;
        int ans=0;
        for(int i=0;i<6;i++){
            ans+=ins/ks[i];
            ins-=ks[i]*(ins/ks[i]);
        }
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 0
n=int(input())
c={}
for i in range(n):
    t=input()
    if t in c:
        c[t]+=1
    else:
        c[t]=1
c=sorted(c.items(),key=lambda x:(-x[1],x[0]))
p=c[0][1]
for i,j in c:
    if j==p:
        print(i)
    else:
        break

Measured memory_bytes: 57436
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String[] spl = s.split(" ");
		int A = Integer.parseInt(spl[0]);
		int B = Integer.parseInt(spl[1]);
		int C = Integer.parseInt(spl[2]);
		
		if(((A > C)&&(B < C))||((A < C)&&(B > C))){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

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

int main()
{
   int a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
  
    if(a==0) cout <<"1";
   else if(b==0) cout <<"2";
  else if(c==0) cout <<"3";
  else if(d==0) cout <<"4";
  else cout <<"5";
  return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000


int main(){

	int N;
	cin>>N;
	
	int cnt4=0,cnt2=0,cntp=0;
	
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		if(a%4==0)cnt4++;
		else if(a%2==0)cnt2++;
		else cntp++;
	}
	
	if(cntp<=cnt4){
		cout<<"Yes"<<endl;
		return 0;
	}
	if(cntp!=cnt4+1||cnt2!=0){
		cout<<"No"<<endl;
		return 0;
	}
	
	cout<<"Yes"<<endl;
	
	
    return 0;
}



Measured memory_bytes: 256
/**
* Think twice, code once.
* 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
* 2.runtime error
* 3.boundary condition
* ---------------------------------------------------------------------------------------
* Author : zzy
* Date : 2020-03-18-17.31.56 Wednesday
*/
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = (int)1e5+1000;
int dp[maxn][5], n, a[maxn], b[maxn], c[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    ms(dp, 0);
    cin >> n;
    for1(i, n) cin >> a[i] >> b[i] >> c[i];
    for1(i, n) {
        for (int j = 1; j <= 3; ++j) {
            int num;
            if (j == 1) num = a[i];
            else if (j == 2) num = b[i];
            else if (j == 3) num = c[i];
            for (int k = 1; k <= 3; ++k) {
                if (k == j) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][k]+num);
            }
        }
    }
    cout << max(dp[n][1], max(dp[n][2], dp[n][3])) << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 3456
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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 ll INF=1e18;

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    ll v=max({a,b,c});
    ll ans=a+b+c;
    ans-=v;
    ll k;
    cin >> k;
    rep(i,k){
        v*=2;
    }
    ans+=v;
    cout << ans << endl;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long a,b;
  cin>>a>>b;
  for(int i=1;i<b+1;i++){
    if(a*i%b==0){
cout<<a*i<<endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#define ll long long
#define mod 1000000007
int main(){
    ll a,b,c,i,j,n,ans=0;
    scanf("%lld",&n);
    for(i=1; i<n; i++){
        ans+=(n-1)/i;
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 1732
#include<iostream>

using namespace std;

int main(void)
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		double x1,y1,x2,y2,x3,y3,x4,y4;
		cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
		double a1,a2;
		a1=(y2-y1)/(x2-x1);
		a2=(y4-y3)/(x4-x3);
		if(a1==a2)
		{
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()


using namespace std;

int main()
{
	int A, B, K;

	cin >> A >> B >> K;

	int i = min(A, B);
	int count = 0;

	while (true)
	{
		if (A % i == 0 && B % i == 0)
		{
			count++;
		}

		if (count == K)
		{
			break;
		}

		i--;
	}

	cout << i << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		final int H = sc.nextInt();
		final int W = sc.nextInt();
		String[] str = new String[H];
		for(int i = 0; i < H; i++) {
			str[i] = sc.next();
		}
		
		boolean[] row = new boolean[H];
		Arrays.fill(row, false);
		boolean[] col = new boolean[W];
		Arrays.fill(col, false);
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				if(str[i].charAt(j) == '#') {
					col[j] = true;
					row[i] = true;
				}
			}
		}
		
		for(int i = 0; i < H; i++) {
			if(row[i]) {
				for(int j = 0; j < W; j++) {
					if(col[j]) {
						System.out.print(str[i].charAt(j));
					}
				}
				System.out.println("");
			}
		}
	}
}


Measured memory_bytes: 26068
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template < typename T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    int len = comma - names;
    for (int i = 0; i < len; ++i) {
        cout << names[i];
    }
    cout <<  " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;

#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const ll LINF = LLONG_MAX, base = 1e9, MOD = 1e9 + 7, N = 1e5 + 10, M = 1e3 + 10;
const int INF = INT_MAX;
const db PI = acos(-1);

void test();

int main() {
    fast_io();
    test();
    return 0;
}

void test() {
    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;
    if (e - a > k) {
        cout << ":(\n";
    } else {
        cout << "Yay!\n";
    }
}


Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.Bits (xor)
import Data.List (intercalate)

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  as <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    s = foldl xor 0 as :: Int
  putStrLn . intercalate " " . map (show . xor s) $ as

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
{-# INLINE unsafeTextToInt #-}


Measured memory_bytes: 33072
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
 		Scanner scanner = new Scanner(System.in);
 		int A = scanner.nextInt();
 		int B = scanner.nextInt();
 		int sum = 0;
 		if (A == 1) {
 			sum += 300000;
 		} else if (A == 2) {
 			sum += 200000;
 		} else if (A == 3) {
 			sum += 100000;
 		}
 		
 		if (B == 1) {
 			sum += 300000;
 		} else if (B == 2) {
 			sum += 200000;
 		} else if (B == 3) {
 			sum += 100000;
 		}
 		
 		if (A == 1 && B == 1 ) {
 			sum += 400000;
 		}
 		
 		System.out.println(sum);
	}

}


Measured memory_bytes: 23636
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

l,r,d=mp()
ans=0
for i in range(l,r+1):
    if i%d==0:
        ans+=1
print(ans)

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

vector<pii> deltas = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int H, W; cin >> H >> W;
	vector<string> arr (H);
	F0R(i, H) cin >> arr[i];
	vector<vector<bool>> seen (H, vector<bool> (W));
	vector<vector<int>> dist (H, vector<int> (W));

	queue<pii> q; 
	F0R(i, H) F0R(j, W) if (arr[i][j] == '#') {
		q.push({j, i});
		seen[i][j] = true;
	}
	
	while (!q.empty()) {
		pii pos = q.front(); q.pop();
		
		for (pii d : deltas) {
			int nx = pos.first + d.first;
			int ny = pos.second + d.second;
			if (0 <= nx && nx < W && 0 <= ny && ny < H && !seen[ny][nx]) {
				seen[ny][nx] = true;
				dist[ny][nx] = 1 + dist[pos.second][pos.first];
				q.push({nx, ny});
			}
		}
	}

	int best = 0;
	F0R(i, H) F0R(j, W) best = max(best, dist[i][j]);
	print(best);	
}

Measured memory_bytes: 13584
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dp[100000+9];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int arr[n];
    for(int i = 0;i<n;i++)
        cin>>arr[i];
    dp[0] = 0;
    for(int i =1 ; i<n;i++){
        dp[i] = 1e9;
        for(int j = 1;i-j>=0 && j<=k ; j++)
            dp[i] = min(abs(arr[i]-arr[i-j]) + dp[i-j] , dp[i] );
    }
    printf("%d",dp[n-1]);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
struct Edge {
  ll to;
  ll cost;
};
int main() {
  int N;
  cin >> N;
  vector<P> a(N);
  REP(i, N) { cin >> a[i].second >> a[i].first; }
  vector<int> permutation(8);
  REP(i, 8) permutation[i] = i;
  do {
    bool ok = true;
    REP(i, N) {
      if (permutation[a[i].second] != a[i].first) ok = false;
    }
    if (!ok) continue;
    ok = true;
    REP(i, 8) {
      int cnt = 0;
      int j = 0, k = i;
      while (j < 8) {
        if (permutation[j] == k) cnt++;
        k++, j++;
        if (7 < k) {
          if (1 < cnt) ok = false;
          k = 0;
          cnt = 0;
        }
      }
      if (1 < cnt) ok = false;
    }
    if (!ok) continue;
    REP(i, 8) {
      int cnt = 0;
      int j = 0, k = i;
      while (j < 8) {
        if (permutation[j] == k) cnt++;
        k--, j++;
        if (k < 0) {
          if (1 < cnt) ok = false;
          k = 7;
          cnt = 0;
        }
      }
      if (1 < cnt) ok = false;
    }
    if (!ok) continue;
    if (ok) {
      REP(i, 8) {
        REP(j, 8) {
          if (permutation[i] == j) {
            cout << "Q";
          } else {
            cout << ".";
          }
        }
        cout << endl;
      }
      return 0;
    }
  } while (next_permutation(permutation.begin(), permutation.end()));
}


Measured memory_bytes: 3120
#include <iostream>

int main() {
    int K, A, B;
    std::cin >> K >> A >> B;
    for (int i = A; i <= B; i++) {
        if (i % K == 0) {
            std::cout << "OK\n";
            return 0;
        }
    }
    std::cout << "NG\n";
}

Measured memory_bytes: 3632
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int n;
    cin >> n;

    int prev = 0;
    bool ans = true;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;

        if (h < prev) ans = false;

        if (h > prev) {
            prev = h - 1;
        }
    }

    if (ans) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
using cost_t=int;

struct Edge {
    int from, to;
    cost_t cost;
    Edge(int from, int to, cost_t cost) : from(from), to(to), cost(cost) {}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

const cost_t INF=1e9;
bool bellman_ford(int s,Graph& g,vector<cost_t>& d){
    int n = g.size();
    d.assign(n,INF);
    d[s] = 0;
    bool update=true;
    for(int i=0;update;i++){
        if(i==n){
            return false;
        }
        update=false;
        for(int i=0;i<n;i++){
            if(d[i]==INF) continue;
            for(auto &e:g[i]){
                cost_t tmp = d[i] + e.cost;
                if(tmp<d[e.to]){
                    d[e.to]=tmp;
                    update=true;
                }
            }
        }
    }
    return true;
}
int main(){
    int V,E,r;
    cin>>V>>E>>r;
    Graph g(V);
    for(int i=0;i<E;i++){
        int s,t,d;
        cin>>s>>t>>d;
        g[s].push_back(Edge(s,t,d));
    }
    vector<int> d;
    auto ret = bellman_ford(r,g,d);
    if(ret){
        for(int i=0;i<V;i++){
            if(d[i]==INF) cout<<"INF"<<endl;
            else cout<<d[i]<<endl;
        }
    }
    else{
        cout<<"NEGATIVE CYCLE"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
using pair = pair<int, int>;
using vec  = vector<int>;
using vvec = vector<vec>;
const int INF = 100000000;
// " ", ' '

// プロトタイプ宣言
// int myfunc(int, vvec);

// グローバル変数
// int N, M;
// vvec data(N, vec(M));

// 関数：

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N; cin >> N;
	vec A(N);
	for (int i=0; i<N; i++) cin >> A.at(i);

	int max_sbt = 0;
	for (int i=0; i<N-1; i++) {
		for (int j=i+1; j<N; j++) {
			int sbt = abs(A.at(i)-A.at(j));
			if (max_sbt < sbt) max_sbt = sbt;
		}
	}

	cout << max_sbt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll p[8][3] = {
  {1,1,1},
  {1,1,-1},
  {1,-1,1},
  {1,-1,-1},
  {-1,1,1},
  {-1,1,-1},
  {-1,-1,1},
  {-1,-1,-1},
};

int main() {
  int n,m;
  cin >> n >> m;

  vector<vector<ll>> v(8,vector<ll>(n));
  rep(i,n){
    ll x,y,z;
    cin >> x >> y >> z;
    rep(j,8){
      v[j][i] = x*p[j][0] + y*p[j][1] + z*p[j][2];
    }
  }
  ll ans = 0;
  rep(j,8){
    sort(v[j].rbegin(),v[j].rend());
    ll res = 0;
    rep(i,m) res += v[j][i];
    ans = max(ans,res);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <array>
#include <bitset>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = Mint(2).pow(n);
  Mint pow(long long n) const {
    if (n==0) return Mint(1);
    Mint y = pow(n>>1); // pow(n/2)を計算する
    y *= y;
    if (n%2==1) y *= *this;
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return a.pow(mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    Mint one = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= (i + one);
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

class UnionFind {
private:
  int n;
  std::vector<int > parent;
public:
  UnionFind(int num) :
    n(num) {
      parent = std::vector<int> (n);
      for (int i=0; i<n; i++) {
        parent[i] = i;
      }
    }
  int GetRoot(int i) {
    int n = i;
    while(parent[n]!=n) {
      n = parent[n];
    }
    parent[i] = n;
    return n;
  }

  bool SameGroup(int n, int m) {
    n = this->GetRoot(n);
    m = this->GetRoot(m);
    return n==m;
  }

  bool Unite(int n, int m) {
    n = this->GetRoot(n);
    m = this->GetRoot(m);
    if (n==m) return false;
    parent[n] = m;
    return true;
  }
};

int getgcd(int a, int b) {
  int max = std::max(a, b);
  int min = std::min(a, b);
  if (min==0) return max;
  return getgcd(min, max%min);
}

Mint mynCk(int n, int k) {
  if (2*k>n) return mynCk(n, n-k);
  Mint retval(1);
  Mint iretval(1);
  for (int i=0; i<k; i++) {
    retval *= Mint(n-i);
  }
  for (int i=1; i<=k; i++) {
    iretval *= Mint(i);
  }
  return retval / iretval;
}

int main() {
  int r1, c1, r2, c2;
  std::cin >> r1 >> c1 >> r2 >> c2;
  Mint ans(0);
  ans += mynCk(r2+c2+2, c2+1);
  ans -= mynCk(r1+c2+1, c2+1);
  ans -= mynCk(r2+c1+1, r2+1);
  ans += mynCk(r1+c1, c1);
  std::cout << ans.x << std::endl;
  return 0;
}

Measured memory_bytes: 3172
#include<stdio.h>
int main(){
	unsigned long long n,i , ans, m;
	while(1){
		scanf("%lld",&n);
		if(n == 0)
			break;
		m = 0;
		i = 1;
		ans = 0;
		while(n > 7){
			m = n % 8;
			if(m > 4)
				m+=2;
			else if(m == 4)
				m++;
			ans = ans + m*i;
			n  /= 8;
			i *= 10;
		}
		if(n > 4)
			n+=2;
		else if(n == 4)
			n++;

		ans = ans + n*i;
	printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>

int shower[200000];

int main()
{
    int n, t, i, answer, aux;
    scanf("%d%d", &n, &t);
    for (i = 0; i < n; i++)
        scanf("%d", &shower[i]);

    answer = t + shower[n - 1];
    for (i = 0; i < n - 1; i++) {
        aux = shower[i + 1] - (shower[i] + t);
        if (aux > 0)
            answer -= aux;
    }
    printf("%d\n", answer);
    return 0;
}


Measured memory_bytes: 896
n=int(input())
t=int(input())
t1=int(input())
maxim=t1-t
if t<=t1:
    max_i=t1
    min_i=t
else:
    min_i=t1
    max_i=t
if n>2:
    for i in range(2,n):
        t=int(input())
        if t-min_i>maxim:
            maxim=t-min_i
        if t>max_i:
            max_i=t
        elif t<min_i:
            min_i=t
print(maxim)


Measured memory_bytes: 5608
import collections


class RollingHash:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=26, mod=2**50 + 1)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in d.values():
        if max(l) - min(l) >= diff:
            return True
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Measured memory_bytes: 50524