akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int A[3][SIZE],n[3],N;
template <class T>
void maa(T& x,T y){
    if(x<y)x=y;
}
template <class T>
void mii(T& x,T y){
    if(x>y)x=y;
}
VI d[3];
LL an;
LL mi=1e18;
int used[SIZE],tt;
void go(VI p){
    if(SZ(d[p[2]])>n[p[2]])return;
    if(SZ(d[p[0]])<n[p[0]])return;
    VL move12;
    REP(i,SZ(d[p[1]])){
        int id=d[p[1]][i];
        move12.PB(A[p[1]][id]-A[p[2]][id]);
    }
    sort(ALL(move12));
    while(SZ(move12)<n[p[2]]-SZ(d[p[2]]))move12.PB((LL)(1e13));
    LL now=0;
    REP(i,n[p[2]]-SZ(d[p[2]]))now+=move12[i];
    VPLL move01;
    REP(i,SZ(d[p[0]])){
        int id=d[p[0]][i];
        move01.PB(MP(A[p[0]][id]-A[p[1]][id],id));
    }
    sort(ALL(move01));
    VPLL tmp;
    tt++;
    REP(i,SZ(d[p[0]])-n[p[0]]){
        now+=move01[i].F;
        int id=move01[i].S;
        tmp.PB(MP(A[p[1]][id]-A[p[2]][id],id));
    }
    sort(ALL(tmp));
    priority_queue<LL>hh;
    REPP(i,SZ(d[p[0]])-n[p[0]],SZ(d[p[0]])){
        int id=move01[i].S;
        hh.push(-(A[p[0]][id]-A[p[2]][id]));
    }
    mi=min(mi,now);
    int it02=0;
    int it01=SZ(d[p[0]])-n[p[0]]-1;
    int it_tmp=0;
    for(int j=0;j<n[p[2]]-SZ(d[p[2]])&&j<SZ(d[p[0]])-n[p[0]];j++){
        now-=move12[n[p[2]]-SZ(d[p[2]])-1-j];
        while(used[move01[it01].S]==tt)it01--;
        while(used[tmp[it_tmp].S]==tt)it_tmp++;
        if(hh.empty()||tmp[it_tmp].F<=-hh.top()-move01[it01].F){
            used[tmp[it_tmp].S]=tt;
            now+=tmp[it_tmp].F;
        }
        else{
            int id=move01[it01].S;
            now+=-hh.top()-move01[it01].F;
            hh.pop();
            used[id]=tt;
            hh.push(-(A[p[0]][id]-A[p[2]][id]));
        }
        mi=min(mi,now);
    }
}
int main(){
    REP(i,3){
        RI(n[i]);
        N+=n[i];
    }
    REP(i,N)REP(j,3)RI(A[j][i]);
    REP(i,N){
        PII ma=MP(-1,-1);
        REP(j,3){
            maa(ma,MP(A[j][i],j));
        }
        an+=ma.F;
        d[ma.S].PB(i);
    }
    VI p;
    REP(i,3)p.PB(i);
    do{
        go(p);
    }while(next_permutation(ALL(p)));
    cout<<an-mi<<endl;
    return 0;
}


Measured memory_bytes: 17700
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int n;
int ans[10005];

void init();
int f(int n);
int main()
{
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        printf("%d\n", ans[i]);
    }
}

void init()
{
    for(int i=1; i<=10000; i++){
        ans[i] = f(i);
    }
}

int f(int n)
{
    int cnt = 0;
    long long x, y, z;
    for(x=1; x<=100; x++){
        if(x*x > n)
            break;
        for(y=1; y<=100; y++){
            if(x*x + y*y + x*y > n)
                break;
            for(z=1; z<=100; z++){
                long long sum = x*x + y*y + z*z + x*y + y*z + z*x;
                if(sum > n)
                    break;
                else if(sum == n)
                    cnt++;
            }
        }
    }
    return cnt;
}


Measured memory_bytes: 1740
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  int a,b;
  cin>>a>>b;
  if(a+b > 9) cout<<"error"<<endl;
  else cout<<a+b<<endl;
  return 0;
}







Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int n = sc.nextInt();
		int[] values = new int[w];
		for(int i=0;i<values.length;i++){
			values[i]=i+1;
		}
		for(int i=0;i<n;i++){
			String str = sc.next();
			String[] ab = str.split(",");
			int a = Integer.parseInt(ab[0])-1;
			int b = Integer.parseInt(ab[1])-1;
			int temp =values[a];
			values[a] = values[b];
			values[b] = temp;
		}
		for(int k=0;k<w;k++){
			System.out.println(values[k]);
			
		}
	}

}

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

int n;
char s[105];

bool palin(int l, int r) {
  for (; l < r; ++l, --r) {
    if (s[l] != s[r]) return false;
  }

  return true;
}

int solve() {
  scanf("%s", s);
  n = strlen(s);

  if (palin(0, n-1) && palin(0, (n-1)/2 - 1) && palin((n+3)/2 - 1, n-1)) printf("Yes\n");
  else printf("No\n");
  return 0;
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  while (t--) solve();
  return 0;
}


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

