akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<int, int> student;

    for (int i = 0; i < n; i++) {
        int order;
        scanf("%d", &order);
        student[order] = i + 1;
    }

    for (auto p : student) {
        int num = p.second;
        printf("%d ", num);
    }
    printf("\n");

    return 0;
}

Measured memory_bytes: 5504
use std;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn e_multiplication_4() {
    let nk = read_vec::<usize>();
    let n = nk[0];
    let k = nk[1];
    let mut a = read_vec::<i64>();
    let (mut s, mut t): (Vec<i64>, Vec<i64>) = a.iter().partition(|&e| *e >= 0);
    const DIV: i64 = 1000000007;
    s.sort();
    t.sort();
    a.sort_by_key(|e| e.abs());

    let is_certainly_negative = s.len() == 0 && k % 2 == 1;

    let ans: i64 = if n == k {
        a.iter()
            .fold(1, |acc, e| (acc * e).rem_euclid(DIV))
    } else if is_certainly_negative {
        a.iter()
            .take(k)
            .fold(1, |acc, e| (acc * e).rem_euclid(DIV))
    } else {
        let init = if k % 2 == 1 { s.pop().unwrap() } else { 1 };
        let mut products: Vec<i64> = vec![];
        let mut s_products = s.rchunks(2).map(|e| e.iter().product()).collect();
        let mut t_products = t.chunks(2).map(|e| e.iter().product()).collect();
        products.append(&mut s_products);
        products.append(&mut t_products);
        products.sort_by_key(|&e| std::cmp::Reverse(e));
        (
            init * products.iter()
                .take(k / 2)
                .map(|e| e.rem_euclid(DIV))
                .fold(1, |acc, e| (acc * e).rem_euclid(DIV))
        ).rem_euclid(DIV)
    };

    println!("{}", ans);
}

fn main() {
    e_multiplication_4();
}


Measured memory_bytes: 7740
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int n;
  string s;
  cin >> n >> s;
  int count_R = 0, count_W = 0;
  rep(i, n) {
    if (s[i] == 'R') count_R++;
    if (s[i] == 'W') count_W++;
  }
  int ans = 0;
  rep(i, count_R) {
    if (s[i] == 'W') ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3740
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,q) for(int i = 0; q > i; i++)
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> lst;
  rep(i,N){
    int tmp; cin >> tmp;
    lst.push_back(tmp);
  }
  //N+1 - K
  sort(lst.begin(),lst.end());
  int min = 1000000000;
  rep(i,N+1-K){
    int tmpp = lst[i+K-1]-lst[i];
    if(min > tmpp) min = tmpp;
  }
  cout << min << endl;
}

Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <set>


