akhauriyash/Code-Regression huggingface dataset:
if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  require 'rubygems'
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'}, Gem.ruby, $0)
end

N = gets.to_i
G = readlines.each_with_object(Array.new(N + 1){[]}){|l, o| a, b = l.split.map(&:to_i); o[a] << b; o[b] << a}
M = 10**9 + 7

@fac, @inv, @fiv = [1, 1], [1, 1], [1, 1]
(2 .. N).each do |i|
  @fac[i] = @fac[i - 1] * i % M
  @inv[i] = M - @inv[M % i] * (M / i) % M
  @fiv[i] = @fiv[i - 1] * @inv[i] % M
end
@s, @dp, @ans = Array.new(N + 1, 0), Array.new(N + 1, 0), Array.new(N + 1, 0)

def dfs1(u, v, d)
  s, i = 1, 1
  G[u].each do |t|
    next if t == v
    s += dfs1(t, u, d + 1)
    i *= @dp[t]*@fiv[@s[t]]%M
  end
  @dp[u] = i*@fac[s - 1]%M
  @s[u] = s
end

def dfs2(u, v, x)
  x = x.nil? ? @dp[1] : x*@s[u]*@inv[N - @s[u]]%M
  @ans[u] = x
  G[u].each do |t|
    next if t == v
    dfs2(t, u, x)
  end
end

dfs1(1, nil, 0)
dfs2(1, nil, nil)
puts @ans.drop(1)

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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug if(true)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
	int n,i,j,k;
	scanf("%d",&n);
	ll sum = 0;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			int gcd = __gcd(j,i);
			for(k=1;k<=n;k++){
				int gcd1 = __gcd(gcd, k);
				sum += gcd1;
			}
		}
	}
	printf("%lld\n",sum);
	return 0;
};

Measured memory_bytes: 3824
from itertools import accumulate
N,Q = map(int,input().split())
S = str(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
sl = [0]*N
for i in range(N):
  if S[i:i+2] == "AC":
    sl[i] = 1
slr = [0]+list(accumulate(sl))
ans = 0
for l,r in lr:
  ans = slr[r-1]-slr[l-1]
  print(ans)


Measured memory_bytes: 33164
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



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

	string s1, s2;
	int n, i, j, k, sl1, sl2, maxx, ans;

	cin >> n >> s1 >> s2;
	sl1 = s1.length(); sl2 = s2.length();
	if (sl1 + sl2 <= n) {
		ans = n;
	}
	else {
		maxx = 0;
		for (i = 0; (i < sl1) && (i < sl2); i++) {
			if (s1.substr(sl1 - 1 - i) == s2.substr(0, i + 1)) maxx = i + 1;
		}
		ans = max(sl1 + sl2 - maxx, n); 
	}
	cout << ans << "\n";


	return 0;
}



Measured memory_bytes: 504
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

type PY struct {
	Id     int
	P      int    // 所属している県
	Y      int    // 誕生都市
	Rank   int    // 誕生時の順番
	Serial string // シリアル
}

func (p *PY) NewSerial() {

	upper := strings.Repeat("0", (6-len(strconv.Itoa(p.P)))) + strconv.Itoa(p.P)
	lower := strings.Repeat("0", (6-len(strconv.Itoa(p.Rank)))) + strconv.Itoa(p.Rank)
	p.Serial = upper + lower
}

type PYS []PY

func (p PYS) Len() int {
	return len(p)
}

func (p PYS) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

type ByP struct {
	PYS
}

func (b ByP) Less(i, j int) bool {
	return b.PYS[i].P < b.PYS[j].P
}

type ByY struct {
	PYS
}

func (b ByY) Less(i, j int) bool {
	return b.PYS[i].Y < b.PYS[j].Y
}

type ByID struct {
	PYS
}

func (b ByID) Less(i, j int) bool {
	return b.PYS[i].Id < b.PYS[j].Id
}

var group = make(map[int][]PY)
var (
	n int
	m int
)

func main() {
	sc.Split(bufio.ScanWords)

	n, m = nextInt(), nextInt()
	for i := 0; i < m; i++ {
		p, y := nextInt(), nextInt()
		group[p] = append(group[p], PY{Id: i, P: p, Y: y, Rank: 0, Serial: ""})
	}

	// fmt.Println(group)

	ans := make([]PY, 0)

	for _, v := range group {
		sort.Sort(ByY{v})
		for i := 0; i < len(v); i++ {
			v[i].Rank = i + 1
			v[i].NewSerial()
			ans = append(ans, v[i])
		}
	}

	// fmt.Println(group)

	sort.Sort(ByID{ans})
	for _, a := range ans {
		fmt.Println(a.Serial)
	}
}


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

int main() {
	int N; string S, T; cin >> N >> S >> T;
	int p;
	for (p = N; p >= 0; p--) {
		if (S.substr(N-p, p) == T.substr(0, p)) break;
	}
	cout << 2*N-p << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using LP = pair<int, int>;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const double PI=3.14159265358979323846;

int mod = 1e9+7;
int INF = 1e9+7;


int main(){

  double H, W, x, y;
  cin >> W >> H >> x >> y;

  double area = W*H/2;

  if(2*x==W && 2*y==H){
    printf("%.15f 1\n", area);
  }else{
    printf("%.15f 0\n", area);
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

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

        String s = sc.next();
        int max = 0;
        int currentLength = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            switch (c) {
                case 'A':
                case 'C':
                case 'G':
                case 'T':
                    currentLength++;
                    break;
                default:
                    currentLength = 0;
                    break;
            }

            if (max < currentLength) {
                max = currentLength;
            }
        }

        System.out.println(max);
    }
}