int main(){
  string S;
  cin >> S;
  long cnt = 0, wsum = 0;
  for (int i=S.size(); i >= 0; i--) {
    if (S[i] == 'W'){
      wsum++;
    } else {
      cnt += wsum;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 640
//おまじないc++
#include <iostream>
#include<cmath>
#include<vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()


int main() {
	int x;
	cin >> x;
	int m = 0;


	for (int i = 1; x >= 100 * i; i++) {
		if (i * 100 <= x && x <= 105 * i) {
			m++;
			break;

		}
	}

	cout << m;
}

	


Measured memory_bytes: 256
main :: IO ()
main = do
    line <- getLine
    case (words line) of
      ["0", "0"] -> return ()
      [h, w] -> do
          printChessboard (read h :: Int) (read w :: Int)
          main

printChessboard :: Int -> Int -> IO ()
printChessboard w h = do
    mapM_ putStrLn $ map (\x -> printLine x h) [0..w-1]
    putStrLn ""

printLine :: Int -> Int -> String
printLine n h =
    map (\x -> if even x then '#' else '.') [n+0..n+h-1]

Measured memory_bytes: 4072
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s,t;
    long long i,j,k=0,max=0;
    cin>>s>>t;
    for(i=0;i<=(s.size()-t.size());i++)
    {
        k=0;
        for(j=0;j<t.size();j++)
        {
            if(s[i+j]==t[j])
            {
                k++;
            }
        }
        if(k>max)
        {
           max=k;
        }
    }
    cout<<(t.size()-max)<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include<cmath>
#include<cstring>
#define pb              push_back
#define pi              acos(-1.0)
#define loop(i,a,n)     for(int i=a;i<n;i++)
#define rloop(i,n,a)    for(int i=n;i>=a;i--)
#define ll              long long int
#define ff              first
#define ss              second
#define pii             pair<ll,ll>
#define sc1(a)          scanf("%d",&a)
#define sc2(a,b)        scanf("%d %d",&a,&b)
#define sc3(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define all(v)          v.begin(),v.end()
#define ms(a,b)         memset(a,b,sizeof a)
#define FastIO          ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define fileout         freopen("output.txt","w",stdout)
#define filein          freopen("input.txt","r",stdin)
#define inf             2e9+5
#define Q               int q;cin>>q;while(q--)
#define check           cout<<"HI"<<endl;

//int x[]= {-1,0,0,1};
//int y[]= {0,-1,1,0};

using namespace std;

int main()
{
    char c;
    cin >> c;
    if(c<97)cout<<'A'<<endl;
    else cout<<'a'<<endl;

}












Measured memory_bytes: 3036
#include<stdio.h>

main() {
	char data[1001];
	int i, sum;

	while (1) {
		scanf("%s", data);	
		if(data[0] == '0') break;

		sum = 0;

		for (i = 0; data[i] != '\0'; i++) {
			sum += data[i] - '0';
		}

		printf("%d\n", sum);

	}

	return 0;

}

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

using namespace std;

void Main() {
    int N;
    cin >> N;
    vector<int> P(N, 0), Q(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> Q[i];
    }

    vector<int> X;
    for (int i = 1; i <= N; ++i) {
        X.push_back(i);
    }

    int counter = 0;
    int np = -1;
    int nq = -1;
    do {
        int diffp = 0;
        int diffq = 0;
        for (int i = 0; i < N; ++i) {
            diffp += abs(X[i] - P[i]);
            diffq += abs(X[i] - Q[i]);
        }
        if (diffp == 0) {
            np = counter;
        }
        if (diffq == 0) {
            nq = counter;
        }
        ++counter;
        if (np >= 0 && nq >= 0) {
            break;
        }
    } while (next_permutation(X.begin(), X.end()));

    cout << abs(np - nq) << endl;
}

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


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

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

typedef long double db;
const db eps = 1e-8;
const db pi = acosl(-1.0);

int sgn(db x) {if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1;}

struct Point{
    db x, y;
    Point(){}
    Point(db x, db y) : x(x), y(y){}
    void input(){cin >> x >> y;}
    Point operator + (const Point &b) const{
        return Point(x + b.x, y + b.y);
    }
    Point operator - (const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    db operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    db operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    Point operator * (const db &k) const{
        return Point(x * k, y * k);
    }
    Point operator / (const db &k) const{
        return Point(x / k, y / k);
    }
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e) : s(s), e(e){}
    void input() {s.input(); e.input();}
    Point getSegCrossPoint(Line v) {
        db a1 = (v.e - v.s) ^ (s - v.s);
        db a2 = (v.e - v.s) ^ (e - v.e);
        db t = a2 - a1;
        return Point((s.x * a2 - e.x * a1) / t, (s.y * a2 - e.y * a1) / t);
    }
}l1, l2;

int main(){
#ifndef ONLINE_JUDGE
// freopen("i.in","r",stdin);
//  freopen("o.out","w",stdout);
#endif
    int T;scanf("%d", &T);
    while(T--){
        Point p;
        l1.input(); l2.input();
        p = l1.getSegCrossPoint(l2);
        cout << fixed << setprecision(10) << p.x <<' ' << p.y <<endl;
    }

    return 0;
}


Measured memory_bytes: 3360
#include<iostream>
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define gcd(a,b) __gcd(a,b)
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcountll(x)
#define printv(v) for(auto p : v) cout << p << " ";
#define printa(a,n) for(int i = 0 ; i < n ; i++) cout << a[i] << " "; 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

inline int waste(int a, int b, int m) { return (((a % m) + (b % m)) % m); }
inline int worse(int a, int b, int m) { return (((a % m) * (b % m)) % m); }
inline int worst(int a, int b, int m) { return (((a % m) - (b % m) + m) % m);}

using namespace std;

int32_t main()
{
   fast;
   #ifndef ONLINE_JUDGE
   freopen("goodluckin.txt","r",stdin);
   freopen("goodluckout.txt","w",stdout);
   #endif

   int n,k;
   cin >> n >> k;
   int a[n];
   for(int i = 0 ; i< n ; i++ ){
    cin >> a[i];
   }
   sort(a,a+n);
   int ans = 0;
   for(int i = 0 ; i < k ;i++){
    ans+=a[i];
   }
   cout << ans;
}

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

#define lli long long


lli knapsack(vector<lli>wt, vector<lli>val, int n, int capacity) {
	lli dp[n + 1][capacity + 1];
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= capacity; j++) {
			if (i == 0 || j == 0)
				dp[i][j] = 0;
			else {
				lli inc = 0, exc = 0;
				if (wt[i - 1] <= j)
					inc = val[i - 1] + dp[i - 1][j - wt[i - 1]];
				exc = dp[i - 1][j];

				dp[i][j] = max(inc, exc);
			}
		}

	}
	return dp[n][capacity];
}

int main() {



	int n, capacity;
	cin >> n >> capacity;

	vector<lli>wt;
	vector<lli>val;
	lli w, v;
	for (int i = 0; i < n; i++) {
		cin >> w >> v;
		wt.push_back(w);
		val.push_back(v);
	}
	cout << knapsack(wt, val, n, capacity);

	return 0;
}


Measured memory_bytes: 79104
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/range/algorithm.hpp>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
#define PI 3.14159265358979

int main() {
  int a, b, x;
  cin >> a >> b >> x;
  double ans;
  if (2 * x < a * a * b) {
    double c = (double)x / (a * b) * 2.0;
    ans = 360.0 / 2 / PI * atan((double)b / c);
  } else {
    double c = (double)(a * a * b - x) / (a * a) * 2.0;
    ans = 360.0 / 2 / PI * atan((double)c / a);
  }

  cout << setprecision(15) << ans << endl;
  return 0;
}


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

int main() {
    int A, B, K; cin >> A >> B >> K;
    int cnt = 0;
    for (int i = min(A, B); i > 0; i--) {
        if (A % i == 0 && B % i == 0) {
            cnt++;
            if (cnt == K) {
             cout << i << endl;
             break;
            }
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0,(i##_len)=(n);(i)<(i##_len);(i)++)
#define rep2(i,a,b) for(ll (i)=(a),(i##_len)=(b);(i)<=(i##_len);(i++))
#define Yes(n) cout<<((n)?"Yes\n":"No\n")
#define pb push_back
using namespace std;
using ll = long long;

template<class T> bool chmax(T&a,const T&b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,const T&b){if(a>b){a=b;return true;}return false;}
template<class T> T abs(T x){return max(x,-x);}
template<class T> T gcd_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=gcd(r,v.at(i));return r;}
template<class T> T lcm(T m,T n) {return m*n/gcd(m,n);}
template<class T> T lcm_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=lcm<T>(r,v.at(i));return r;}
template<class T> T factorial(T n){if(n==0)return 1;T r=1;for(T i=2;i<=n;i++)r*=i;return r;}
template<class T> T nCr(T n,T k){return factorial<T>(n)/(factorial<T>(k)*factorial<T>(n-k));}
template<class T> T dot_product(vector<T>u,vector<T>v){T r=0;for(T i=0;i<u.size();i++)r+=u.at(i)*v.at(i);return r;}
template<class T> T sum(vector<T>v){return reduce(all(v),0LL);}

// Template ends here
int solve(ll N, vector<ll> a){
    ll current = 0, cnt = 0, i = N;
    while (i--) {
        if (a.at(current) == 2) {
            cout << ++cnt << "\n";
            return 0;
        }
        current = a.at(current) - 1;
        cnt++;
    }
    cout << "-1\n";
    return 0;
}

int main() {
    ll N;
    scanf("%lld",&N);
    vector<ll> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, move(a));
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
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; }
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; }
const ll MOD = 1e9 + 7;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
int main() { // 問題文はしっかり読め!!!
	string s;
	cin >> s;
	int d;
	cin >> d;
	int n = s.size();
	VVV dp(n + 1, VV(2, V(d, 0))); // i桁目まで見て、その桁までsぴったりかのフラグで、桁和をdで割った余りがkになるもの
	dp[0][0][0] = 1;
	rep(i, n) {
		rep(j, 2) { // ここはnjが0ならばぴったりで、1ならばぴったりではないことを表す
			rep(k, d) {
				rep(num, 10) {
					int nj = j;
					if (nj == 0) {
						if (s[i] - '0' < num) continue;
						if (s[i] - '0' > num) nj = 1;
					}
					dp[i + 1][nj][(k + num) % d] += dp[i][j][k];
					dp[i + 1][nj][(k + num) % d] %= MOD;
				}
			}
		}
	}
	ll ans = (MOD - 1 + dp[n][0][0] + dp[n][1][0]) % MOD;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll m = (ll)1e9 + 7;
const ll N = 100500;
char s[N];
ll n,dp[N][15];

ll ctoi(char x) {
   return x - '0';
}

ll add(ll a , ll b) {
   return (a + b) % 13;
}

ll madd(ll a , ll b) {
   return ((a % m) + (b % m)) % m;
}

ll f(ll curr , ll sum) {
   if (curr >= n) return sum == 5;
   ll &sol = dp[curr][sum];
   if (sol != -1) return sol;
   if (s[curr] != '?') {
      sol = f(curr + 1 , add(sum * 10 , ctoi(s[curr])));
   } else {
      sol = 0;
      for (ll dig = 0 ; dig < 10 ; dig++) {
         sol = madd(sol , f(curr + 1 , add(sum * 10 , dig)));
      }
   }
   return sol % m;
}

int main() {
   scanf("%s" , s);
   n = strlen(s);
   memset (dp , -1 , sizeof dp);
   printf("%lld\n" , f(0 , 0));
}


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

using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 1 << 30
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int MOD = 1000000007;


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

    ll n,k; cin >> n >> k;

    std::vector<ll> v(100001, 0);
    REP(i,n){
        ll a,b; cin >> a >> b;
        v[a] += b;
    }

    ll ans = 0;
    REP(i, 100001){
        k-=v[i];
        if(k<=0){
            ans = i;
            break;
        }
    }

    cout << ans << endl;


    return 0;
}


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

using namespace std;

#define int long long 

int32_t main()
{
	//ios_base::sync_with_stdio(false);cin.tie(0);
	int n, sum = 0,a[200005];
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		sum^=a[i];
	}
	for(int i = 1;i <= n;i++)
	{
		cout << (sum^a[i]) <<" ";
	}
	cout << endl;
	return 0;
}


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