int main()
{
	int N, K;
	std::cin >> N >> K;

	int R, S, P;
	std::cin >> R >> S >> P;

	std::string T;
	std::cin >> T;

	std::string Best(T);	// K回前・・・の条件を考えない時の手

	for (int i = 0; i < N; ++i) {
		switch (T[i]) {
		case 'r':
			Best[i] = 'p';
			break;

		case 's':
			Best[i] = 'r';
			break;

		case 'p':
			Best[i] = 's';
			break;
		}
	}

	int score = 0;

	// K回前・・・の条件を考えて手を直す。
	for (int i = 0; i < N; ++i) {

		if ((K <= i) && (Best[i] == Best[i - K])) {
			// K回前の手と同じなら、K回前とK回後と違う手を出す。

			if ((i + K) < N) {
				if (Best[i - K] == Best[i + K]) {
					Best[i] = T[i];
				}
				else {
					Best[i] = 'r' + 'p' + 's' - Best[i - K] - Best[i + K];
				}

			}
			else {
				Best[i] = T[i];
			}
		}
		else {
			// 勝ち
			switch (Best[i]) {
			case 'r':
				score += R;
				break;

			case 's':
				score += S;
				break;

			case 'p':
				score += P;
				break;
			}
		}
	}

	std::cout << score << std::endl;

	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

#define HASH_LEN 1024

typedef struct {
    int x, y;
} point_t;

typedef struct _hash_element hash_element_t;
struct _hash_element {
    void *value;
    hash_element_t *next;
};

hash_element_t *_hash[HASH_LEN];
hash_element_t _hashelm[HASH_LEN];
int _hashelm_index;

void hash_init() {
    int i;
    for (i = 0; i < HASH_LEN; i++) {
        _hash[i] = NULL;
    }
    _hashelm_index = 0;
}

hash_element_t *hash_new_element(void *value) {
    hash_element_t *elm = &_hashelm[_hashelm_index++];
    elm->value = value;
    return elm;
}

int hash_star(int x, int y) {
    return (x * 33 + y) & (HASH_LEN - 1);
}

void hash_set_star(point_t *star) {
    int h;
    hash_element_t *elm;
    
    h = hash_star(star->x, star->y);
    elm = hash_new_element((void*)star);
    elm->next = _hash[h];
    _hash[h] = elm;
}

point_t *hash_get_star(int x, int y) {
    int h;
    hash_element_t *elm;
    point_t *p;

    h = hash_star(x, y);
    elm = _hash[h];
    while (elm != NULL) {
        p = (point_t*)elm->value;
        if (p->x == x && p->y == y) return p;
        elm = elm->next;
    }
    return NULL;
}


point_t target[200], offset[200], stars[1000];

int main(void) {
    int m, n, i, j;

    while (scanf("%d", &m) != EOF && m) {
        hash_init();
        point_t *o, *s;

        for (i = 0; i < m; i++) {
            scanf("%d%d", &(target[i].x), &(target[i].y));
            if (i == 0) {
                o = &target[i];
            }
            else {
                offset[i].x = target[i].x - o->x;
                offset[i].y = target[i].y - o->y;
            }
        }
        scanf("%d\n", &n);
        for (i = 0; i < n; i++) {
            scanf("%d%d", &(stars[i].x), &(stars[i].y));
            hash_set_star(&stars[i]);
        }

        for (i = 0; i < n; i++) {
            s = &stars[i];
            for (j = 1; j < m; j++) {
                if (hash_get_star(s->x + offset[j].x, s->y + offset[j].y) == NULL) break;
            }
            if (j == m) {
                printf("%d %d\n", s->x - o->x, s->y - o->y);
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 632
#include<bits/stdc++.h>
using namespace std;
#define C getchar()
inline int read() {
	int num = 0;
	char c = C;
	for(;c<'0' || c>'9';c=C);
	for(;c>='0' && c<='9';c=C) num = (num << 1) + (num << 3) + c - 48;
	return num;
}

int n,k,q;
int a[110000];
int f[110000][25];

int main() {
	
	n = read();
	for(int i=1;i<=n;++i) a[i] = read();
	k = read(),q = read();
	a[n + 1] = 2e9;
	int now = 1;
	
	for(int i=1;i<=n;++i) {
		while (a[now] - a[i] <= k) ++ now;
		f[i][0] = now - 1;
	}
	
	for(int i=1;1<<i<=n;++i) {
		for(int j=n;j>=1;--j) { 
			f[j][i] = f[f[j][i - 1]][i - 1];
		}
	}
	
	for(int i=1;i<=q;++i) {
		int x = read(),y = read();
		if (x > y) swap(x , y);
		int j = 20,ans = 0;
		for(;1 << j > n;--j);
		
		for(;j>=0;--j) while (f[x][j] < y) x = f[x][j],ans += 1 << j;
		printf("%d\n",ans + 1);
	}
	
	return 0;
} 

Measured memory_bytes: 11520
import Foundation

func readFourInts(separator: String.Element = " ") -> (a: Int, b: Int, c: Int, d: Int) {
    let ints = readLine()!.split(separator: separator).map { Int($0)! }
    return (a: ints[0], b: ints[1], c: ints[2], d: ints[3])
}

func mainC() {
    let (A, B, H, M) = readFourInts()

    let times = H * 60 + M
    let Adgree = (Double(times) * 0.5).truncatingRemainder(dividingBy: 360)
    let Bdgree = (Double(times) * 6).truncatingRemainder(dividingBy: 360)

    let diff = (Adgree - Bdgree) * Double.pi / 180.0

    let result = Double(A * A + B * B) - 2 * Double(A * B) * cos(diff)
    print(result.squareRoot())
}
mainC()

Measured memory_bytes: 13976
#include<stdio.h>
int main()
{
   int j,N,A[100],count,tmp;
   int flag;
   scanf("%d",&N);
for(j = 0; j < N; j++){
   scanf("%d",&A[j]);
}
flag = 1;
while(flag == 1){
    flag = 0;
       for(j = N-1; j >= 1; j--){
           if(A[j] < A[j-1]){
               tmp = A[j];
               A[j] = A[j-1];
               A[j-1] = tmp;
               count++;
               flag = 1;
           }
       }
   } 
   for(j = 0; j < N; j++){
   printf("%d",A[j]);
   if(j < N-1)
   printf(" ");
   }
   printf("\n");
   printf("%d\n",count);
   return 0;
}


Measured memory_bytes: 2104
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var s = Console.ReadLine().Trim();

        var wins = s.Count(x => x == 'o');
        Console.WriteLine(wins + 15 - s.Length >= 8 ? "YES" : "NO");
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long 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 {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= 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 {
		mint res(*this);
		return res /= a;
	}

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

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////
/*
ll D = 365;
ll T = 26;//タイプ数
vll c(T + 1);
vvll s(D + 1, vll(T + 1));

vvll last(D + 1,vll(T+1,0));

ll score(vll t) {

	repn(i, D) {
		repn(j, T) {
			if (t[i] == j) { last[i][j] = i; }
			else { last[i][j] = last[i - 1][j]; }

			cout << i << " " << j << last[i][j] << endl;
		}
	}

	ll ret = 0;
	repn(i, D) {
		ret += s[i][t[i]];
		repn(j, T) {
			ret -= c[j] * (i - last[i][j]);
		}
	}

	return ret;
	
}
*/


int main() {
	//cin >> D;
	//repn(i, T) cin >> c[i];
	//repn(i, D)repn(j, T) cin >> s[i][j];

	//vll ans(D + 1);
	
	//repn(i, D) {
		//ll id = 1;
		//repn(j, T) {
			//if (s[i][id] < s[i][j]) { id = j; }
			//}
		//ans[i] = id;
	//}

	//repn(i, D) {
		//cout << 1; if (i != D) { cout << endl; }
	//}

	repn(i, 365) { cout << 1 << endl; }

	//cout << score(ans) << endl;
	
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
  
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
 
#define pb emplace_back
#define fi first
#define se second

using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
 
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-8;
const ll MOD = 1e9+7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
 
// head

struct Mod{
  unsigned n;
  Mod(){}
  Mod( ll x ){
    if( x < 0 ) n = x%MOD+MOD;
    else n = x%MOD;
  }
};
Mod operator + ( Mod a  , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a  , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a  , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
  Mod res = 1;
  while( k ){
    if( k & 1 ) res *= x;
    k /= 2;
    x *= x;
  }
  return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
  ll d = a;
  if( b != 0 ){
    d = extgcd( b , a % b , y , x );
    y -= a / b * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
// Mod inv( Mod a ){ return modpow( a , MOD-2 ); }
Mod operator / ( Mod a  , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }


int n, x[3], s;
int a, b, c;

Mod dp[64][PW(18)];


bool check( int mask ){
  if( mask & PW(c) ){
    if( mask & PW(c+b) ){
      if( mask & PW(c+b+a) ){
	return true;
      }
    }
  }
  return false;
}

int main(){

  scanf( "%d" , &n );
  a = in(); s += a;
  b = in(); s += b;
  c = in(); s += c;

  dp[0][1] = 1;

  Mod ans = 0;
  REP( i , n ) REP( j , PW(s+1) ) if( dp[i][j].n != 0 ){
    FOR( k , 1 , 11 ){
      int ne = j * PW(k) + 1;
      ne = ne & ( PW(s+1) - 1 );
      if( check(ne) ){
	ans += dp[i][j] * modpow( 10 , n-1-i );
      } else {
	dp[i+1][ne] += dp[i][j];
      }
    }
  }

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


Measured memory_bytes: 37632
# coding: utf-8
# Your code here!
n = int(input())
K = int(input())

def make_list(n):
    N = []
    while(n>0):
        N.append(n%10)
        n = n //10
    N.reverse()
    return N

N = make_list(n)
m = len(N)
dp = [[[ 0 for k in range(K+1)] for j in range(2)] for i in range(m)]  
#dp[i][j][k]:上からi桁目で、j=0:nのi桁目までと等しくない,j=1:等しい、0でない数字がk個であるものの個数
dp[0][0][0] =  1 #x = 0
dp[0][0][1] = N[0] - 1 #0 < x < N[0]
dp[0][1][0] = 0
dp[0][1][1] = 1 #x = N[0]

for i in range(1,m):
    dp[i][0][0] = 1 #i桁目まで全部0
    #dp[i][1][0] = 0:最上位が0はありえない
    for k in range(1,K+1):
        if N[i] == 0:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k]
        else:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][1][k-1] * (N[i] - 1)
            dp[i][1][k] = dp[i-1][1][k-1]
#print(dp)
print(dp[m-1][1][K] + dp[m-1][0][K])


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long X, long long Y, long long A, long long B, long long C, std::vector<long long> p, std::vector<long long> q, std::vector<long long> r){
    sort(all(p), greater<i64>());
    sort(all(q), greater<i64>());
    sort(all(r), greater<i64>());
    vector<i64> a;
    rep(i, X) a.push_back(p[i]);
    rep(i, Y) a.push_back(q[i]);
    rep(i, C) a.push_back(r[i]);
    sort(all(a), greater<i64>());
    i64 ans = 0;
    rep(i, X+Y) ans += a[i];
    cout << ans << endl;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    std::vector<long long> p(A);
    for(int i = 0 ; i < A ; i++){
        scanf("%lld",&p[i]);
    }
    std::vector<long long> q(B);
    for(int i = 0 ; i < B ; i++){
        scanf("%lld",&q[i]);
    }
    std::vector<long long> r(C);
    for(int i = 0 ; i < C ; i++){
        scanf("%lld",&r[i]);
    }
    solve(X, Y, A, B, C, std::move(p), std::move(q), std::move(r));
    return 0;
}


Measured memory_bytes: 8432
def main():
    s = int(input())
    root = int(pow(s,0.5))
    temp = 0
    for i in reversed(range(1,root+1)):
        if s%i == 0:
            temp = i
            break
    ans = temp - 1 + (s//temp) - 1

    print(ans)






if __name__ == "__main__":
    main()


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

using namespace std;


int main()
{
        int mod,i,s=0;
        cin>>mod;
        for(i=1;i<=1000000;i++)
        {
            s=s*10+7;
            s%=mod;
            if(s) continue;
            cout<<i<<endl;
            return 0;
        }
        cout<<"-1"<<endl;

        return 0;
}

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

int main() {
    int H,W;
    cin >> H >> W;
    string S[H];
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }
    const int dx[4] = {1, 0, -1, 0};
    const int dy[4] = {0, 1, 0, -1};
    
    int flag = 0;
    for (int i = 0; i < H; ++i ){
        for (int j = 0; j < W; ++j ){
            if (S[i][j] == '.') {
                continue;
            }
            int num = 0;
            for (int d = 0; d < 4; ++ d){
                int ni = i + dy[d];
                int nj = j + dx[d];
                if ( ni < 0 or H <= ni) {
                    continue;
                }
                if ( nj < 0 or W <= nj) {
                    continue;
                }
                if ( S[ni][nj] == '#' ) {
                    num = 1;
                }
            }
            if ( num == 0 ){
                flag = 1;
            }
        }
    }
    if (flag == 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<ll> h(N);
    for(int i=0; i<N; ++i) {
        cin >> h[i];
    }
    stack<ll> st;
    vector<ll> l(N), r(N);
    for(int i=0; i<N; ++i) {
        while(!st.empty() && h[st.top()] >= h[i]) {
            st.pop();
        }
        l[i] = st.size() == 0 ? 0 : st.top()+1;
        st.push(i);
    }
    while(!st.empty()) {
        st.pop();
    }
    for(int i=N-1; i>=0; --i) {
        while(!st.empty() && h[st.top()] >= h[i]) {
            st.pop();
        }
        r[i] = st.size() == 0 ? N : st.top();
        st.push(i);
    }
    ll res = 0;
    for(int i=0; i<N; ++i) {
        res = max(res, h[i] * (r[i] - l[i]));
    }
    cout << res << endl;
}


Measured memory_bytes: 6036
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

class CMaximalValue {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n;
        in>>n;
        int ans=0;
        vector<int> b(n+1,100001);
        Fr(i,n-1) in>>b[i];
        fr(i,n){
            ans+=min(b[i],b[i+1]);
        }
        out<<ans<<endl;
    }
};

int main() {
    CMaximalValue solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <iterator>      // std::next prev


using namespace std;


int main() {   
    std::ios::sync_with_stdio(false);
	string a,b;
	cin>>a>>b;
	
	int al = a.length();
	int bl = b.length();
	if(al<bl)
	{
		cout<<"LESS";
	}
	else if(al>bl)
	{
		cout<<"GREATER";
	}
	else
	{
		for(int i = 0 ; i < al ; i++)
		{
			char ai = a[i];
			char bi = b[i];
			int a_i = ai - '0';
			int b_i = bi - '0';
			if(ai<bi)
			{
				cout<<"LESS";
				return 0;
			}
			else if(ai>bi)
			{
				cout<<"GREATER";
				return 0;
			}
		}
		cout<<"EQUAL";
	}
	return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
ans[0] = sum(a[::2]) - sum(a[1::2])
for i in range(1,n):
  ans[i] = a[i-1] * 2 - ans[i-1]
print(*ans)

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

int main() {
  string S;
  cin >> S;
  int a[26];
  
  for(int i=0; i<S.size(); i++){
    for(int j=0; j<26; j++){
     if(S[i]==97+j) {
       a[j]=1;
       break;
     }
    }
  }    
  
  int count=0;
  char moji='z';
  for(int j=0;j<26;j++){
     if(a[j]==1) count++;
    
     else{
       moji= j+97;
       break;
     }
    }
  
  if(count==26) cout << "None" << endl;
  else cout << moji << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=65537;
const int mo=65537;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head


const int N = 510;
int A[N][N],p[N][N];
/* 合并子问题 */
void merge(int n)
{
    /*
     * n 为偶数时，比赛 n - 1 天
     * n 为奇数时，比赛 n 天
     */
    int days = n&1 ? n  : n-1;
    /*
     * 中间值，若n为奇数，则使 m = (n / 2) + 1,
     * 即，前半部分不小于后半部分
     */
    int m = (int)ceil(n / 2.0);
    int passed_days = m& 1? m : m - 1;    /* 已经安排的天数 */

    /*
     *  通过前 n/2 的比赛安排，构造后n/2的比赛安排
     *  如果 n 为奇数，则会产生一个虚拟选手
     */
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= passed_days; j++)
        {
            if (A[i][j] != 0)   /* 如果 i 号在第 j 天有对手 */
            {
                /*
                 * 那么，(i + m) 号在第 j 天的对手为 i号的
                 * 对手往后数 m 号
                 */
                A[i + m][j] = A[i][j] + m;
            }
            else   /* 如果 i 号在第 j 天没有对手*/
            {
                /*
                 * 那么就让 i 号和 （i + m）号互为对手
                 */
                A[i + m][j] = i;
                A[i][j] = i + m;
            }
        }
    }

    int add_one = 0;        /*标志子问题是否是奇数，如果是的话构造增量加1 */
    if (A[1][passed_days] == m + 1)
        add_one = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = passed_days + 1, count = 0; j <= days; j++, count++)
        {
            /*
             * 构造i 号在第 j 天的对手
             */
            int r_value = (count + (i - 1)  + add_one) % m + m + 1;
            A[i][j] = r_value;
            A[r_value][j] = i;
        }
    }
    if ( n & 1 )            /* 如果 n 为奇数，消除虚拟的选手 */
    {
        for (int i = 1; i <= 2 * m; i++)
        {
            for (int j = 1; j <= days; j++)
                if (A[i][j] == n + 1)
                    A[i][j] = 0;        /* A[i][j] = 0 ,表示 i 号选手在第 j 天没有比赛 */
        }
    }
}

/* 分治求解循环赛问题 */
void tournament(int n)
{
    if (n <= 1)
        return;
    else if (n == 2)        /* 2 个选手 */
    {
        A[1][1] = 2;
        A[2][1] = 1;
    }
    else
    {
        tournament((int)ceil(n / 2.0));
        merge(n);
    }
}

int main() {
    int n;
    scanf("%d",&n);
    if (n%2==1) {
        if (n==1) {
            puts("Yes\n1");
        } else {
            puts("No");
        }
        return 0;
    }
    tournament(n);
    for (int i=0;i<n;i++) p[i][i]=1;
    for (int i=1;i<=n-1;i++) {
        for (int j=1;j<=n;j++) if (A[j][i]>j) {
            p[j-1][A[j][i]-1]=i+1;
            p[A[j][i]-1][j-1]=n+i;
        }
    }
    puts("Yes");
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) printf("%d%c",p[i][j]," \n"[j==n-1]);
}



Measured memory_bytes: 5204
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void calc(int n, int[] a) {
    ulong[int] d;
    ulong lo, hi; // 重複文字の位置
    foreach (i, c; a)  {
        if (c in d) {
            lo = d[c];
            hi = i;
            break;
        }
        d[c] = i;
    }

    int span = cast(int)(hi - lo);
    foreach (k; 1..n+2) {
        long ans = nck(n + 1, k) - nck(n - span, k - 1);
        if (ans < 0) ans += MOD;
        writeln(ans);
    }
}

void main() {
    int n = readint;
    auto a = readints;

    initFactTable(n + 1);
    calc(n, a);
}

const MOD = 10^^9 + 7;

long[] fact; // 階乗
long[] factInv; // 階乗の逆元

void initFactTable(int n) {
    fact = new long[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = i * fact[i - 1] % MOD;

    factInv = new long[n + 1];
    factInv[n] = modPow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        factInv[i] = factInv[i + 1] * (i + 1) % MOD;
}

long modPow(long x, long k, long m) {
    if (k == 0) return 1;
    if (k % 2 == 0) return modPow(x * x % m, k / 2, m);
    return x * modPow(x, k - 1, m) % m;
}

long nck(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return (fact[n] * factInv[k] % MOD) * factInv[n - k] % MOD;
}


Measured memory_bytes: 11580
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n;
char s[N];

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>(s+1);
	int cnt=0;
	for(int i=1;i<=n;i++){
		cnt++;
		while(i+1<=n&&s[i]==s[i+1]){
			i++;
		}
	}
	cout<<cnt<<'\n';
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) (1e9 + 7);
//const ll MOD = 998244353;
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

//------------------------------------------------------

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

    int n;
    cin >> n;
    int h[100010];
    rep(i, n) cin >> h[i];
    h[0]--;

    rep(i, n - 1) {
        if (h[i + 1] == h[i]) continue;
        else if (h[i + 1] - h[i] >= 1) h[i + 1]--;
        else {
            Yes(false);
            dbg3(h, n);
            return 0;
        }
    }
    Yes(true);
    dbg3(h, n);

    return 0;
}



Measured memory_bytes: 640
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-9
# define MOD 1000000000
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Out(int a) {
    if(a<0) {putchar('-'); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
const int N=105;
//Code begin...


int main ()
{
    LL a, b;
    scanf("%lld%lld",&a,&b);
    puts(abs(a-b)<=1?"Brown":"Alice");
    return 0;
}


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

int main(){

	int n;
	double w, h;

	while(scanf("%d, %lf, %lf", &n, &w, &h) != EOF){
		if(w/(h*h) >= 25) cout << n << endl;	
	}

	return 0;

}

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

int N, M;
vector<vector<int>> G;
vector<int> visited;

int dfs(int d, int cur) {
  if(d == N - 1) return 1;
  int ret = 0;
  for(auto p : G[cur]) {
    if(visited[p]) continue;
    visited[p] = true;
    ret += dfs(d + 1, p);
    visited[p] = false;
  }
  return ret;
}

int main() {
  cin >> N >> M;
  G.resize(N);
  visited.resize(N);
  rep(i, 0, M) {
    int a, b; cin >> a >> b; a--, b--;
    G[a].push_back(b); G[b].push_back(a);
  }
  visited[0] = true;
  cout << dfs(0, 0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<vector>
#include<map>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	while(cin>>n)
	{
		string *a=new string [n];
		int i,j;
		for(i=0;i<n;i++)
			cin>>a[i];
		bool flag=0;
		for(i=0;i<n-1;i++)
		{
			if(a[i][a[i].size()-1]!=a[i+1][0])
				flag=1;
		}
		map<string,int>mp;
		for(i=0;i<n;i++)
			mp[a[i]]++;
		map<string,int>::iterator it;
		bool flag2=0;
		for(it=mp.begin();it!=mp.end();it++)
			if(it->second>=2)
			{
				flag2=1;
				break;
			}
		if(flag==0&&flag2==0)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
		delete [] a;
	}
	return 0;
}


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

int powx(long long int x,long long int y){
  int j;
  int a;
  a=1;
  for(j=1;j<y+1-x;j++){
   a=a*10;
  }
  return(a);
}


int main(){

 long long int N,M;
  scanf("%lld %lld",&N,&M);

/*
  char A[];
  scanf("%s",A);
  */

  
  long long int s[M+1],c[M+1],che[N+1];
  long long int i;
  for(i=1;i<=M;i++){
   scanf("%lld %lld",&s[i],&c[i]);
   }
  
  long long int A;
  A=0;
  for(i=1;i<=N;i++){
    che[i]=-1;
   }

  for(i=1;i<=M;i++){

    if(che[s[i]]==-1){
      che[s[i]]=c[i];
      A += c[i]*powx(s[i],N);
    }
    else if( che[s[i]] != c[i]){
      printf("-1");
      return(0);
    }
    else{}


   }  
  if(N == 1 && A == 0){
    printf("0");
  }

  else if( che[1]==0){
    printf("-1");
  }
  else{
    if(che[1]==-1){
    printf("%lld",A+powx(1,N) );
    }
    else{
    printf("%lld",A );
    }
  }





 return(0);
 }


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 1e5;
int n, k;
ll c[N+1];
bool z[N+1];

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  for (int i=2; i<=N; ++i)if(!z[i])for(int j=i*2; j<=N; j+=i) z[j]=true;
  cin >> n >> k;
  FOR(i, 1, k+1) c[i] = modPow(k/i, n);
  FOR(i, 2, k+1)if(!z[i])FOR(j, 1, k/i+1) c[j] -= c[j*i];
  ll ans = 0;
  FOR(i, 1, k+1) ans += c[i]%MOD*i%MOD;
  cout << (ans%MOD+MOD)%MOD << endl;
}

Measured memory_bytes: 4472
#include <bits/stdc++.h>
#define LL long long

using namespace std;

template<typename tp> inline void read(tp &x) {
	x = 0; register char c = getchar(); register bool f = 0;
	for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if (f) x = -x;
}

const int N = 100010, MOD = 1e9 + 7;

int f[N], n, p[N][26];
char s[N];

int main() {
    read(n);
    scanf("%s", s + 1);
    for (int i = 0; i < 26; ++i) {
        p[n + 1][i] = 1;
    }
    for (int i = n; i >= 1; --i) {
        int k = s[i] - 'a';
        for (int j = 0; j < 26; ++j) {
            p[i][j] = p[i + 1][j];
        }
        p[i][k]++;
    }
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        LL cache = 1;
        for (int j = 0; j < 26; ++j) {
            if (j == s[i] - 'a') continue;
            cache *= p[i][j];
            cache %= MOD; 
        }
        ans += cache;
        ans %= MOD;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 10624
#include <bits/stdc++.h>
using namespace std;
int N,M;


int main() {
  ios::sync_with_stdio(false);
  string in;
  cin >> in;
  if(in[0] == 'A') cout << "T";
  if(in[0] == 'C') cout << "G";
  if(in[0] == 'G') cout << "C";
  if(in[0] == 'T') cout << "A";

  return 0;

}


Measured memory_bytes: 256
#include <iostream>

int main(int argc, char *argv[]) {
	int a, b;
	char o;
	std::cin >> a >> b;
	if (a > b) std::cout << "a > b" << std::endl;
	else if (a < b) std::cout << "a < b" << std::endl;
	else std::cout << "a == b" << std::endl;
	return 0;
}

Measured memory_bytes: 1160
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

string s;

int main()
{
	cin>>s;
	int n=s.size();
	
	for(int i=0; i<n; i++)
	{
		if((i+1)%2==1) // odd 
		{
			if(s[i]!='R' && s[i]!='U' && s[i]!='D')
			{
				puts("No");
				return 0;
			}
		}
		else // even 
		{
			if(s[i]!='L' && s[i]!='U' && s[i]!='D')
			{
				puts("No");
				return 0;
			}
		}
	}
	
	puts("Yes");
	return 0;
}

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

int main() {
  int n, k, arr[200000], curr_max;
  cin >> k >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  curr_max = k - (arr[n-1]-arr[0]);
  for (int i = 0; i < n-1; i++) {
    curr_max = max(curr_max, arr[i+1]-arr[i]);
  }
  cout << k - curr_max;
  return 0;
}

Measured memory_bytes: 1024
N=int(input())
mod=10**9+7
DP=[[0]*256 for i in range(N+2)]
NO=[False]*256
S='AGCT'
T=0
for a in range(4):
  for b in range(4):
    for c in range(4):
      for d in range(4):
        T=list(S[a]+S[b]+S[c]+S[d])
        NO[a*64+b*16+c*4+d]=('AGC' in ''.join(T))
        for l in range(3):
          T[l],T[l+1]=T[l+1],T[l]
          NO[a*64+b*16+c*4+d]|=('AGC' in ''.join(T))
          T[l],T[l+1]=T[l+1],T[l]
DP[0][-1]=1
for i in range(N+1):
  for j in range(256):
    if NO[j]:
      DP[i][j]=0
      continue
    for k in range(4):
      DP[i+1][(j*4+k)&255]=(DP[i+1][(j*4+k)&255]+DP[i][j])%mod
P=0
for i in range(256):
  P+=DP[N][i]
print(P%mod)

Measured memory_bytes: 71728
#include<bits/stdc++.h>//万能头万岁！
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	int a,b,h;
	cin>>a>>b>>h;
	cout<<(a+b)*h/2;
	return 0;
}
//木有钱233 NO_MANEY 奉上

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> grap[100001];
int dp[100001];
int solve(int src){
    if(dp[src]!=-1)return dp[src];
    bool leaf=1;
    int bestLen=0;
    for(auto child:grap[src]){
        leaf=0;
        bestLen=max(bestLen,solve(child));
    }
    return dp[src]=leaf?0:1+bestLen;
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        grap[u].push_back(v);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,solve(i));
    cout<<ans<<endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;

void solve()
{
    int d, t, s;
    cin >> d >> t >> s;

    cout << (t * s >= d ? "Yes" : "No") << endl;
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

#ifdef _DEBUG
    freopen("a-input-1.txt", "r", stdin);
    //freopen("a-output-1.txt", "w", stdout);
#endif

    solve();
    //int t; cin >> t; while(t--) solve();

    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n){ cin >> a[i]; a[i]--; }
  vector<int> idx(n);
  rep(i,n){ idx[a[i]] = i; }

  set<int> st;
  ll ans = 0;
  for(int x=n-1; x>=0; x--){
    int i = idx[x];
    ll c = 0;
    st.insert(i);
    vector<int> l(2,-1);
    vector<int> r(2,n);
    auto it = st.find(i);
    rep(j,2){
      if(it==st.begin())break;
      it--;
      l[j] = *it;
    }
    it = st.find(i);
    rep(j,2){
      it++;
      if(it==st.end())break;
      r[j] = *it;
    }
    vector<int> ls(2); ls[0] = i-l[0]; ls[1] = l[0]-l[1];
    vector<int> rs(2); rs[0] = r[0]-i; rs[1] = r[1]-r[0];
    c = (ll)ls[0]*rs[1] + (ll)ls[1]*rs[0];
    ans += c*(x+1);
  }

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


Measured memory_bytes: 5760
import std.stdio,
       std.string,
       std.conv;

void main() {
  int N = readln.chomp.to!(int);
  string[] S;
  bool[] tate;
  for (int i = 0; i < 2; i++) {
    S ~= readln.chomp;
  }
  for (int i = 0; i < N; i++) {
    if (S[0][i] == S[1][i]) {
      tate ~= true;
    }
    else {
      tate ~= false;
      i++;
    }
  }

  long ans = (tate[0] ? 3 : 6);
  for (int i = 1; i < tate.length; i++) {
    long kake;
    if (tate[i]) {
      kake = (tate[i - 1] ? 2 : 1);
    }
    else {
      kake = (tate[i - 1] ? 2 : 3);
    }
    ans = (ans * kake) % 1000000007;
  }

  ans.writeln;
}


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

using namespace std;

const int nmax = 1e9 + 7;
const long long INF = 1e18;
const double PI = 2 * asin(1);
typedef long long ll;


int main(){
  int N; cin >> N;
  string S; cin >> S;
  int Q; cin >> Q;
  vector <int> K(Q);
  for (int i = 0; i < Q; i++) cin >> K[i];
  
  for (int i = 0; i < Q; i++){
    ll ans = 0;

    ll DP[N + 1][3];
    for (int j = 0; j < 3; j++){
      DP[0][j] = 0;
    }
    
    for (int j = 1; j < N + 1; j++){
      for (int k = 0; k < 3; k++){
        DP[j][k] = DP[j - 1][k];
      }

      if (j - K[i] > 0){
        if (S[j - K[i] - 1] == 'D'){
          DP[j][2] -= DP[j][1];
          DP[j][0]--;
        }else if (S[j - K[i] - 1] == 'M'){
          DP[j][1]--;
        }
      }
      
      if (S[j - 1] == 'D'){
        DP[j][0]++;
      }else if(S[j - 1] == 'M'){
        DP[j][1]++;
        DP[j][2] += DP[j][0];
      }else if(S[j - 1] == 'C'){
        ans += DP[j][2];
      }
    }
    
    cout << ans << endl;
  }
  
  return 0;
}


Measured memory_bytes: 24836
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

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

  ll x, y;
  cin >> x >> y;
  cout << __gcd(x, y) << endl;
  return 0;
}



Measured memory_bytes: 3184
//AnkitCode99 here....
//every ups and downs matter!

#include<bits/stdc++.h>
#define endl "\n"
#define Ryuga ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr)
typedef long long int ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)

using namespace std;

const ll sz=1e5+5;
const ll szz=1e6+6;
const ll mod=1e9+7;

int main()
{
	Ryuga;

	

	clock_t startTime=clock();

	ll x;
	cin>>x;
	ll p=100,y=0;

	while(p<x)
	{
		p+=p/100;
		y++;
	}
	cout<<y<<endl;


	cerr << endl <<setprecision(20)<< double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

}//Goodbye...

Measured memory_bytes: 3776
#include<stdio.h>
#include<string.h>

int main(){
	char a[11],b[11],c[11];
	int d,e;
	
scanf("%s %s\n",&a,&b);
scanf("%d %d\n",&d,&e);	
scanf("%s",&c);

	if(strcmp(a,c)==0){
		printf("%d %d",d-1,e);
	}
	else if(strcmp(b,c)==0){
		printf("%d %d",d,e-1);

	}
return 0;

}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int a[200005],c[200005];
int main(){
	int n,k,t,s;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	    cin>>a[i];
	for(int j=1;j<=k;j++){
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++){
			int aa=max(1,i-a[i]),bb=min(n+1,i+a[i]+1);
			c[aa]++;
			c[bb]--;
		}
		s=0;
		bool f=true;
		for(int i=1;i<=n;i++){
			a[i]=s+=c[i];
			if(a[i]<n) f=false;
		}
		if(f==true) break;
	}
	for(int i=1;i<=n;i++)
	    cout<<a[i]<<' ';
	return 0;
}

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

int main(void) {
	string str1, str2;
	int i1, i2;	
	vector<char> v;
	vector<char>::iterator it;
	int n; 
	cin >> n;
	while (n--) {
		cin >> str1 >> str2;
		if (str1.length() > 80 || str2.length() > 80) {
			cout << "overflow\n"; 
			continue;
		}
		int up = 0, n1, n2;
		char c;
		v.clear();
		if (str1.length() < str2.length())
			swap(str1, str2);
		for (i1 = str1.length() - 1, i2 = str2.length() - 1;
				i2 >= 0; i1--, i2--) {
			n1 = str1[i1] - '0';
			n2 = str2[i2] - '0';
			n1 = n1 + n2 + up;
			up = n1 / 10;
			n1 = n1 % 10;
			c = (char)(n1 + '0');
			v.push_back(c);
		}
		while (i1 >= 0) {
			n1 = str1[i1] - '0';
			n1 = n1 + up;
			up = n1 / 10;
			n1 = n1 % 10;
			c = (char)(n1 + '0');
			v.push_back(c);
			i1--;
		}
		if (up == 1) {
			v.push_back('1');
		}
		if (v.size() > 80) {
			cout << "overflow" << endl;
			continue;
		}
		reverse(v.begin(), v.end());
		for (it = v.begin(); it != v.end(); it++) {
			cout << *it;
		}
		cout << endl;
	}
}


Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    int A;
    scanf("%d",&A);
    int B;
    scanf("%d",&B);
    printf("%d\n", max({A+B, A-B, A*B}));
    return 0;
}

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

using namespace std;

typedef long long ll;

#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i < ll(b); i++)
#define FORD(i, a, b) for (ll i = b - 1; i >= ll(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int N;
    cin>>N;
    cout<<(10000-N)%1000<<endl;
}

Measured memory_bytes: 3604
n=int(input())
a=[]
b=[]
for i in range(n):
    s=int(input())
    if s%10==0:
        a.append(s)
    else:
        b.append(s)
b.sort()
if len(b)==0:
    print(0)
else:
    #print(sum(a))
    #print(sum(b[:-1]))
    if sum(b)%10==0:
        print(sum(a)+sum(b[1:]))
    else:
        print(sum(a)+sum(b))


Measured memory_bytes: 3060