Measured memory_bytes: 21844
from copy import deepcopy

H, W, K = map(int, input().split())
board = []
for _ in range(H):
  board.append(input())
ans = 0

for h in range(0, 2**H):
  for w in range(0, 2**W):
    h_str = format(h, 'b').zfill(H)
    w_str = format(w, 'b').zfill(W)
    test = deepcopy(board)
    for i in range(H):
      if h_str[i] == '1':
        test[i] = 'r'*W
      for j in range(W):
      	if w_str[j] == '1':
          test[i] = test[i][:j] + 'r' + test[i][j+1:]
    counter = 0
    for row in test:
      counter += row.count('#')
    if counter == K:
      ans += 1
print(ans)

Measured memory_bytes: 9336
n=int(input())
a={}
for _ in range(n):
  m=input()
  if m in a:
    a[m]+=1
  else:
    a[m]=1
b=[]
v=max(a.values())
for k in a.items() :
     if k[1] == v:
      b.append(k[0])
b.sort()
for l in b:
  print(l)

Measured memory_bytes: 32092
#include <stdio.h>

int yu(int,int);//最大公約数を求める,xのほうが大きい
int sokutei(int,int);//一つめの引数が大きいなら０、小さいなら１、同じなら２を出力

int main(){
  int x,y;
  scanf("%d %d",&x,&y);
  if(sokutei(x,y)==0){
    printf("%d\n",yu(x,y));
  }
  else if(sokutei(x,y) == 1){
    printf("%d\n",yu(y,x));
  }
  else if(sokutei(x,y) == 2){
    printf("%d\n",x);
  }
  return 0;
}

int sokutei(int x,int y)
{
  if(x < y)return 1;
  else if (x > y)return 0;
  else if(x == y)return 2;
}
int yu(int x,int y)
{
  int result,amari;
  while(1){
    amari = x%y;
    x = y;
    if(amari == 0){
      result = y;
      break;
    }
    y = amari;
  }
  return result;
}



Measured memory_bytes: 2080
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <string.h>
#include <bitset>
#include <map>
#include <climits>
#include <set>

using namespace std;