using namespace std;

#define ll long long int 
#define F first
#define S second
#define pb push_back

const ll N = 2e5 + 5;
const ll MOD =  1e9 + 7;
const ll INF = 2e9 + 10;
int n, posx[N], posy[N], pr[N], sz[N], mn[N];
vector < pair <int, int> > all;
set < pair <int, int> > st;
int Find(int v){
    if (pr[v] == 0) return v;
    return (pr[v] = Find(pr[v]));
}
void Union(int u, int v){
    u = Find(u), v = Find(v);
    if (sz[v] < sz[u]) swap(u, v);
    sz[v] += sz[u];
    pr[u] = v;
    mn[v] = min(mn[u], mn[v]);
    return;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> posx[i] >> posy[i];
        all.pb({posx[i], i});
        sz[i] = 1;
        mn[i] = posy[i];
    }
    sort(all.begin(), all.end());
    for (auto it : all){
        int id = it.S;
        while (st.size() && (*st.begin()).F < posy[id]){
            Union((*st.begin()).S, id);
            st.erase(st.begin());
        }
        st.insert({mn[Find(id)], id});
    }
    for (int i = 1; i <= n; i++){
        cout << sz[Find(i)] << '\n';
    }
    return 0;
}

Measured memory_bytes: 12668
#include <iostream>
#include <unordered_map>

