akhauriyash/Code-Regression huggingface dataset:
from collections import Counter
n = int(input())
v = list(map(int,input().split()))
a = Counter(v[::2])
b = Counter(v[1::2])
a = a.most_common()
b = b.most_common()
a1 = a[0][1]
b1 = b[0][1]
if len(a) == 1:
    a2 = 0
else:
    a2 = a[1][1]
if len(b) == 1:
    b2 = 0
else:
    b2 = b[1][1]
if a[0][0] != b[0][0]:
    print(n-(a1+b1))
else:
    print(min(n-(a1+b2),n-(a2+b1)))

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

int main() {
int n;
cin >> n;
vector<int>d(n);
for(int i=0; i<n; i++){
    cin >> d[i];
}
int sum =0;
for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
        sum += d[i] * d[j];
    }
}
    cout << sum << endl;


}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List

main = do
    [h,w] <- map read . words <$> getLine
    a <- replicateM h (map read . words <$> getLine)
    let moves = solve h w (zip [1..h] a)
    print $ length moves
    forM moves (putStrLn . unwords . map show) 


solve :: Int -> Int -> [(Int,[Int])] -> [[Int]]
solve h w list = rmoves ++ lastmoves
    where tuples = map (calcraw w) list
          rmoves = concatMap fst tuples
          rparities = map snd tuples
          (lastmoves,lparity) = calcCol h (w,rparities)

calcraw :: Int -> (Int,[Int]) -> ([[Int]],Int)
calcraw width (y,raw) = (reverse rms, p)
    where (rms,p,col) = foldl (move y width) ([],0,1) raw

move :: Int -> Int -> ([[Int]],Int,Int) -> Int -> ([[Int]],Int,Int)
move y width (moves, parity, column) elem | column < width = if mod (parity + elem) 2 == 0
                                                             then (moves,0,column+1)
                                                             else ([y,column,y,column+1]:moves, 1, column+1)
                                          | otherwise = if mod (parity + elem) 2 == 0
                                                        then (moves,0,column+1)
                                                        else (moves,1,column+1)

moveCol :: Int -> Int -> ([[Int]],Int,Int) -> Int -> ([[Int]],Int,Int)
moveCol x height (moves, parity, raw) elem | raw < height = if mod (parity + elem) 2 == 0
                                                                 then (moves,0,raw+1)
                                                                 else ([raw,x,raw+1,x]:moves, 1, raw+1)
                                              | otherwise = if mod (parity + elem) 2 == 0
                                                            then (moves,0,raw+1)
                                                            else (moves,1,raw+1)
calcCol :: Int -> (Int,[Int]) -> ([[Int]],Int)
calcCol height (x,col) = (reverse rms, p)
    where (rms,p,raw) = foldl (moveCol x height) ([],0,1) col

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#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 CCitySavers {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n;
        in>>n;
        vector<int> a(n+1),b(n);
        for(auto& i:a) in>>i;
        for(auto& i:b) in>>i;
        ll ans=0;
        fr(i,n){
            int ka=min(a[i],b[i]);
            ans+=ka;
            b[i]-=ka;
            ka=min(a[i+1],b[i]);
            a[i+1]-=ka;
            ans+=ka;
        }
        out<<ans<<endl;
    }
};

int main() {
    CCitySavers solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    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 reprev(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;

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

    cout << (n / 2 + n % 2) << endl;
}


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

int main()
{
    int n;
    cin >> n;
    int a[n] = {};
    for(int i=0; i<n; i++){
        cin >> a[i];
        a[i]--;
    }
    bool check[n] = {};
    int t = a[0];
    int ans = 1;
    while(!check[t]){
        check[t] = true;
        if(t==1){
            cout << ans << endl;
            return 0;
        }
        t = a[t];
        ans++;
    }
    cout << "-1" << endl;
    return 0;
}

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

typedef pair< int, int > pii;

const int N = int(2e5) + 10;
pii dp[N];
string s;
bool mark[N];
vector< int > ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k, c;
    
    cin >> n >> k >> c;
    cin >> s;
    
    vector< int > v;
    
    for(int i = 0 ; i < s.length() ; i++){
        if(s[i] == 'o'){
            v.push_back(i);
        }
    }
    
    int j = 0;
    
    for(int i = 0 ; i < v.size() ; i++){
        while(j + 1 < i && v[i] - v[j + 1] > c){
            j++;
        }
        
        if(v[i] - v[j] <= c){
            dp[v[i]] = {1, -1};
        }else{
            dp[v[i]] = {1 + dp[v[j]].first, v[j]};
        } 
    }
    
    int st = v[v.size() - 1];
    
    vector< int > ve;
    
    while(st != -1){
        mark[st] = true;
        st = dp[st].second;
    }
    
    ve = v;
    int last = ve[ve.size() - 1];
    
    for(int i = 0 ; i < ve.size() ; i++){
        if(!mark[ve[i]]) continue;
        
        if(i == 0){
            if(dp[last].first - 1 < k){
                ans.push_back(ve[i] + 1);
            }
        }else{
            int sum = 0;
            
            if(i != int(ve.size()) - 1){
                sum = dp[last].first - dp[ve[i]].first;
            }
            
            sum += dp[ve[i - 1]].first;
            
            if(sum < k){
                ans.push_back(ve[i] + 1);
            }
            
        }
    }
    
    for(auto u: ans){
        printf("%d\n", u);
    }
    
	return 0;
}