int main()
{
    int N;
    cin >> N;
    using ull = unsigned long long;
    ull n = 1E+9 + 7;
    ull p = 1;
    for (int i = 1; i <= N; ++i)
    {
        p *= (i % n);
        p = p % n;
    }
    cout << p << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int datas[200005];
int n;
LL eval(LL krg)
{
	LL ret=0;
	for(int a=0;a<n;a++)
	{
		ret+=abs(datas[a]-(krg+a+1));
	}
	return ret;
}
int main()
{
	scanf("%d", &n);
	for(int a=0;a<n;a++)
	{
		scanf("%d", &datas[a]);
	}
	LL L=-2000000000, R=2000000000;
	while(R-L>100)
	{
		LL mid1=(L*2+R)/3;
		LL mid2=(L+R*2)/3;
		LL h1=eval(mid1), h2=eval(mid2);
		if(h1 < h2)
		{
			R=mid2;
		}
		else
		{
			L=mid1;
		}
	}
	LL ret=1e18;
	for(LL a=L;a<=R;a++)
	{
		LL h=eval(a);
		ret=min(ret, h);
	}
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
#define inf 1e9+7
#define pb push_back
#define make make_pair
#define kaku(a) cout << a << endl;
 
using namespace std;
 
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define PI 3.14159265359
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}
long long lcm(long long a,long long b){ return a/gcd(a,b)*b;}
 
typedef pair<ll,ll> Pair;
 
int main(){
    ll n,m ;
    cin >> n >> m;
    vector<ll> g[n];
    rep(i,m){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        g[a].pb(b);
    }
    ll d[n][3];
    ll visit[n][3];
    rep(i,n) rep(j,3) {
        d[i][j]=inf;
        visit[i][j]=false;
    }
    
    queue<Pair> que;//頂点とどの段階か
    ll s,t;
    cin >> s >> t;
    s--;t--;
    que.push(make(s,0));
    d[s][0]=0;
    
    while(!que.empty()){
        Pair ima=que.front();
        que.pop();
        if(visit[ima.first][ima.second]) continue;
        visit[ima.first][ima.second]=true;
        for(ll b : g[ima.first]){
            ll modit=(ima.second+1)%3;
            if(visit[b][modit]) continue;
            else{
                d[b][modit]=d[ima.first][ima.second]+1;
                que.push(make(b,modit));
            }
        }
    }
    if(d[t][0]==inf) {kaku(-1);}
    else{kaku(d[t][0]/3);}
}



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



int main(){
	
	int N;
	cin>>N;
	
	vector<int> x(N);
	
	int ans = 1;
	int now = 1;
	for(int i=0;i<N;i++){
		cin>>x[i];
	}
	
	for(int i=0;i<N;i++){
		ans = mod(ans * now);
		if(i==0){
			x[i]=1;
			now++;
		}
		else{
			if(x[i-1]+2 <= x[i]){
				x[i] = x[i-1]+2;
				now++;
			}
			else{
				x[i] = x[i-1];
			}
		}
		
	}
	
	cout<<ans<<endl;


	return 0;
}

Measured memory_bytes: 640
s = input()
is_a = False
cnt_c = s[2:-1].count("C")
cnt_l = 0
if s[0] == "A":
    is_a = True
else:
    pass
for letter in s:
    if letter.isupper():
        cnt_l += 1
    else:
        continue
if is_a == True and cnt_c == 1 and cnt_l == 2:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3060
import sys
import math
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    D, G = map(int, input().rstrip().split())
    problem_list = []
    for i in range(1, D+1):
        p, c = map(int, input().rstrip().split())
        problem_list.append((p, c + (i * 100 * p), i * 100))

    min_problems = 10**9
    for bit in range(1 << D):
        problem_num = 0
        total_score = 0
        unsolved_problems = None

        for i in range(D):
            if bit & (1 << i):
                # ボーナスポイントを取得
                problem_num += problem_list[i][0]
                total_score += problem_list[i][1]
                if problem_num >= min_problems:
                    break
            else:
                # ボーナスポイントを取得しない
                unsolved_problems = problem_list[i]

        if problem_num >= min_problems:
            continue

        if G <= total_score:
            min_problems = min(min_problems, problem_num)
        else:
            diff = G - total_score
            num, _, score = unsolved_problems
            needed_num = math.ceil(diff / score)
            if num > needed_num:
                problem_num += needed_num
                total_score += needed_num * score
                min_problems = min(min_problems, problem_num)
    print(min_problems)

if __name__ == '__main__':
    main()

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

int main(){
	int N;
	cin >> N;
	vector<int> P(N);
	for(int i = 0; i < N; i++)cin >> P.at(i);
	int cnt = 0;
	for(int i = 1; i < N - 1; i++){
		int Pax = max(max(P.at(i - 1), P.at(i)), P.at(i + 1));
		int Pin = min(min(P.at(i - 1), P.at(i)), P.at(i + 1));
		if(P.at(i) != Pax && P.at(i) != Pin) cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<ll,pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main(){
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n), b;
    rep(i, n)cin >> a[i];
    ll ans = inf; b = a;
    rep(i, n){
        rep(j, n)chmin(b[j], a[(j+i) % n]);
        chmin(ans, i*x + accumulate(all(b), 0LL));
    }
    cout << ans << endl;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n=1,cnt=0,ans=0,a[100][100],b,c,cmp,data,m,h,x,y,xcmp=0,ycmp=0,sum=0;

string s,w;

vector<int> z;

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

       rep(i,3){
           rep(j,3){
               cin >> a[i][j];
               //Cout(a[0][1]);
           }
       }
      if(a[0][0]-a[1][0]==a[0][1]-a[1][1] && a[0][1]-a[1][1]==a[0][2]-a[1][2]){
        if(a[1][0]-a[2][0]==a[1][1]-a[2][1] && a[1][1]-a[2][1]==a[1][2]-a[2][2]){
         Cout("Yes");
         return 0;
      }  
      }
      Cout("No");
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(int argc, char const *argv[])
{
  char day[3];
  scanf("%s",&day);
  if(day[0]=='S'){
    if(day[1]=='U'){
      printf("7");
      return 0;
    }else{
      printf("1");
      return 0;
    }
  }
  if(day[0]=='M'){
    printf("6");
    return 0;
  }
  if(day[0]=='T'){
    if(day[1]=='U'){
      printf("5");
      return 0;
    }else{
      printf("3");
      return 0;
    }
  }
  if(day[0]=='W'){
    printf("4");
    return 0;
  }
  if(day[0]=='F'){
    printf("2");
    return 0;
  }
}


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


typedef long long int ll;

int main()
{
	ll n;
	cin>>n;
	ll ret=0;
	ll pre=0;
	
	for(ll i=0; i<n; i++) {
		ll x;
        cin>>x;
		if(pre==0) {
			ret += x-1;
			pre=1;
		}
		else if(x==pre+1) {
			pre++;
		}
		else if(x>pre+1) {
			ret += (x-1)/(pre+1);
		}
	}
	cout<<ret<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N , M;
    cin >> N >> M;
    vector<int> vec(M);
      for (int i = 0; i < M; i++) {
        cin >> vec.at(i);
      }
    int a=0;
    for(int i = 0; i < M; i++){
        a += vec.at(i);
    }
    if (N < a){
        cout << "-1" <<endl;
    }
    else{
        cout << N-a << endl;
    }
    }


Measured memory_bytes: 3672
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef struct elemts{
  int a;
  int b;
} Elemts;

Elemts container[100000];

int cmpElemts(const void* x, const void* y){
  const Elemts* xx=(const Elemts*)x;
  const Elemts* yy=(const Elemts*)y;
  return xx->a>yy->a;
}

int main(){
  int N=0;
  long K=0;
  memset(container,-1,sizeof(container));
  cin>>N>>K;
  for(int i=0;i<N;i++)
    cin>>container[i].a>>container[i].b;
  qsort(container,N,sizeof(Elemts),cmpElemts);
  //for(int i=0;i<N;i++)
  //  cout<<container[i].a<<endl;
  long cnt=0;
  int index=0;
  while(cnt<K){
    cnt+=container[index].b;
    index++;
  }
  cout<<container[--index].a<<endl;
  return 0;
}

Measured memory_bytes: 1788
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define rep(i, j) FOR(i, 0, j, 1)
#define rrep(i, j) RFOR(i, j, 0, 1)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define endl "\n"
#define MOD 1000000007
#define DEB(x) cout<<"##"<<x<<"##"<<endl;
void solve()
{ 
	ll n,count1=0,ans=0;
	cin>>n;
	while(n%2==0)
	{
		n=n/2;
		count1++;
	}
	ans+=(sqrt(1.0+8*count1)-1)/2;
	for(int i=3;i<=sqrt(n);i+=2)
	{
		count1=0;
		if(n==1)
			break;
		while(n%i==0)
		{
			n=n/i;
			count1++;
		}
		ans+=(sqrt(1.0+8*count1)-1)/2;
	}
	if(n!=1)
	{
		ans++;	
	}
	cout<<ans;
} 
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int tt=1;
	//cin>>tt;
	while(tt--)
	solve(); 	
	return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
char s[100005];
int main(){
	int n,i,j,k,o,p,l;
	scanf("%s",s+1);
	n=strlen(s+1);
	int ok=1;
	for(i=3;i<=n;i++)
	if(s[i]!=s[i-2]){ok=0;break;}
	if(ok==1)printf("Second");
	else{
	if(s[1]==s[n]){
	if(n%2==0)printf("First");
	else printf("Second");
	}
	else{
	if(n%2==1)printf("First");
	else printf("Second");
	}
	}
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
////////////////////////////////////////////////
int main()
{
    string n;
    cin >> n;
    int le, cnt = 0;
    le = n.length();

    rep(i, le)
    {
        cnt += (int)(n[i]) - 48;
    }
    if (cnt % 9 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

struct PrimeNumber
{
    //O(sqrt(n))
    bool is_prime(long long n){
        for(long long i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return n != 1;
    }

    //O(sqrt(n))  isn't sorted
    vector<long long> divisor(long long n){
        vector<long long> res;
        for(long long i = 1; i * i <= n; i++){
            if(n % i == 0){
                res.push_back(i);
                if(i != n / i) res.push_back(n / i);
            }
        }
        return res;
    }

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

    //O(sqrt(n))
    map<long long, long long> prime_factor(long long n){
        map<long long, long long> res;
        for(long long i = 2; i * i <= n; i++){
            while(n % i == 0){
                n /= i;
                res[i]++;
            }
        }
        if(n != 1) res[n] = 1;
        return res;
    }

    //O(n log log n)
    vector<long long> eratosthenes(long long n){
        vector<long long> prime;
        vector<bool> is_prime(n + 1, true);
        long long p = 0;
        is_prime[0] = false; is_prime[1] = false;
        for(long long i = 2; i <= n; i++){
            if(is_prime[i]) prime.push_back(i);
            for(long long j = 2 * i; j <= n; j += i) is_prime[j] = false;
        }
        return prime;
    }
};

vector<ll> calc(ll n){
    vector<ll> table(n+1);
    for(ll i = 1; i <= n; i++){
        for(ll j = i; j <= n; j += i){
            table[j] += 1;
        }
    }
    return table;
}


int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n; cin >> n;
    PrimeNumber pn;

    /*
    vector<ll> vec = pn.divisor(100);
    rep(i, vec.size()){
        cout << vec[i] << endl;
    }
    cout << vec.size() << endl;
    */

    /*
    ll ans = 0;
    rep(i, n){
        //vector<ll> tmp = pn.divisor((i+1));
        ll tmp2 = pn.divisor2((i+1));
        ans += (i+1) * tmp2;
    }
    cout << ans << endl;
    */
   
    vector<ll> res = calc(n);
    /*
    rep(i, res.size()){
        cout << res[i] << endl;
    }
    */
    ll ans = 0;
    rep(i, n){
        ans += (i+1) * res[i+1];
    }
    cout << ans << endl;

}

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

int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i=0;i<n;i++){cin >> a[i];}
	double ans=0;
	for(int i=0;i<n;i++){ans+= 1.0/a[i];}
	cout << 1.0/ans << endl;
	return 0;
}


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

int main(){
  int A, B;
  cin >> A >> B;
  if(A<=8){
    if(B<=8){
      cout << "Yay!" << endl;
    }else{
      cout << ":(" << endl;
    }
    return 0;
  }
  if(B<=8){
    if(A<=8){
      cout << "Yay!" << endl;
    }else{
      cout << ":(" << endl;
    }
    return 0;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const int inf=1145141919;
const int dd[]={0,-1,0,1,0};
using namespace std;
int a[50],b[50],c[50],d[50],e[50];
signed main(){
	int n,m;
	int i,j;
	cin>>n>>m;
	for(i=0;i<n;i++)
		cin>>a[i]>>b[i];
	for(i=0;i<m;i++)
		cin>>c[i]>>d[i];
	for(i=0;i<n;i++){
		int u=inf,v=-1;
		for(j=0;j<m;j++){
			int x=abs(a[i]-c[j])+abs(b[i]-d[j]);
			if(x<u){
				u=x;
				v=j;
			}
		}
		e[i]=v;
	}
	for(i=0;i<n;i++)
		cout<<e[i]+1<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, begin, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

ll Fac(ll N, vector<ll> &memo1);
ll comb(ll n, ll r, vector<ll> &memo1, vector<ll> &memo3);

int main()
{
    int N;
    cin >> N;
    map<int, int> map;
    vector<int> A(N);
    vector<ll> memo1(2 * 100000 + 1, -1), memo3(2 * 100000 + 1, -1);
    rep(i, 0, N)
    {
        cin >> A.at(i);
        map[A.at(i)]++;
    }
    ll sum = 0;
    rep(i, 1, N + 1)
    {
        sum += comb(map[i], 2, memo1, memo3);
    }
    rep(i, 0, N)
    {
        cout << sum - map.at(A.at(i)) + 1 << endl;
    }
}

ll Fac(ll N, vector<ll> &memo1)
{
    if (memo1.at(N) != -1)
    {
        return memo1.at(N);
    }
    if (N == 0)
    {
        return memo1.at(0) = 1;
    }
    else
    {
        return memo1.at(N) = (N * Fac(N - 1, memo1));
    }
}

ll comb(ll n, ll r, vector<ll> &memo1, vector<ll> &memo3)
{
    if (n < r)
    {
        return 0;
    }
    ll A = Fac(r, memo1);
    ll B = 1;
    for (int i = 1; i <= r; i++)
    {
        B = (B * (n - i + 1));
    }
    return memo3.at(n) = B / A;
}


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

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

    ll a[n];

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

    sort(a, a + n);

    ll sum[n];
    sum[0] = a[0];
    for(int i = 1; i < n; i++){
        sum[i] = sum[i - 1] + a[i];
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        if(i != n - 1){
            if(sum[i] * 2 >= a[i + 1]){
                ans++;
            }else{
                ans = 0;
            }
        }else{
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
import sys

inp = list(map(lambda x: int(x), input().split(" ")))
n = inp[0]
k = inp[1]
inp = list(map(lambda x: int(x), input().split(" ")))

dp = [0]*(n)

for i in range(n-1):
    dp[i+1] = dp[i] + abs(inp[i+1]-inp[i])
    for j in range(2,k+1):
        if (i+1-j>=0):
            dp[i+1] = min(dp[i+1], dp[i+1-j] + abs(inp[i+1]-inp[i+1-j]))

print(dp[-1])

Measured memory_bytes: 52704
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main() {
	int N;
	scanf("%d", &N);
	double A[N];
	for (int i = 0; i < N; ++i) scanf("%lf", &A[i]);
	long long B[N], ans = 0;
	for (int i = 0; i < N; ++i) B[i] = llround(A[i] * 1000000000LL);
	vector<long long> p5[19];
	int p2[44];
	fill_n(p2, 44, 0);
	for (int i = 0; i < N; ++i) {
		int x = 0;
		long long temp = B[i];
		while (temp % 5 == 0) ++x, temp /= 5;
		p5[x].push_back(B[i]);
	}
	for (int i = 0; i < 19; ++i) {
		for (long long j: p5[18 - i]) {
			int x = 0;
			long long temp = j;
			while (temp % 2 == 0) ++x, temp /= 2;
			++p2[x];
		}
		for (long long j: p5[i]) {
			int x = 0;
			long long temp = j;
			while (temp % 2 == 0) ++x, temp /= 2;
			for (int k = max(0, 18 - x); k < 44; ++k) ans += p2[k];
			if (i * 2 >= 18 && x * 2 >= 18) --ans;
		}
	}
	printf("%lld", ans / 2);
	return 0;
}

Measured memory_bytes: 8076
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define LLINF (1<<60)
#define MOD 1000000007
# define rep(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;

int main() {
    int n, k;
    int zero = 0;
    vector<int> right, left;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t < 0)left.pb(-t);
        else if (t == 0)zero++;
        else right.pb(t);
    }
    sort(left.begin(), left.end());
    int ans = INF;
    for (int getleft = 0; getleft <= left.size(); getleft++) {
        int getright = k - zero - getleft;

        if (getright == 0) {
            if (getleft == 0) {
                ans = 0;
                cout << ans;
                return 0;
            }
            else {
                if (0 <= getleft && getleft <= left.size()) {
                    ans = min(ans, left[getleft - 1]);
                }
            }
        }
        else if (getleft == 0) {
            if (0 <= getright && getright <= right.size()) {
                ans = min(ans, right[getright - 1]);
            }
        }
        else {
            if (0 <= getright && getright <= right.size() && 0 <= getleft && getleft<=left.size()) {
                ans = min(ans, max(right[getright - 1], left[getleft - 1]) + min(right[getright - 1], left[getleft - 1]) * 2);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

signed main(){
        llin(n);
        llin(l);
        ll k=10000;
        ll a=0;
        FOR(i,0,n-1){
                if(abs(k)>abs(l+i)) k=l+i;
                a+=l+i;
        }
        sal(a-k)
}


Measured memory_bytes: 256
from itertools import permutations
n = int(input())
P = tuple(map(int,input().split()))
Q = tuple(map(int,input().split()))

dict = {}
d = [i for i in range(1,n+1)]
i = 1
for x in permutations(d,n):
    dict[x] = i
    i += 1

print(abs(dict[P]-dict[Q]))

Measured memory_bytes: 43376
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
int main()
{
	int num, gen;
	scanf("%d%d", &num, &gen);
	vector<pii>v;
	ll sum = 0;
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		v.push_back(make_pair(za, zb));
		if ((gen&za) == za)sum += zb;
	}
	ll maxi = sum;
	for (int i = 29; i >= 0; i--)
	{
		if (0 == (gen&(1 << i)))continue;
		ll mok = (gen - (1 << i)) | ((1 << i) - 1);
		ll s = 0;
		for (int j = 0; j < num; j++)
		{
			if ((mok&v[j].first) == v[j].first)s += v[j].second;
		}
		maxi = max(maxi, s);
	}
	printf("%lld\n", maxi);
}

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

namespace AtCoderPre
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();

            if(a >= 3200)
            {
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("red");
            }


        }
    }
}

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

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

  if (N == "AKIHABARA")
    cout << "YES" << endl;
  else if (N == "KIHABARA")
    cout << "YES" << endl;
  else if (N == "AKIHBARA")
    cout << "YES" << endl;
  else if (N == "AKIHABRA")
    cout << "YES" << endl;
  else if (N == "AKIHABAR")
    cout << "YES" << endl;
  else if (N == "KIHBARA")
    cout << "YES" << endl;
  else if (N == "KIHABRA")
    cout << "YES" << endl;
  else if (N == "KIHABAR")
    cout << "YES" << endl;
  else if (N == "AKIHBRA")
    cout << "YES" << endl;
  else if (N == "AKIHBAR")
    cout << "YES" << endl;
  else if (N == "AKIHABR")
    cout << "YES" << endl;
  else if (N == "KIHBRA")
    cout << "YES" << endl;
  else if (N == "KIHABR")
    cout << "YES" << endl;
  else if (N == "KIHBAR")
    cout << "YES" << endl;
  else if (N == "AKIHBR")
    cout << "YES" << endl;
  else if (N == "KIHBR")
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
bool prime(int n) {
	if (n <= 1) 
	    return false;
	for (int i = 2; i * i < n; i++){
		if (n % i == 0) 
		    return false;
	}
	return true;
}
 
int main(){
	int x;
	cin >> x;
	while (!prime(x)){
	    x++;
	}
	cout << x << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var n = sc.nextInt();
		var a = new int[n];
		for (var i = 0; i < n - 1; i++) {
			a[sc.nextInt() - 1]++;
		}
		sc.close();

		for (var i = 0; i < n; i++) {
			System.out.println(a[i]);
		}
	}
}

Measured memory_bytes: 60068
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        long N = sc.nextLong();

        System.out.println(solve(N));
    }

    private static String solve(long N) {
        long[] num = new long[12+1];
        num[0] = 0;
        for (int i=1; i<12; i++) {
            num[i] = (long)Math.pow(26, i) + num[i-1];
            // System.err.println("i=" + i + " : " + num[i]);
        }



        StringBuilder ans = new StringBuilder();
        for (int i=1; i<=12; i++) {
            if (N <= num[i]) {
                // i文字
                N -= num[i-1] + 1;
                for (int k=0; k<i; k++) {
                    int count = (int)(N%26);
                    ans.append((char)(count + 'a'));
                    N /= 26;
                }

                break;
            }
        }

        return ans.reverse().toString();
    }
}

Measured memory_bytes: 35816
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

bool isP(int n) {
    string s = to_string(n);
    rep(i, s.size()/2) {
        int j = s.size() - i - 1;
        if(s[i] != s[j]) return false;
    }
    return true;
}

int main(){
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    REP(i, a, b+1) {
        if(isP(i)) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int W,H,x,y,r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

    if(y-r < 0 || y+r > H || x-r < 0 || x+r > W) printf("No\n");
    else printf("Yes\n");
}


Measured memory_bytes: 2692
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
main()
{
	cin>>n;
	vector<int>a(n);
	for(int&i:a)cin>>i;
	cin>>m;
	vector<int>b(m);
	for(int&i:b)cin>>i;
	cout<<lexicographical_compare(a.begin(),a.end(),b.begin(),b.end())<<endl;
}


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

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

using namespace std;

const int INF=1<<29;

bool contain(const string &s,const string &t){
	int m=s.length(),n=t.length();
	rep(i,m-n+1) if(s.substr(i,n)==t) return true;
	return false;
}

vector<string> trim_dup(const vector<string> &s){
	int n=s.size();
	vector<string> res;
	rep(i,n){
		bool ok=true;
		rep(j,n) if(i!=j && contain(s[j],s[i])) ok=false;
		if(ok) res.push_back(s[i]);
	}
	return res;
}

int main(){
	for(int n;cin>>n,n;){
		vector<string> s(n);
		rep(i,n) cin>>s[i];

		s=trim_dup(s);
		n=s.size();

		int cost[14][14];
		rep(i,n) rep(j,n) {
			int li=s[i].length(),lj=s[j].length();
			int k;
			for(k=0;k<li;k++){
				if(s[i].substr(k)==s[j].substr(0,min(lj,li-k))) break;
			}
			cost[i][j]=lj-li+k;
		}

		int dp[1<<14][14];
		rep(S,1<<n) rep(i,n) dp[S][i]=INF;
		rep(i,n) dp[1<<i][i]=s[i].length();
		rep(S,1<<n) rep(i,n) {
			rep(j,n) if((S&(1<<j))==0) {
				dp[S|1<<j][j]=min(dp[S|1<<j][j],dp[S][i]+cost[i][j]);
			}
		}
		printf("%d\n",*min_element(dp[(1<<n)-1],dp[(1<<n)-1]+n));
	}

	return 0;
}

Measured memory_bytes: 1836
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL << 60; //intじゃ扱えないことに注意！
using P = pair<int,int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++) //範囲外参照とループの初期化に注意！

int main() {
    ll N,M,K;
    cin >> N >> M >> K;
    vector<ll> A(N),B(M);
    rep(i,N) cin >> A[i];
    rep(i,M) cin >> B[i];

    ll t = 0;
    rep(i,M) t += B[i];      

    int j = M;
    int ans = 0;
    rep(i,N+1){          //尺取り法
        while(j > 0 && t > K){
            j--;
            t -= B[j];     //tがKを超えないようにBを減らす
        }
        if(t > K) break;
        ans = max(ans, i+j);
        if(i == N) break;
        t += A[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6424
N, M = map(int, input().split())
A = list(map(int, input().split()))

from heapq import heappush, heappop, heapify

B = []
for i in range(N):
    B.append(-A[i])
    
heapify(B)

cnt=0
while cnt<M:
    tmp = heappop(B)
    heappush(B, -(-tmp//2))
    cnt+=1
    
print(sum(B)*(-1))

Measured memory_bytes: 14224
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)
#define Graph vector<vecctor<ll>>
#define pairs vector<pair<ll,ll>>
#define pb push_back



using namespace std;
using ll = long long;

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







int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    int a[n];
    rep(i,n){
        cin >> a[i];
    }
    sort(a,a+n);
    int ans =0;
    rep(i,k){
        ans += a[i];
    }

    cout << ans << endl;
    return 0;

    
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end(),greater<pair<int,int>>())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000007 //1000000000000000003
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;



void Main(){

  int N;
  cin >> N;

  int p[N];

  vector<pair<int,int>> ve;

  rep(i,N){
    cin>>p[i];
    ve.emplace_back(p[i],(i+1));
  }

  SORT(ve);

  multiset<int> se;

  ll ans=0;

  se.insert(0);
  se.insert(0);
  se.insert(N+1);
  se.insert(N+1);

  rep(i,N){
    int num=ve[i].second;
    se.insert(num);
    auto itr=se.find(num);
    ll l2,l1,r1,r2;
    ll ln2,ln1,rn1,rn2;

    ln2=*(prev(itr,2));
    ln1=*(prev(itr,1));
    rn2=*(next(itr,2));
    rn1=*(next(itr,1));

    l2=ln1-ln2;
    l1=num-ln1;
    r2=rn2-rn1;
    r1=rn1-num;

    ans+=(r1*l2+r2*l1)*ve[i].first;
  }

  cout<< ans<<"\n";


}


//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

#define N 36

int main(void){
  char A[N], C[N];
  int  B[N], D[N];
  int  n, i, j, tmp, min_i;
  bool flag=true;

  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf(" %c%d ", &A[i], &B[i]);
    C[i]=A[i]; D[i]=B[i];
  }

  for(i=0; i<n-1; i++){
    for(j=n-1; j>i; j--){
      if(B[j-1]>B[j]){
	swap(B[j-1], B[j]);
	swap(A[j-1], A[j]);
      }
    }
  }

  for(i=0; i<n-1; i++){
    min_i=i;
    for(j=i+1; j<n; j++){
      if(D[min_i]>D[j]){
	min_i=j;
      }
    }
    if(i!=min_i){
      swap(C[i], C[min_i]);
      swap(D[i], D[min_i]);
    }
  }

  for(i=0; i<n; i++){
    if(i) printf(" %c%d", A[i], B[i]);
    else  printf("%c%d", A[i], B[i]);
  }
  printf("\nStable\n");

  for(i=0; i<n; i++){
    if(i) printf(" %c%d", C[i], D[i]);
    else  printf("%c%d", C[i], D[i]);
  }

  for(i=0; i<n; i++){
    if(A[i]!=C[i]){
      flag=false;
      break;
    }
  }

  if(flag) printf("\nStable\n");
  else     printf("\nNot stable\n");

  return 0;
}



Measured memory_bytes: 3212
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math


N = int(input())
groups = []
for i in range(N):
    l,r = map(int,input().split())
    groups.append([l,r])

cnt = 0
for i in range(N):
    cnt += groups[i][1]-groups[i][0]+1

print(cnt)


Measured memory_bytes: 13376
/***
**   AUTHOR::ASHUTOSH MOUDGIL
***/


#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F first
#define S second
#define int long long
//#define ll long long
#define all(x) x.begin(),x.end()
#define rsort(x) sort(all(x)); reverse(all(x));
#define endl '\n'
#define vi vector<int>
#define vlli vector<long long>
#define pii pair<int,int>
#define mod 1000000007
#define LMAX 1e18
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define PI 3.141592654
#define deb1(x) cout << #x <<"="<< x <<endl;
#define deb2(x,y) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<endl;
#define deb3(x,y,z) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<<endl;
#define deb4(x,y,z,a) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<< ", "<<#a <<"="<<a << endl;
#define debarr(x) cout << #x<<"::"<<endl;for(int i : x){cout << i <<" ";} cout <<endl;

inline void add(int& a, int b){a = (a+b); if(a>=mod)a-=mod;}
inline void sub(int& a, int b){a = a-b; if(a<0)a+=mod;}
inline void mul(int& a, int b){a = (a*b)%mod;}



void mymain(){
    int n;
    cin >> n;
    while(n > 0){
        if(n%10 == 7){
            cout << "Yes" <<endl;
            return;
        }
        n/=10;
    }
    cout <<"No" <<endl;
}

signed main(){
IOS;
///freopen("input.txt", "r", stdin);
///freopen("output.txt", "w", stdout);
int t=1;
///cin>>t;

for(int tt=0;tt<t;tt++){
   ///cout << "Case #" << tt+1 <<": ";
   mymain();
}
return 0;
}
/*

*/


Measured memory_bytes: 3648
l=int(input())
n=20
ans=[]
for i in range(19):
  ans.append((i+1,i+2,0))
for i in range(l.bit_length()-1):
  ans.append((i+1,i+2,1<<i))
  m=l-(1<<(i+1))
x=1<<(i+1)
for i in range(m.bit_length()):
  if m&(1<<i):
    ans.append((i+1,n,x))
    x+=(1<<i)
print(n,len(ans))
for i in ans:print(*i)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;

int c;
int grid[4][4];
int a[4],b[4];
bool flag=true;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    a[1]=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin>>c;
            grid[i][j]=c;
        }
    }
    a[1]=0;
    for(int i=1;i<=3;i++){
        b[i] = grid[1][i];
    }
    a[2] = grid[2][1] - b[1];
    a[3] = grid[3][1] - b[1];
    
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(a[i]+b[j] != grid[i][j]){
                flag=false;
                break;
            }
        }
    }
    if(flag)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
	int w, a, b;


	cin >> w >> a >> b;

	int res = 0;

	if (a < b){
		if (a + w < b){
			res = b - a - w;
		}
		else
			res = 0;
	}
	else {
		if (b + w < a)
			res = a - b - w;
	}

	cout << res << endl;
}

Measured memory_bytes: 256
D=int(input())
*c,=map(int,input().split())
s=[]
for i in range(D):
    *x,=map(int,input().split())
    s.append(x)

dt=[]
last=[-1]*26
v=0
for d in range(D):
    news=[s[d][i]+c[i]*(d-last[i])*(d-last[i]-1) for i in range(26)]
    maxi=0
    tmp=-float('inf')
    for i in range(26):
        if tmp<news[i]:
            maxi=i
            tmp=news[i]
    last[maxi]=d
    v+=s[d][maxi]
    for i in range(26):
        v-=c[i]*(d-last[i])
    dt.append(maxi+1)

def score(T):
    last=[-1]*26
    v=0
    for d in range(D):
        v+=s[d][T[d]-1]
        last[T[d]-1]=d
        for i in range(26):
            v-=c[i]*(d-last[i])
    return v

v0=max(score(dt)+10**6,0)

for _ in range(6):
    for d in range(1,D):
        y=-1
        newdt=dt+[]
        for i in range(26):
            if dt[d]!=i+1:
                newdt[d]=i+1
                v1=max(score(newdt)+10**6,0)
                if v0<v1:
                    y=i+1
                    v0=v1
        if y!=-1:
            dt[d]=y

for i in dt:
    print(i)

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

if __name__ == "__main__":
    N = int(input())
    pre_w = input()
    words = [pre_w]
    for i in range(N-1):
        w = input()
        if w in words:
            print("No")
            exit()
        words.append(w)

        if pre_w[-1] == w[0]:
            pre_w = w
            continue
        else:
            print("No")
            exit()
    print("Yes")


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

// #define DEBUG

void printarray(int n, int a[])
{
    for (int i = 1; i < n + 1; i++)
    {
        cout << a[i];
        if (i != n)
            cout << " ";
    }
    cout << endl;
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, w, vi, wi;
    cin >> n >> w;
    int dp_list[n + 1][w + 1] = {};

    for (int i = 0; i < n; i++)
    {
        cin >> vi >> wi;
        for (int j = 0; j < w + 1; j++)
        {

            if (j + wi <= w)
            {
                dp_list[i + 1][j + wi] = max(dp_list[i][j + wi], dp_list[i][j] + vi);
            }
            dp_list[i + 1][j] = max(dp_list[i + 1][j], dp_list[i][j]);
        }
    }

    cout << dp_list[n][w] << endl;
    return 0;
}


Measured memory_bytes: 7068