using namespace std;

using ull = uint64_t;

ull n, m;

ull sum[100010];
unordered_map<ull, ull> countmap;
ull ans = 0;

int main() {
    cin >> n >> m;
    for (ull i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        sum[i] = (sum[i - 1] + tmp) % m;
    }

    for (ull i = 0; i <= n; i++) {
        if (countmap.find(sum[i]) == countmap.end()) {
            countmap[sum[i]] = 0;
        }
        countmap[sum[i]]++;
    }

    for(auto&& p : countmap) {
        ans += p.second * (p.second - 1) / 2;
    }

    cout << ans << endl;

    return 0;
}


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

vector<int> di = {0, 0, -1, 1};
vector<int> dj = {1, -1, 0, 0};

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

    int n, T;
    cin >> n >> T;

    int sum = 0;

    vector<int> t(n);
    rep(i,n) cin >> t[i];

    ll ans = 0;
    for(int i = 1; i < n; ++i) {
        if(t[i] - t[i-1] < T) {
            ans += t[i] - t[i-1];
        }
        else {
            ans += T;
        }
    }
    ans += T;

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

Measured memory_bytes: 3956
import java.util.*;

public class Main{
    public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    String b[]= {"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"};
    String[] sp =S.split("");
    for(int i=0; i<sp.length; i++){
	for(int j=0; j<26; j++){
	    if(sp[i].equals(b[j])){
		sp[i]=b[(j+N)%26];
		System.out.print(sp[i]);
		break;
	    }
	}
    }
    System.out.println();
    }
}


Measured memory_bytes: 26836
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, T;
int A[3003], B[3003];
int DP[3003][3000];
int INVDP[3003][3000]; 
// T-1分後までにi以外の食事を食べ、最後にiを食べるのは、
// T分後までにi-1とi+1以降の食事をする