Measured memory_bytes: 5900
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define nl '\n'
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define flood(x) memset(x, 0x3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define dcit cin.sync_with_stdio(0);cin.tie(0);
#define frp(x, y) freopen(x, "r", stdin);freopen(y, "w", stdout);
typedef pair<int, int> pii;
typedef long long ll;

#ifdef LOCAL_PROJECT

#define gc getchar()
#define pc(x) putchar(x)

#endif
#ifndef LOCAL_PROJECT

#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)

#endif

template<typename T> void scani(T &x) {x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printi(T n) {register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);pc(10);}
string nextstring() { string r; register char c=gc;while(c==32||c==10) c = gc;while(!(c==32||c==10)) { r += c;c = gc; }return r; }
char nextgetchar(){ register char c = gc; while(c==32 || c==10) c = gc; return c;}

void prints(string k){ for (int i = 0; i < k.length(); i++)pc(k[i]); }
void scani() {}

template<typename First, typename ... Ints>
void scani(First &arg, Ints&... rest) { scani(arg);scani(rest...); }

int N, W; ll ans=0;  ll dp[100002];
int main(){
    flood(dp);
    scani(N, W);
    dp[0]=0;
    for (int i = 0, v, w; i < N; i++) {
        scani(w, v);
        for (int j = 100000; j >= v; j--) dp[j] = min(dp[j], dp[j-v]+w);
    }
    for (int i = 0; i <= 100000; i++) {
        if(dp[i]<=W)ans=i;
    }
    printi(ans);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int a=0;
char s[5];
int main()
{
    for (size_t i = 0; i < 4; i++) {

        scanf("%s\n",s+i);
        if (s[i]=='+') a++;
        else a--;

        }
        printf("%d\n",a );
        
}


Measured memory_bytes: 256
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

var mod = 998244353;
function mul(a,b){return ((a>>16)*b%mod*65536+(a&65535)*b)%mod;}
function pow(a,n){for(var r=1;n;a=mul(a,a),n>>=1)if(n&1)r=mul(a,r);return r;}

console.log(main());
function main(){
  var n = o.a();
  var ans = pow(3,n);
  var fac = 2, m = n/2;
  var inv = [];
  inv.length = m+2;
  inv[0] = inv[1] = 1;
  for(var i = 0; i < m;){
    ans -= fac;
    fac = mul(mul(fac,(n-i)*2),inv[++i]);
    inv[i+1] = mod-mul(inv[mod%(i+1)|0],(mod/(i+1)|0));
  }
  ans%=mod;
  return ans<0?ans+mod:ans;
}

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

long long int f(long long int i,long long int n){
  return i*n - i*(i-1) + 1;
}

int main(){
  long long int n,k;
  cin >> n >> k;
  long long int cnt = 0;
  for(long long int i=k;i<=n+1;i++){
    cnt += f(i,n);
    cnt %= (long long int)(pow(10,9)+7);
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <string>
#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    string s;
    cin >> s;
    s[5] = ' ';
    s[13] = ' ';
    cout << s << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using P = pair<int, int>;
int main()
{
int n;
const ll t = 200000;
cin >> n;
ll sum = 0;
vector<ll> a(t);
rep(i,n){
    ll l;
    cin >> l;
    a[l]++;
    sum += l;

}

cout << endl;
int q;
cin >> q;
rep(i,q){
    ll b,c;
    cin >> b >> c;
    sum += (c-b)*a[b];
    a[c] += a[b];
    a[b] = 0;
    cout << sum << endl;

}
return 0;
}

Measured memory_bytes: 4824
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct xyz{
  int x,y,z;
  xyz(int x,int y,int z):x(x),y(y),z(z){}
};
ll a,b,c,n;
vector<xyz> v;
bool out(int x,int y,int z){
  if(x<0||x>=a||y<0||y>=b||z<0||z>=c) return true;
    return false;
}

int calc(int x,int y,int z){
  int r=0;
  int ax[]={1,-1,0,0,0,0};
  int ay[]={0,0,1,-1,0,0};
  int az[]={0,0,0,0,1,-1};
  for(int i=0;i<6;i++){
    if(out(x+ax[i],y+ay[i],z+az[i])) continue;
    bool f=false;
    for(int j=0;j<v.size();j++){
      if(v[j].x==x+ax[i]&&v[j].y==y+ay[i]&&v[j].z==z+az[i]) f=true;
    }
    if(!f) r++;
  }
  return r;
}

int main(){
  cin >> a >> b >> c >> n;
  ll ans=(a*b+b*c+c*a)*2;
  ll x,y,z;
  for(int i=0;i<n;i++){
    cin >> x >> y >> z;
    ans+=2*calc(x,y,z)-6;
    v.push_back(xyz(x,y,z));
  }
  cout << ans << endl;
  return 0;
}

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

using ll = long long;

#define for_(i,a,b) for(int i = (a);i < (b);i++)
#define rfor_(i,a,b) for(int i = (b)-1;i >= (a);i--)
#define rep(i,n) for_(i,0,(n))
#define rrep(i,n) rfor_(i,0,(n))

int A, B;

int main(){
	cin.tie(0);
  
  cin>>A>>B;
  
  cout<<(A-1)*(B-1)<<endl;

	return 0;
}


Measured memory_bytes: 888
//https://atcoder.jp/contests/dp/tasks/dp_l
//shauryakr
#include<bits/stdc++.h>
using namespace std;
long long int arr[3005], n;
long long int dp[3005][3005][2];
long long int solve(int start, int ends, int player)
{
    if(start > ends)
    {
        return 0;
    }

    if(dp[start][ends][player] != -1)
        return dp[start][ends][player];

    long long int ans = player?1000000000000000:-1000000000000000;
    if(!player)
    {
        ans = max(solve(start + 1, ends, 1 - player) + arr[start], solve(start, ends-1, 1 - player) + arr[ends]);
    }
    else
    {
        ans = min(solve(start + 1, ends, 1 - player) - arr[start], solve(start, ends-1, 1 - player) - arr[ends]);
    }

    dp[start][ends][player] = ans;
    return ans;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> arr[i];
    }

    memset(dp,-1, sizeof dp);
    cout << solve(0, n-1, 0) << endl;
    return 0;
}

Measured memory_bytes: 141568
import java.util.Scanner;
//
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
//━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
		long n=sc.nextLong();
		int rootN = (int) (Math.sqrt(n));
		long ans=digCount(n);
		for (int i=1;i<=rootN;i++) {
			if (n%i==0) {
				long a=i;
				long b=n/i;
				long bigger =Math.max(a,b);
				long biggerDigCount= digCount(bigger);
				ans =Math.min(ans, biggerDigCount);
			}
		}
		System.out.println(ans);
		
//━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
	}
	//----------------------------------------
	//置き場
//桁数
static long digCount(long n) {
	int res = 0;
	while(n > 0) {
		res ++;
		n /= 10;
		}
	return res;
}
	//----------------------------------------
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please


//たまらず解説をみてお勉強中
int P[100001];

int Find(int A) {
	if (P[A] == A) return A;
	else {
		P[A] = Find(P[A]);
		return P[A];
	}
}

void Union(int A, int B) {
	int a = Find(A);
	int b = Find(B);
	P[b] = a;
}

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


	int N;
	cin >> N;

	pair<int, int> X[100001], Y[100001];
	rep1(i, N) {
		int x, y;
		cin >> x >> y;
		X[i] = make_pair(x, i);
		Y[i] = make_pair(y, i);
	}
	sort(X + 1, X + N + 1);
	sort(Y + 1, Y + N + 1);

	vector<pair<int, pair<int, int>>> eda;

	rep1(i, N - 1) {
		eda.push_back(make_pair(abs(X[i + 1].first - X[i].first), make_pair(X[i].second, X[i + 1].second)));
		eda.push_back(make_pair(abs(Y[i + 1].first - Y[i].first), make_pair(Y[i].second, Y[i + 1].second)));
	}

	sort(eda.begin(), eda.end());

	rep1(i, N) P[i] = i;

	ll kotae = 0;
	for (auto itr : eda) {
		if (Find(itr.second.first) != Find(itr.second.second)) {
			Union(itr.second.first, itr.second.second);
			kotae += itr.first;
		}
	}

	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 6516
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int n, a, b;
    cin>>n;
    cin>>a>>b;
    vector<int> ans(3, 0);
    f(i, n){
        int u;
        cin>>u;
        if(u <= a) ans[0]++;
        else if(u > a && u <= b) ans[1]++;
        else ans[2]++;
    }
    s(ans);
    cout<<ans[0];
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007


int main() {
	int n;
	scanf("%d", &n);
	vector<tuple<string, int, int>> s(n);
	REP(i, n) {
		string str;
		int x;
		cin >> str >> x;
		s[i] = make_tuple(str, -x, i+1);
	}
	SORT(s);
	REP(i, n) {
		printf("%d\n", get<2>(s[i]));
	}
	return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
d=[]
for i in range(10):
    sub_list=list(map(int,input().split()))
    d.append(sub_list)
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for i in range(h):
    a_list=list(map(int,input().split()))
    for j in a_list:
        if j==-1:
            pass
        else:
            ans+=d[j][1]
print(ans)
                  


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

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

int main(){
    ll N, K, Q;
    cin >> N >> K >> Q;
    ll A[Q];
    ll p[N] = {0};
    rep(i, Q){
        cin >> A[i];
        p[A[i] - 1]++;
    }
    rep(i, N){
        p[i] = K - (Q - p[i]);
        if(p[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 2176
fun main(arr: Array<String>) {
    val inpt = readLine()!!.split(" ").map { it.toLong() }
    var ab = inpt.take(2).toMutableList()
    val k = inpt[2].toInt()
    for(i in (0 until k)) {
        val idx1 = i%2
        val idx2 = (idx1+1)%2

        if(ab[idx1]%2!=0L) {
            ab[idx1]--
        }
        ab[idx2] += ab[idx1]/2
        ab[idx1] = ab[idx1]/2
    }
    println(ab.joinToString(" "))
}


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

string s;
bool check(int i, int j) {
	return (s[i-j] != s[i] && s[i-j] != s[i+j] && s[i] != s[i+j]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	cin >> s;
	int pr = 0, pg = 0, pb = 0;
	int sr[n], sg[n], sb[n];
	sr[n-1] = sg[n-1] = sb[n-1] = 0;
	for (int i=n-2; i>=0; i--) {
		sr[i] = sr[i+1] + (s[i+1] == 'R');
		sg[i] = sg[i+1] + (s[i+1] == 'G');
		sb[i] = sb[i+1] + (s[i+1] == 'B');
	}
	ll ans = 0;
	for (int i=0; i<n; i++) {
		ll cur = 0;
		if (s[i] == 'R') {
			cur += pg*sb[i];
			cur += pb*sg[i];
			for (int j=1; i-j>=0 && i+j<n; j++) {
				if (check(i, j)) cur--;
			}
		}
		else if (s[i] == 'G') {
			cur += pr*sb[i];
			cur += pb*sr[i];
			for (int j=1; i-j>=0 && i+j<n; j++) {
				if (check(i, j)) cur--;
			}
		}
		else {
			cur += pr*sg[i];
			cur += pg*sr[i];
			for (int j=1; i-j>=0 && i+j<n; j++) {
				if (check(i, j)) cur--;
			}
		}
		ans += cur;
		if (s[i] == 'R') pr++;
		else if (s[i] == 'G') pg++;
		else pb++;
	}
	cout << ans;
}

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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int n; cin >> n;
    map<string, ll> mp;
    ll ans = 0;
    REP(i, 0, n){
        string s; cin >> s;
        sort(ALL(s));
        mp[s]++;
    }
    for(auto &x : mp){
        ans += (x.second*(x.second-1))/2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d, ab, cd;
  cin >> a >> b >> c >> d;
  ab = a + b;
  cd = c + d;
  
  if (ab < cd) {
    cout << "Right" << endl;
  }
  else if (ab > cd) {
    cout << "Left" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }  

}

Measured memory_bytes: 256
// AtCoder Beginner Contest 119 - Problem A: Still TBD (https://vjudge.net/contest/337465#problem/A) 
#include <bits/stdc++.h>

using namespace std;

string solve(const string& s)
{
    int month = stoi(s.substr(5, 2));

    return month <= 4 ? "Heisei" : "TBD";
}

int main()
{
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    auto ans = solve(s);

    cout << ans << '\n';

    return 0;
}


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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int nn = n;
    int sum = 0;
    while(n > 0){
        sum += n % 10;
        n /= 10;
    }
    //cout << sum << endl;
    //cout << nn << endl;
    if(nn % sum == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}



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

const int N=200001;
const int mod=998244353;
int n,m,k;

int fact[N];
int inv_fact[N];

inline int mul(int a,int b)
{
    return ((a%mod)*(b%mod))%mod;
}

inline int add(int a,int b)
{
    return ((a%mod)+(b%mod))%mod;
}

int power(int a,int b)
{
    if(b==0) return 1;
    if(b==1) return a;
    int res=power(a,b/2);
    res=mul(res,res);
    if(b&1)
        res=mul(res,a);
    return res;
}

int mod_inv(int a)
{
    return power(a,mod-2);
}

void _init()
{
    fact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=mul(fact[i-1],i);
    }
    inv_fact[N-1]=mod_inv(fact[N-1]);
    for(int i=N-2;i>=0;i--)
    {
        inv_fact[i]=mul(inv_fact[i+1],i+1);
    }
    return;
}

int ncr(int n,int r)
{
    if(r>n) return 0;
    int ans=mul(fact[n],inv_fact[r]);
    ans=mul(ans,inv_fact[n-r]);
    return ans;
}

signed main()
{
    cin>>n>>m>>k;
    _init();
    int ans=0;
    for(int i=0;i<=k;i++)
    {
        int temp=mul(m,power(m-1,n-i-1));
        temp=mul(temp,ncr(n-1,i));
        ans=add(ans,temp);
    }
    cout<<(ans%mod)<<endl;
    return 0;
}

Measured memory_bytes: 6728
class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数nで初期化"""
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ノードxが属するグループの根を返す"""
        if self.parents[x] < 0:
            return x
        else:
            #経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """xが属するグループとyが属するグループを併合"""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """xが属するグループの要素数を返す"""
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """x, yが同じグループに属するかどうかを返す"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """xが属するグループ内の要素をリストで返す"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """全ての根に対する要素をリストで返す"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """グループの総数を返す"""
        return len(self.roots())

    def all_group_members(self):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



N,M=map(int,input().split())
p= [0] + list(map(int, input().split()))
uf = UnionFind(N+1)
for _ in range(M):
    x,y=map(int, input().split())
    uf.union(x,y)
ans = 0
for i in range(1, 1+N):
    if p[i]==i:
        ans += 1
    else:
        if uf.same(i, p[i]):
            ans += 1
print(ans)

Measured memory_bytes: 85096
# -*- coding: utf-8 -*-

N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

ans, mind = 0, 1000
for i in range(N):
    td = abs(A - (T - 0.006 * H[i]))
    if mind > td:
        ans = i + 1
        mind = td

print(ans)


Measured memory_bytes: 3060
#include<iostream>
using namespace std;
string s;
char t;
long long k;
int cnt;
main(){
    cin>>s>>k;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1')cnt++;
        else {
            t=s[i];
            break;
        }
    }
    if(cnt>=k)cout<<1<<endl;
    else cout<<t<<endl;
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main()
{
	int N, Z, W;
	vec(A)
		cin >> N >> Z >> W;
	fx(N) {
		vecp(A)
	}
	if (N==1) {
		ce(abs(W-A.at(0)))
	}
	else {
		ce(max(abs(A.at(N - 2) - A.at(N - 1)), abs(W - A.at(N - 1))))
	}
    return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())

a = [0] + list(map(int, input().split()))
a1 = [0] * (n+1)

step = 1
start = 0
while(True):
    start += 1
    a1[step] += 1
    step = a[step]
    if a1[step] == 1:
        break
c = step
gap = 0
while(True):
    gap += 1
    step = a[step]
    if step == c:
        break
result = 1
if k > start:
    k = (k-start) % gap
    result = c
for _ in range(k):
    result = a[result]

print(result)


Measured memory_bytes: 32380
#include <iostream>

using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b < c + d) {
		cout << "Right" << endl;
	}
	else if (a + b > c + d) {
		cout << "Left" << endl;
	}
	else {
		cout << "Balanced" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  int ans = 0;
  rep(i,N){
    cin >> h.at(i);
    if(h.at(i) >= K) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3768
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
    char s[3];
    int i,x=0;
    for(i=0;i<3;i++){
        scanf("%c",&s[i]);
        if(s[i]=='1'){
            x=x+1;
        }
    }
    printf("%d",x);
    return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstring>
# include <string>
# include <cstdlib>
# include <algorithm>
# include <stack>
# include <queue>
# include <vector>
# define maxx (103)
# define Pi (3.14159265358979)
# define inf (2147483647)
using namespace std;
int read() {
	int x=0,f=1;
	char ch;
	while(ch<'0'||ch>'9')  {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
int main() {

	int n,k,ans;
	ans=1;
	n=read();
	k=read();
	
	int i;
	for(i = 1;i <= n;i++){
		ans+=min(ans,k);
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#define ll long long
int t;
ll a,b,c,d;
ll gcd(ll x,ll y) {return y == 0 ? x : gcd(y, x%y);
}
int main() {
    std :: cin >> t;
    while(std :: cin >> a >> b >> c >> d){
        ll g=gcd(b,d);
        if(a<b || b>d || ((a-c-1ll)/g-(a-b)/g>0)) puts("No");
        else puts("Yes");
    }
} 

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

using namespace std;



int main() {
	int n;
	while (cin >> n, n) {
		vector<int> k(n);
		for (int i = 0; i < n; ++i) cin >> k[i];
		string s; cin >> s;
		int now = 0;
		for (int c : s) {
			if (isupper(c)) {
				c -= 'A';
				(c -= k[now] - 52) %= 52;
				if (c >= 26) c = (c % 26) + 'a';
				else c += 'A';
			} else {
				c -= 'a';
				(c -= k[now] - 52) %= 52;
				if (c >= 26) c = (c % 26) + 'A';
				else c += 'a';
			}
			cout << (char)c;
			(now += 1) %= n;
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define SIZE 600005
#define MX 13
using namespace std;

int now[SIZE];
int memo[MX][SIZE];
char T[SIZE];
int id[SIZE];

void change(int &t)
{
	if(t==1) t=2;
	else if(t==2) t=1;
}
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",&T);
	int m=strlen(T);
	for(int i=0;i<n;i++)
	{
		int t=1;
		for(int j=0;j<=i;j++) t*=3;
		for(int j=0;j<t;j++)
		{
			int x=j;
			for(int k=0;k<i;k++) x/=3;
			now[j]=x;
		}
		bool flip=false;
		for(int j=0;j<m;j++)
		{
			if(T[j]=='S') flip=!flip;
			else
			{
				int x=id[j];
				int K=0;
				for(int k=0;k<3;k++)
				{
					int to=k*(t/3)+x;
					if(flip) change(now[to]);
					if(now[to]==2)
					{
						K=k;
						now[to]=0;
					}
					else now[to]++;
					if(flip) change(now[to]);
				}
				id[j]+=K*(t/3);
			}
		}
		for(int j=0;j<t;j++)
		{
			if(flip) change(now[j]);
			memo[i][j]=now[j];
		}
	}
	int T=1;
	for(int i=0;i<n;i++) T*=3;
	for(int i=0;i<T;i++)
	{
		int ret=0,t=1;
		for(int j=0;j<n;j++)
		{
			t*=3;
			ret+=memo[j][i%t]*(t/3);
		}
		printf("%d ",ret);
	}
	puts("");
}

Measured memory_bytes: 10260
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = n; i > 0; i--)
#define rep3(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep4(i, s, e) for (int i = (e); i < (int)(s); i--)

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

    int c = 0;
    int now = 1;
    vector<int> count(n);

    rep(i, n){
        cin >> count.at(i);
    }

    while (now != 2 && c < n + 1) {
        now = count.at(now - 1);
        c++;
        if (now == 2) {
            break;
        }
    }

    if (now != 2) {
        c = -1;
    }
    cout << c << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
//const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    vector<int> a(N), b(N), c(N);

    REP(i,N) cin >> a[i] >> b[i] >> c[i];
    map<pair<int,int>, int> mp;
    REP(i, 1<<(N/2)){
        int sumA=0, sumB=0, sumC=0;
        REP(j,N/2){
            if((i>>j) & 1){
                sumA += a[j];
                sumB += b[j];
                sumC += c[j];
            }
        }
        if(mp.count({sumA, sumB})){
            chmin(mp[{sumA, sumB}], sumC);
        }
        else mp[{sumA, sumB}] = sumC;
    }
    map<pair<int,int>, int> mp2;
    REP(i, 1<<(N-N/2)){
        int sumA=0, sumB=0, sumC=0;
        REP(j,N-N/2){
            if((i>>j) & 1){
                sumA += a[j+N/2];
                sumB += b[j+N/2];
                sumC += c[j+N/2];
            }
        }
        if(mp2.count({sumA, sumB})){
            chmin(mp2[{sumA, sumB}], sumC);
        }
        else mp2[{sumA, sumB}] = sumC;
    }

    int ans = INF;
    for(auto x : mp){
        int sumA = x.first.first;
        int sumB = x.first.second;
        for(int i=1;i*max(Ma,Mb)<405;i++){
            if(mp2.count({i*Ma-sumA, i*Mb-sumB})) chmin(ans, x.second + mp2[{i*Ma-sumA, i*Mb-sumB}]);
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
 
using lli = long long int;
using ll = long long ;
using ld=long double;
using d= double;


int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    ll sum=0;
    for(int i=0;i<n-1;i++){
        sum+=a[i];
    }
    if(a[n-1]<sum)
    cout<<"Yes";
    else
    cout<<"No";
}

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

using namespace std;

int main(){
	int n;
	cin >> n;
	int l[3000] ;
	for(int i=0;i<n;i++) cin >> l[i];
	//sort(l,l+n,greater<int>());
	sort(l,l+n);
	int count=0;
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				//cout << i << " " << j << " " << k << endl;
				if(l[i]+l[j]<=l[k]){
					//cout << "out" << endl;
					break;
				}
				else if(l[j]+l[k]>l[i] && l[k]+l[i] >l[j]) {
					//cout << "goo" << endl;
					count++;
				}
			}
		}
	}
	cout << count << endl;
}





Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;

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

        int n = stdIn.nextInt();
        String s = stdIn.next();
        char [] cs = s.toCharArray();
        int [] is = new int [cs.length];
        for(int i=0; i<is.length; i++){
            is[i] = (int)(cs[i] - '0');
        }

        int [][] a = new int [10][30000];
        int [] iN = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

        for(int i=0; i<n; i++){
            a[is[i]][iN[is[i]]++] = i;
        }

        int counter = 0;
        for(int i=0; i<=9; i++){
            int idxI = -1;
            for(int l=0; l<iN[i]; l++){
                if(a[i][l] >= 0){
                    idxI = a[i][l];
                    break;
                }
            }
            if(idxI == -1){
                continue;
            }
            for(int j=0; j<=9; j++){
                int idxJ = -1;
                for(int l=0; l<iN[j]; l++){
                    if(a[j][l] > idxI){
                        idxJ = a[j][l];
                        break;
                    }
                }
                if(idxJ == -1){
                    continue;
                }
                for(int k=0; k<=9; k++){
                    int idxK = -1;
                    for(int l=0; l<iN[k]; l++){
                        if(a[k][l] > idxJ){
                            counter++;
                            break;
                        }
                    }
                }
            }
        }

        System.out.println(counter);
    }
}

Measured memory_bytes: 24660
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;cin>>N>>K;
  int x=1;
  for(int i=0; i<N; i++){
    if(x+K>2*x)x*=2;
    else x+=K;
  }
  cout<<x<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;


int main(){
  ll D, T, S;
  cin>>D>>T>>S;
  Yes(D<=T*S);
  return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include <functional>
#include <limits>
#include <set>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

int solve(vector<pair<int,int>>& P){
	int N = P.size(), res = 0;
	multiset<int> s;
	
	s.insert(-1);
	s.insert(-1);
	s.insert(N);
	s.insert(N);
	
	sort(P.begin(), P.end(), greater<pair<int,int>>());
	
	for(int i = 0; i < N; i++){
		decltype(s)::iterator it =  s.lower_bound(P[i].second);
		int a, b, c, d;
		it--, it--;
		a = *it++;
		b = *it++;
		c = *it++;
		d = *it++;
		
		res += ((b - a) * (c - P[i].second) + (P[i].second - b) * (d - c)) * P[i].first;
		
		s.insert(P[i].second);
	}
	
	
	return res;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	vector<pair<int,int>> P;
	
	cin>>N;
	
	P.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>P[i].first;
		P[i].second = i;
	}
	
	cout<<solve(P)<<endl;
	
	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <math.h>
int main() {
    int N,D;
    scanf("%d%d",&N,&D);
    short d[N][D];
    double res = 0;
    int cnt = 0;
    for(int i=0;i<N;++i)
        for(int j=0;j<D;++j)
            scanf("%hd",&d[i][j]);
    for(int a=0;a<N-1;++a) {
        for(int b=a+1;b<N;++b) {
            res = 0;
            for(int j=0;j<D;++j) {
                int tmp = abs(d[a][j] - d[b][j]);
                res += tmp*tmp;
            }
            res = sqrt(res);
            long long ires = (long long)(res*1000000);
            if(ires - res*1000000 == 0) cnt++;
        }
    }
    std::cout<<cnt;
}

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

class Player{
private:
    bool played_;
    queue<int> games_;
    int id_;
public:
    void SetId(int i);
    int GetId();
    void NewDay();
    bool CanPlay();
    int NextGame();
    void Play();
    void Input(int i);
};

void Player::SetId(int i) {
  id_ = i;
}

int Player::GetId() {
  return id_;
}

void Player::NewDay(){
  played_ = false;
}

bool Player::CanPlay(){
  return !(played_ or games_.empty());
}

int Player::NextGame() {
  return games_.front();
}

void Player::Play() {
  games_.pop();
  played_ = true;
}

void Player::Input(int i) {
  games_.push(i);
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<Player> players(n);
  vector<Player*> active_players(n);
  for (int i = 0; i < n; ++i) {
    players[i].SetId(i);
    active_players[i] = &players[i];
    for (int j = 0; j < n - 1; ++j) {
      int a;
      cin >> a;
      players[i].Input(a - 1);
    }
  }
  
  int game = 0;
  int day = 0;
  int prev_game = 0;
  
  while (game < n * (n - 1) / 2) {
    vector<Player*> next_active_players;
    for (Player* player : active_players) {
      if (not player->CanPlay()) continue;
      Player* opponent = &players[player->NextGame()];
      if (not opponent->CanPlay()) continue;
      if (player->GetId() == opponent->NextGame()) {
        player->Play();
        opponent->Play();
        next_active_players.push_back(player);
        next_active_players.push_back(opponent);
        ++game;
      }
    }
    if (game == prev_game) {
      cout << -1 << endl;
      return 0;
    }
    prev_game = game;
    ++day;
    for (Player* player : next_active_players) {
      player->NewDay();
    }
    active_players = next_active_players;
  }
  cout << day << endl;
  return 0;
}


Measured memory_bytes: 4736
def f;gets.to_i;end
while(n=f)>0
m,g=f,f
a=(1..n).to_a
b=[a.dup]
l=(1..f).map{i=0;(r=gets.chars).map{|c|c>?0&&(*a[i,2]=a[i+1],a[i]);i+=1};b<<a.dup;r}
x=y=0
puts m==(s=a[g-1])?0:l.find{|r|r=[?0]+r;x+=1;y=(1..n-1).find{|j|r[j-1,3].all?{|k|k<?1}&&b[x-1][j-1,2]-[m,s]==[]}}?"#{x} #{y}":1
end

Measured memory_bytes: 6108
#include <bits/stdc++.h>
typedef long long       ll;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb                push_back
#define mp                make_pair
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define fore(i, b, e)      for(int i = b; i < e; i++)
#define forr(i, b, e)      for(int i = b; i < e; i++)
#define forg(i, b, e, m)  for(int i = b; i < e; i+=m)
#define fi first
#define se second
int faster_in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -faster_in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
//using namespace __gnu_pbds;

typedef pair<int, int>  ii;
typedef pair<int, ii>  iii;
typedef vector<int>     vi;

typedef vector<ii>      vii;
typedef vector<ll>      vll;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int INF = int(1e9 + 7);
const double PI = acos(-1);
const double EPS = 1e-9;
#define tam 1234567
#define getnods int newnodo=nodo*2,mid=(iz+der)/2;
int tree[tam*4];
int nxt[tam];
void update(int nodo,int iz,int der,int pos,int valor)
{
    if (iz==der)
    {
        tree[nodo]=valor;
        return;
    }
    getnods
    if (pos<=mid)
    update(newnodo,iz,mid,pos,valor);
    else
    update(newnodo+1, mid+1,der,pos,valor);
    tree[nodo]=max(tree[newnodo],tree[newnodo+1]);
}
int query(int nodo,int iz,int der,int li,int ri)
{
    if (der<li|| iz>ri)
        return 0;
    if (iz>=li && der<=ri)
    {
        return tree[nodo];
    }
    getnods
    return max(query(newnodo,iz,mid,li,ri),
                query(newnodo+1,mid+1,der,li,ri));
}
const int MOD=998244353;
void MODUL(int &num)
{
    while(num>=MOD)
        num-=MOD;
}
int n;
int dp[tam];
int go(int num)
{
    if (num==n+1)
        return 1;
    if (dp[num]!=-1)
        return dp[num];
    int ways=0;
    ways+=go(nxt[num]+1);
    MODUL(ways);
    ways+=go(num+1);
    MODUL(ways);
    return dp[num]=ways;

}
int main()
{
    memset(dp,-1,sizeof dp);
    cin>>n;
    set<ii> s;
    vector<ii> v;
    int posx,add;
    forr(i,0,n)
    {
        cin>>posx>>add;
        v.pb({posx,add});
    }
    sort(v.begin(),v.end());
    forr(i,0,n)
    {
        
        s.insert({v[i].fi,i});
    }
    
    int mipos,miadd,hasta,cord;
    for(int i=n-1;i>=0;i--)
    {
        mipos=v[i].fi;
        miadd=v[i].se;
        auto ite=s.lower_bound({mipos+miadd,0});
        
        ite--;
        hasta=(*ite).se+1;
        cord=i+1;
        nxt[cord]=max(cord,query(1,1,n,cord,hasta));
        
        update(1,1,n,cord,nxt[cord]);
    }
    
    cout<<go(1)<<endl;
}
// PLUS ULTRA!

Measured memory_bytes: 27632