// DP[i][j]はj分までで料理0-(i-1)まで注文できる時にかかる最大値
// DP[i][j]はj分までで料理(N-1)-(i)まで注文できる時にかかる最大値
// iこ目の料理でT分は、

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

  cin >> N  >> T;
  int a, b;
  rep(i, N) {
    cin >> a >> b;
    A[i] = a;
    B[i] = b;
  }
  rep(i, T) {
    if (i>=A[0]) DP[0][i] = B[0];
    else DP[0][i] = 0;
    if (i>=A[N-1]) INVDP[N-1][i] = B[N-1];
    else INVDP[0][i] = 0;
  }

  rep(i, N) {
    if (i==0) continue;
    rep(j, T) {
      if (j-A[i]<0) DP[i][j] = DP[i-1][j];
      else DP[i][j] = max(DP[i-1][j], DP[i-1][j-A[i]]+B[i]);
    }
  }

  for(int i=N-2; i>=0; i--) {
    rep(j, T) {
      if (j-A[i]<0) INVDP[i][j] = INVDP[i+1][j];
      else INVDP[i][j] = max(INVDP[i+1][j], INVDP[i+1][j-A[i]]+B[i]); 
    }
  }

  int ans = 0;
  rep(i, N) {
    rep(j, T) {
      if (i==0) ans = INVDP[1][T-1] + B[0];
      else if (i==N-1) ans = max(ans, DP[N-2][T-1]+B[N-1]);
      else ans = max(ans, DP[i-1][j]+INVDP[i+1][T-j-1]+B[i]);
    }
  }

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

Measured memory_bytes: 70656
#!/usr/bin/env python3
import sys


def gcd(a: int, b: int):
    if a < b:
        return gcd(b, a)
    while b != 0:
        a, b = b, a % b
    return a


def solve(A: int, B: int, K: int):
    g = gcd(A, B)
    c = [i for i in range(1, g + 1) if g % i == 0]
    print(c[-K])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(A, B, K)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.Scanner;

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

		int ans = (int) ((Math.ceil(n / x)) * t);
		System.out.println(ans);
		sc.close();
	}
}




Measured memory_bytes: 37288
#include <iostream>
 
using namespace std;
int main(void){
    uint16_t N,M;
    uint16_t x,count=0;
    
    uint64_t sum=0;
    
    cin>>N;
    cin>>M;
    
    uint16_t num[N];
    
    for(int i=0;i<N;i++){
        cin>>x;
        num[i]=x;
        sum+=num[i];
    }
    
    for(int j=0;j<N;j++){
        if((4*M)*num[j]>=sum){
            count++;
        }
        if(count==M){
            cout<<"Yes";
            return 0;
        }
    }
    
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
# ショートカット前中後でG1-3に分け、i, jがそれぞれどこにいるかで場合分け

n, x, y = map(int, input().split())
ans = [0 for _ in range(n - 1)]
debug = [[] for _ in range(n-1)]
mid = (y - x) // 2 + x # G2の真ん中

for i in range(1, n):
  for j in range(i + 1, n + 1):
    # G1 -> G1
    if j <= x or y <= i:
      ans[j - i - 1] += 1
      
    # G1 -> G2
    elif i <= x and x < j < y:
      if j <= mid:
        ans[j - i - 1] += 1
      else:
        ans[(x - i) + (y - j)] += 1
        
    # G2 -> G3
    elif x < i < y and y <= j:
      if i >= mid:
        ans[j - i - 1] += 1
      else:
        ans[(i - x) + (j - y)] += 1
        
    # G1 -> G3
    elif i <= x and y <= j:
      ans[(x - i) + (j - y)] += 1
    
    # G2 -> G2
    else:
      ans[min(j - i - 1, (i - x) + (y - j))] += 1

# 結果の表示
for i in ans:
  print(i)

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

using namespace std;
typedef long long ll;

int n, m;
string s[1010];
int dp[1010][1010];
int md = 1e9 + 7;
void addMd(int &x, int y)
{
    x += y;
    if (x >= md)
        x -= md;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    dp[n-1][m-1] = 1;
    for (int i = n-1; i >= 0; --i)
        for (int j = m-1; j >= 0; --j)
            if (s[i][j] == '.')
            {
                if (i+1 < n)
                    addMd(dp[i][j], dp[i+1][j]);
                if (j+1 < m)
                    addMd(dp[i][j], dp[i][j+1]);
            }
    cout << dp[0][0] << "\n";

    return 0;
}


Measured memory_bytes: 5248
def s(total, que, p_m, ans_str, in_list):
    if que == 0:
        total += in_list[que]
        ans_str += str(in_list[que])
    else:
        total += in_list[que] if p_m else -in_list[que]
        ans_str += ("+" + str(in_list[que])) if p_m else ("-" + str(in_list[que]))
    if que == 3:
        if total == 7:
            print(ans_str + "=7")
            exit()
    else:
        s(total, que + 1, True, ans_str, in_list)
        s(total, que + 1, False, ans_str, in_list)


a = list(map(int, list(input())))
print(s(0, 0, True, "", a))


Measured memory_bytes: 3064
N, W = [int(i) for i in input().split()]
noWeight = [[0 for j in range(W+1)] for i in range(N)]
wv = [[] for i in range(N)]
for i in range(N) :
	wv = [int(i) for i in input().split()]
	for j in range(1,W+1) :
		if i != 0 :
			if j < wv[0]  :
				noWeight[i][j] = noWeight[i-1][j]
			else :
				noWeight[i][j] = max(noWeight[i-1][j - wv[0]] + wv[1], noWeight[i-1][j])
		else :
			if j >= wv[0] :
				noWeight[i][j] = wv[1]
			else :
				noWeight[i][j] = 0
	
print(noWeight[N-1][W])

Measured memory_bytes: 171528
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
using CostType = long long;
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &rhs) const {
    return cost != rhs.cost ? cost < rhs.cost : dst != rhs.dst ? dst < rhs.dst : src < rhs.src;
  }
  inline bool operator<=(const Edge &rhs) const { return cost <= rhs.cost; }
  inline bool operator>(const Edge &rhs) const {
    return cost != rhs.cost ? cost > rhs.cost : dst != rhs.dst ? dst > rhs.dst : src > rhs.src;
  }
  inline bool operator>=(const Edge &rhs) const { return cost >= rhs.cost; }
};

vector<Edge> detect_bridge(const vector<vector<Edge> > &graph) {
  int n = graph.size();
  vector<Edge> res;
  vector<int> depth(n, -1), imos(n, 0);
  function<void(int, int)> dfs = [&](int par, int ver) {
    bool multiedge = false;
    for (const Edge &e : graph[ver]) {
      if (depth[e.dst] == -1) {
        depth[e.dst] = depth[ver] + 1;
        dfs(ver, e.dst);
        if (imos[e.dst] == 0) res.emplace_back(min(ver, e.dst), max(ver, e.dst), e.cost);
        imos[ver] += imos[e.dst];
      } else if (!multiedge && e.dst == par) {
        multiedge = true;
      } else if (depth[e.dst] < depth[ver]) {
        ++imos[ver];
        --imos[e.dst];
      }
    }
  };
  REP(i, n) {
    if (depth[i] == -1) {
      depth[i] = 0;
      dfs(-1, i);
    }
  }
  // sort(ALL(res), [](const Edge &lhs, const Edge &rhs) {
  //   return lhs.src != rhs.src ? lhs.src < rhs.src : lhs.dst != rhs.dst ? lhs.dst < rhs.dst : lhs.cost < rhs.cost;
  // });
  return res;
}

int main() {
  int n, m; cin >> n >> m;
  vector<vector<Edge> > graph(n);
  while (m--) {
    int a, b; cin >> a >> b; --a; --b;
    graph[a].emplace_back(a, b);
    graph[b].emplace_back(b, a);
  }
  cout << detect_bridge(graph).size() << '\n';
  return 0;
}


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

using namespace std;

#define fast_cin() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define reP(i, x, n) for(int i=x; i<n; i++)
#define aLL(x) x.begin(), x.end()
#define pB push_back
#define eB emplace_back
#define tRav(a, x) for(auto& a: x)
#define fI first
#define sE second
#define lB lower_bound
#define uB upper_bound
#define MOD 1000000007

typedef vector<int> vec;
typedef long long ll;
typedef unsigned long long ull;

bool isPalindrome(string str) 
{ 
    int l = 0;
    int h =str.length() - 1; 
  
    while (h > l) 
    { 
        if (str[l++] != str[h--]) 
        { 
            return false; 
        } 
    } 
   return true; 
} 


int main(){
    fast_cin();
    double l;cin>>l;
    double x=l/3;
    //cout<<x<<endl;
    double ans = x*x*x;
    printf("%0.12f\n", ans);

}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC" << endl;
    else            cout << "ABC" << endl;
    return 0;
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define uy q.front()
#define SIZE (ll)(1e6)
#define mod (ll)(1e9+7)
using namespace std;
typedef long long  ll;
int main(){
int n,w;cin>>n>>w;
ll ar[n],we[n],dp[n+1][w+1];
for(int i=0;i<n;i++){
  cin>>we[i]>>ar[i];}

  for(int i=0;i<=n;i++){
    for(int j=0;j<=w;j++){
      if(i==0||j==0)
      dp[i][j]=0;
    else if(we[i-1]<=j){
      dp[i][j]=max(dp[i-1][j],(ar[i-1]+dp[i-1][j-we[i-1]]));
    }
    else dp[i][j]=dp[i-1][j];
    }
  }
  cout<<dp[n][w];return 0;}










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

class Radix {
private:
  const char* s;
  int a[128];
public:
  Radix(const char* s = "0123456789ABCDEF") : s(s) {
    int i;
    for(i = 0; s[i]; ++i)
      a[(int)s[i]] = i;
  }
  std::string to(long long p, int q) {
    int i;
    if(!p)
      return "0";
    char t[64] = { };
    for(i = 62; p; --i) {
      t[i] = s[p % q];
      p /= q;
    }
    return std::string(t + i + 1);
  }
  std::string to(const std::string& t, int p, int q) {
    return to(to(t, p), q);
  }
  long long to(const std::string& t, int p) {
    int i;
    long long sm = a[(int)t[0]];
    for(i = 1; i < (int)t.length(); ++i)
      sm = sm * p + a[(int)t[i]];
    return sm;
  }
};

int main() {
    int n, k;
    cin >> n >> k;
    Radix r;
    cout << r.to(n, k).size() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    cout << s.front() << n-2 << s.back() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	ll n, x; cin >> n >> x;
	vector<ll> a(n);
	for( auto &k : a ) cin >> k;
	ll cnt = 0;
	for( int i = 0; i < n-1; ++i ){
		if( i == 0 && x-a[i] < 0 ){
			cnt += a[i+1]-(x-a[i]);
			a[i] = x-a[i+1];
			a[i+1] = 0; 
		} else if( a[i+1] + a[i] > x ){
			cnt += a[i+1]-x+a[i];
			a[i+1] = x-a[i];
		}
	}
	/* for( int i = 0; i < n; ++i ){
		cout << a[i] << ' ';
	} cout << endl; */
	cout << cnt << endl;
}

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

int main() {
 int A, B, K, L, J, H;
 cin >> A >> B;
 K = A+B;
 L = K%3;
 J = A%3;
 H = B%3;
 if (L == 0){
     cout << "Possible";
 }
 else if (J == 0){
     cout << "Possible";
 }
 else if(H == 0){
     cout << "Possible";
 }
     else {
         cout << "Impossible";
     }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,x,p=0;
	cin>>a>>b>>c>>x;
	for(int i=0;i<=a;i++)
	{
		for(int j=0;j<=b;j++)
		{
			for(int k=0;k<=c;k++)
			{
				if(500*i+100*j+50*k==x)
				{
					p++;
				}
			}
		}
	}
	cout<<p;
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  int n;cin>>n;
  int sum=0;
  int tmp=n;
  while(tmp!=0){
    sum+=tmp%10;
    tmp=tmp/10;
  }
  if(n%sum==0){
    std::cout << "Yes" << '\n';
  }else{
    std::cout << "No" << '\n';
  }
  return 0;
}


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

template<typename T, T mod>
struct modint {
private:
  T x;

public:
  modint(): x((T)0) {}
  modint(T y): x(y >= 0? y % mod: (mod - (-y) % mod) % mod) {}

  T get() {
    return x;
  }

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

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

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

  modint &operator/=(const modint &p) {
    *this *= p.inverse();
    return *this;
  }

  modint operator-() const { return modint(-x); }
  modint operator+(const modint &p) const {return modint(*this) += p; }
  modint operator-(const modint &p) const {return modint(*this) -= p; }
  modint operator*(const modint &p) const {return modint(*this) *= p; }
  modint operator/(const modint &p) const {return modint(*this) /= p; }

  bool operator==(const modint &p) const { return x == p.x; }
  bool operator!=(const modint &p) const { return x != p.x; }

  modint inverse() const {
    T a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return modint(u);
  }

  modint pow(int e) const {
    T a = 1, p = x;
    while(e > 0) {
      if (e % 2 == 0) {
	p = (p * p) % mod;
	e /= 2;
      } else {
	a = (a * p) % mod;
	e--;
      }
    }
    return modint(a);
  }
};

const long long MOD = 1000000007;

using mi = modint<long long, MOD>;

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  for (int i = 0; i < h; ++i) cin >> a[i];

  vector< vector<mi> > dp(h, vector<mi>(w, 0));
  dp[0][0] = 1;

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (i + 1 < h && a[i + 1][j] == '.') dp[i + 1][j] += dp[i][j];
      if (j + 1 < w && a[i][j + 1] == '.') dp[i][j + 1] += dp[i][j];
    }
  }

  cout << dp[h - 1][w - 1].get() << '\n';
  return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <vector>
#include <algorithm>
#define NMAX 200005

using namespace std;

int n, k,freq[NMAX];
vector <int> a;
vector <pair <int, int> > b;
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (!freq[x]) {
			a.push_back(x);
		}
		freq[x]++;
	}
	sort(a.begin(), a.end());
	if (a.size() <= k) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < a.size(); i++) {
		b.push_back({ freq[a[i]],a[i] });
	}
	sort(b.begin(), b.end());
	int taken = 0;
	for (int i = 0, j = b.size() - 1; i < k; i++, j--) {
		taken += b[j].first;
	}
	cout << n - taken;
	return 0;
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
using ll = long long;
int main(){
	ll n,w;
  	scanf("%lld%lld",&n,&w);
    vector<ll> dp(w + 1);
    for(int i=0;i<n;i++){
     	ll we,val;
     	scanf("%lld%lld",&we,&val);
     	for(int j=w-we;j>=0;j--){
      		dp[j+we]=max(dp[j+we],dp[j]+val);
     	}
    }

	ll answer = 0;
   	for(int i=0;i<=w;i++) {
        answer=max(answer, dp[i]);
   	}
   	printf("%lld\n", answer);
}


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VLL p(n);
  rep(i,n) cin >> p[i];
  rep(i,n) p[i]--;
  VLL idx(n);
  rep(i,n) idx[p[i]] = i;
  ll ans = 0;
  set<int> st;
  for(int i = n-1; i >= 0; i--){

    st.insert(idx[i]);
    auto itr = st.find(idx[i]);
    VLL l(2,-1);
    VLL r(2,n);

    // find left
    auto litr = itr;
    rep(j,2){
      if( litr == st.begin()) break;
      litr--;
      l[j] = *litr;
    }

    // find right
    auto ritr = itr;
    rep(j,2){
      ritr++;
      if( ritr == st.end()) break;
      r[j] = *ritr;
    }

    VLL ls(2),rs(2);

    ls[0] = *itr - l[0];
    ls[1] = l[0] - l[1];

    rs[0] = r[0] - *itr;
    rs[1] = r[1] - r[0];

    ll c = rs[0] * ls[1] + rs[1] * ls[0];
    ans += c * (i+1);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define int         ll int
#define float       double
#define	endl		'\n'
#define maxpq       priority_queue<ll>
#define minpq       priority_queue<ll, vector<ll>, greater<ll> >
#define mii         map<int,int>
#define msi         map<string,int>
#define mis         map< int, string>
#define mpi         map<pair< int, int>, int>
#define pii         pair< int, int>
#define vi          vector< int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define EPS         1e-9
#define INF         1e18
#define PI          3.14159265358979323846
#define MAXI        1000000
#define what_is(x)  cerr << #x << " is " << x << endl;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
#define N 100005

signed main()
{
	fast;
	int t=1;
	//cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		int i,j,k;
		char arr[n][m];
		for(i=0;i<=n-1;i++)
		{
			for(j=0;j<=m-1;j++)
			{
				cin>>arr[i][j];
			}
		}
		int dp[n+1][m+1];
		memset(dp,0,sizeof(dp));
		dp[1][1]=1;
		for(i=2;i<=n;i++)
		{
			if(arr[i-1][0]=='#') break;
			dp[i][1]=1;
		}
		for(j=2;j<=m;j++)
		{
			if(arr[0][j-1]=='#') break;
			dp[1][j]=1;
		}
		for(i=2;i<=n;i++)
		{
			for(j=2;j<=m;j++)
			{
				int res=0;
				if(arr[i-2][j-1]!='#')
				{
					res+=dp[i-1][j]%hell;
				}
				if(arr[i-1][j-2]!='#')
				{
					res+=dp[i][j-1]%hell;
				}
				dp[i][j]=res%hell;
			}
		}
		
		cout<<dp[n][m]<<endl;
	}
}

Measured memory_bytes: 12380
using System;
class Program
{
    static void Main()
    {
        string z;
        string x = Console.ReadLine();
        string[] a = x.Split(' ');
        int n = int.Parse(a[0]);
        int m = int.Parse(a[1]);
        int o = int.Parse(a[2]);
        if (n <= m)
        {
            if (m <= o)
            {
                z = a[0] + " " + a[1] + " " + a[2];
            }
            else if (n <= o)
            {
                z = a[0] + " " + a[2] + " " + a[1];
            }
            else
            {
                z = a[2] + " " + a[0]+ " "+  a[1];
            }
        }

        else
        {
            if (n <= o)
            {
                z = a[1]+" " + a[0]+" " + a[2]; //mno
            }
            else if (m <= o)
            {
                z = a[1] + " " + a[2] + " " + a[0]; //mno
            }
            else
            {
                    z = a[2] + " " + a[1] + " " + a[0]; //mno
            }

        }
        Console.WriteLine(z);
    }
}


Measured memory_bytes: 15944
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

vector<P> v;

bool comp(P a, P b){
	return (a.first > b.first);
}

int main(void){
	int m,i=0;
	ll n,a,b,c,ans=0ll;
	cin >> n >> m;
	for(i=0; i<n; ++i){
		cin >> a;
		v.push_back(P(a,1ll));
	}
	for(i=0; i<m; ++i){
		cin >> b >> c;
		v.push_back(P(c,b));
	}
	sort(v.begin(),v.end(),comp);
	i = 0;
	while(n>0){
		ans += v[i].first*(min(v[i].second,n));
		n -= min(v[i].second,n);
		++i;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 6512
/**
 * Created by hiramekun at 22:27 on 2019-12-16.
 */
/**
 * Created by hiramekun at 20:44 on 2019-12-08.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll h, w;
    cin >> h >> w;
    vvl a(h, vl(w)), b(h, vl(w));
    rep(i, h) rep(j, w) cin >> a[i][j];
    rep(i, h) rep(j, w) cin >> b[i][j];

    ll max_diff = 2 * 80 * (h + w);
    bool dp[h][w][max_diff];
    rep(i, h) rep(j, w) rep(l, max_diff) dp[i][j][l] = false;

    ll mid = 80 * (h + w);
    dp[0][0][b[0][0] - a[0][0] + mid] = true;
    dp[0][0][-b[0][0] + a[0][0] + mid] = true;

    rep(i, h) {
        rep(j, w) {
            rep(l, max_diff) {
                if (dp[i][j][l]) {
                    if (i + 1 <= h - 1) {

                        dp[i + 1][j][l + b[i + 1][j] - a[i + 1][j]] = true;
                        dp[i + 1][j][l - b[i + 1][j] + a[i + 1][j]] = true;
//                        vl candi{l + b[i + 1][j] - a[i + 1][j],
//                                 l - b[i + 1][j] + a[i + 1][j]};
//
//                        each(e, candi) dp[i + 1][j][e] = true;
                    }
                    if (j + 1 <= w - 1) {

                        dp[i][j + 1][l + b[i][j + 1] - a[i][j + 1]] = true;
                        dp[i][j + 1][l - b[i][j + 1] + a[i][j + 1]] = true;
//                        vl candi{l + b[i][j + 1] - a[i][j + 1],
//                                 l - b[i][j + 1] + a[i][j + 1]};
//
//                        each(e, candi)dp[i][j + 1][e] = true;
                    }
                }
            }
        }
    }
    ll ans = ll_inf;
    rep(i, max_diff) {
        if (dp[h - 1][w - 1][i]) ans = min(ans, abs(i - mid));
    }
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 160384