akhauriyash/Code-Regression huggingface dataset:
N = int(input())
count = [[0 for _ in range(9)] for _ in range(9)]
for i in range(1, N + 1):
    if str(i)[0] != "0" and str(i)[-1] != "0":
        count[int(str(i)[0]) - 1][int(str(i)[-1]) - 1] += 1
ans = 0
for i in range(0, 9):
    for k in range(0, 9):
        ans += count[i][k] * count[k][i]
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

int main() {
	int a, b;
	cin >> a >> b;

	if (a + b == 16) {
		if (a == b) {
			cout << "Yay!" << endl;
			return 0;
		}
		else {
			cout << ":(" << endl;
			return 0;
		}
	}
	else {
		if ((a < 8 && b <= 8) || (a <= 8 && b < 8)) {
			cout << "Yay!" << endl;
			return 0;
		}
		else {
			cout << ":(" << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 256
// chal ab jayda mat udd, agle me niche jaega...

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

#define rep(i,st,en) for(__typeof(en) i=(st)-(st>en); i!=(en)-(st>en); i+=1-2*(st>en))
#define ff first
#define ss second
#define endl '\n'
#define all(v) v.begin(), v.end()
#define COVID_19 ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(NULL);
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{cout << *it << " = " << a << endl;    err(++it, args...);}
typedef long long ll;
const ll mod = 1e9+7;

int main() {
    COVID_19
    int k, n;   cin>>k>>n;
    int arr[n];
    rep(i,0,n)  cin>>arr[i];
    sort(arr, arr+n);
    vector<int> dif;
    rep(i,1,n)
        dif.push_back(arr[i]-arr[i-1]);
    dif.push_back(k-arr[n-1]+arr[0]);
    sort(all(dif));
    int ans = accumulate(all(dif), 0) - dif[n-1];
    cout<<ans<<endl;
    return 0;
}

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define INF 999999999
#define MOD 1000000007

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

ll k, a, b, ans, yen;

int main(){
	cin >> k >> a >> b;
	ans = 1;
	ll i=1;
	for(;i<=k-1;i++){
		if(ans+2<ans-a+b&&ans>=a){ 
			ans += b-a;
			i++;
		}else{
			ans++;
		}
	}
	if(i==k) ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	const inputLines = input.split("\n");
	const line1 = inputLines[1];
	const line1vars = line1.split(" ");
	var ls = line1vars.map(a => parseInt(a, 10));
	ls = ls.sort(
		function(a,b){
			return (a < b ? -1 : 1);
		}
	);
	var result = 0;
	for (var i = 0; i < ls.length; i++) {
		for (var j = i + 1; j < ls.length; j++) {
			for (var k = j + 1; k < ls.length; k++) {
				// console.log({
				// 	i: i,
				// 	j: j,
				// 	k: k
				// });
				if (ls[i] == ls[j] || ls[j] == ls[k] || ls[i] == ls[k]) {
					continue;
				}
				if (ls[k] < ls[i] + ls[j]) {
					// console.log("hit");
					result += 1;
				}
			}
		}
	}
	console.log(result);



	// tmp = input[1].split(" ");
	// //文字列から10進数に変換するときはparseIntを使います
	// var a = parseInt(input[0], 10);
	// var b = parseInt(tmp[0], 10);
	// var c = parseInt(tmp[1], 10);
	// var s = input[2];

	//出力
	// console.log('%d %s',a+b+c,s);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

// node index.js
// 1
// 2 3
// test
// (Ctrl + D)


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

using namespace std;
int n;
string x;
pair<string, int> music[51];


int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> music[i].first >> music[i].second;
    }
    cin >> x;
    int sum=0, flag=0;
    for(int i=0; i< n; i++){
        if(music[i].first.compare(x) == 0 && flag==0){
            flag=1;
            continue;
        }
        if(flag==1){
            sum += music[i].second;
        }
    }

    cout << sum;
    return 0;
}

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

using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,k,h) for(int i = k; i < h; ++i)
#define rep3(i,k,h) for(int i = k; i <= h; ++i)
#define INF LLong_MAX // long long INF
#define inf INT_MAX // int inf

typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;

int main() {
    string s;
    cin >> s;
    int a = s[0] - 48, b = s[1]-48, c = s[2]-48, d = s[3]-48;
    if(a+b+c+d == 7) {
        printf("%d+%d+%d+%d=7\n",a,b,c,d);
    }
    else if(a-b+c+d == 7){
        printf("%d-%d+%d+%d=7\n",a,b,c,d);
    }
    else if(a+b-c+d == 7) {
        printf("%d+%d-%d+%d=7\n",a,b,c,d);
    }
    else if(a+b+c-d == 7) {
        printf("%d+%d+%d-%d=7\n",a,b,c,d);
    }
    else if(a-b-c+d == 7) {
        printf("%d-%d-%d+%d=7\n",a,b,c,d);
    }
    else if(a+b-c-d == 7) {
        printf("%d+%d-%d-%d=7\n",a,b,c,d);
    }
    else if(a-b+c-d == 7) {
        printf("%d-%d+%d-%d=7\n",a,b,c,d);
    }
    else if(a-b-c-d == 7) {
        printf("%d-%d-%d-%d=7\n",a,b,c,d);
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int MOD = 365;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        // k: コンテストの種類数
        int k = 26;
        
        // n: 1日目～n日目にコンテストが開催される
        int n = sc.nextInt();
        
        // c[i]: タイプiのコンテストのマイナス係数
        int[] c = new int[k];
        for (int i = 0; i < k; i++) {
            c[i] = sc.nextInt();
        }
        
        // s[d][i]: タイプiをd日目に開催したときに増加する満足度
        int[][] s = new int[n+1][k];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        
        // t[i]: i日目に開かれるコンテストのタイプ
        int[] t = new int[n+1];
        for (int i = 1; i <= n; i++) {
            t[i] = sc.nextInt() - 1;
        }
        
        // last[i]: タイプiのコンテストが最近何日目に開かれたか
        int[] last = new int[k];
        
        // 満足度計算
        int score = 0;
        for (int i = 1; i <= n; i++) {
            int contest = t[i];
            
            // UP
            score += s[i][contest];
            last[contest] = i;
            
            // DOWN
            for (int j = 0; j < k; j++) {
                score -= c[j] * (i-last[j]);
            }
            
            System.out.println(score);
        }
    }
    
    static public class Test {
        Test() {
            // System.out.println(MOD);
        }
        
    }
}

Measured memory_bytes: 46496
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;

    char ar[10][10],ar2[10][10];
    int n,m,k,ans;
    map<int,vector<int>> mp,mp2;

    int ar3[10],ar4[10];

    void func2(int c)
    {
        if(c>m)
        {
            int i,j,b=0;
            for(i=1;i<=n;++i)
                for(j=1;j<=m;++j)
                    ar2[i][j]=ar[i][j];
            for(i=1;i<=n;++i)
            {
                if(ar3[i]==1)
                {
                    for(j=1;j<=m;++j)
                        ar2[i][j]='.';
                }
            }
            for(j=1;j<=m;++j)
            {
                if(ar4[j]==1)
                {
                    for(i=1;i<=n;++i)
                        ar2[i][j]='.';
                }
            }
            for(i=1;i<=n;++i)
                for(j=1;j<=m;++j)
                    if(ar2[i][j]=='#')
                        ++b;
            if(b==k)
            {
                ++ans;
            }
            return;
        }
        func2(c+1);
        ar4[c]=1;
        func2(c+1);
        ar4[c]=0;
    }

    void func(int i)
    {
        if(i>n)
        {
            func2(1);
            return;
        }
        func(i+1);
        ar3[i]=1;
        func(i+1);
        ar3[i]=0;
    }

    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int i,j,b=0;
            cin>>n>>m>>k;
            for(i=1;i<=n;++i)
            {
                for(j=1;j<=m;++j)
                {
                    cin>>ar[i][j];
                    if(ar[i][j]=='#')
                        ++b;
                }
            }
            func(1);
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 3620
n,k = map(int, input().split())
nums = []
for _ in range(n):
    a, b = map(int, input().split())
    nums.append((a,b))
nums.sort(key=lambda x: x[0])
for t in nums:
    k -= t[1]
    if k <= 0:
        print(t[0])
        break


Measured memory_bytes: 18192
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int X = sc.nextInt();
		int Y = sc.nextInt();

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();

		long[] p = nextLongArray(sc, A);
		long[] q = nextLongArray(sc, B);
		long[] r = nextLongArray(sc, C);

		sc.close();

		Arrays.sort(p);
		Arrays.sort(q);
//		Arrays.sort(r);

		List<Long> ans = new ArrayList<>();
		for (int i = 0; i < X; i++) {
			ans.add(p[A - i - 1]);
		}
		for (int i = 0; i < Y; i++) {
			ans.add(q[B - i - 1]);
		}

		for (int i = 0; i < C; i++) {
			ans.add(r[i]);
		}

		ans.sort(Comparator.reverseOrder());

		long z = 0;
		for (int i = 0; i < X + Y; i++) {
			z += ans.get(i);
		}

		out.println(z);

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

	@SuppressWarnings("unused")
	private long[] nextLongArray(Scanner sc, int n) {
		long[] result = new long[n];
		for (int i = 0; i < n; i++) {
			result[i] = sc.nextLong();
		}
		return result;
	}
}


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

int main()
{
	int N;
	while (cin >> N, N) {
		vector<vector<int>> eq(N, vector<int>(N + 1, 0));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= N; j++) {
				cin >> eq[i][j];
			}
		}
		vector<int> dp(1 << N, 100000000);
		dp[0] = 0;
		for (int i = 1; i < (1 << N); i++) {
			for (int j = 0; j < N; j++) {
				if (i&(1 << j)) {
					dp[i] = min(dp[i - (1 << j)] + eq[j][0], dp[i]);
					for (int k = 0; k < N; k++) {
						if ((i - (1 << j)) & (1 << k)) {
							dp[i] = min(dp[i - (1 << j)] + eq[j][k+1], dp[i]);
						}
					}
				}
			}
		}
		cout << dp[(1 << N)-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 3376
s = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(s[int(input())-1])

Measured memory_bytes: 3060
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

const ll inf = (ll)(1e17 + 17);
const ll mod = (ll)(1e9 + 7);
ll n, k;
vll a;
bool can(ll t) {
	ll total = 0;
	for(ll i = 0; i < n; i++) {
		if(a[i] <= t) continue;
		total += (a[i] + t - 1)/t;
		total--;
	}
	return total <= k;
}

int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  cin >> n >> k;
  ll low = 1, high = inf;
  a.resize(n, 0);
  for(ll i = 0; i < n; i++) cin >> a[i];
  ll ans = -1, mid;
  while(low <= high) {
  	mid = (low + high)/2;
  	if(can(mid)) {
  		ans = mid;
  		high = mid - 1;
  	} else {
  		low = mid + 1;
  	}
  }
  cout << ans << endl;
  return 0;
} //good night.

Measured memory_bytes: 4776
<?php

$a = trim(fgets(STDIN));
$b = strlen($a);
$input = str_split($a);
$result = "No";

if ((($input[0] == $input[1] && $input[2] == $input[3]) and ($input[2] != $input[1])) or
    ($input[0] == $input[2] && $input[1] == $input[3]) and ($input[0] != $input[1]) or
    ($input[0] == $input[3] && $input[2] == $input[1]) and ($input[0] != $input[1])) {
    $result = "Yes";
} else if ($input[0] == $input[1] && $input[0] == $input[2]) {
    $result = "No";
} else if ($input[0] == $input[1] && $input[0] == $input[3]) {
    $result = "No";
}
echo $result;
?>

Measured memory_bytes: 5368
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

int main(){
int sx,sy,tx,ty;
cin>>sx>>sy>>tx>>ty;
int yoko=tx-sx;
int tate=ty-sy;

for(int i=0;i<yoko;i++){
cout<<"R";
}
for(int i=0;i<tate;i++){
    cout<<"U";
}
for(int i=0;i<yoko;i++){
    cout<<"L";
}
for(int i=0;i<tate+1;i++){
    cout<<"D";
}


for(int i=0;i<yoko+1;i++){
cout<<"R";
}
for(int i=0;i<tate+1;i++){
cout<<"U";
}
cout<<"LU";

for(int i=0;i<yoko+1;i++){
 cout<<"L";
}
for(int i=0;i<tate+1;i++){
cout<<"D";
}
cout<<"R";
}








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

int main()
{
    int a, b, c;
    bool falg = false;
    cin >> a >> b >>c;

    if(a < c){
        if(c < b){
            cout << "Yes";

            return 0;
        }
    }

    if(c < a){
        if(b < c){
            cout << "Yes";

            return 0;
        }
    }


    cout << "No";



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>

#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define ATCODER 1000000007
using namespace std;
 
////////////////////////

int main(){
  int n,a,b,c,d,p,q,res=10000;
  cin >> n >> a >> b >> c >> d;
  a--;b--;c--;d--;
  for(int w=1;w<=n;w++){
    p = abs(a/w-b/w) + abs(a%w-b%w);
    q = abs(c/w-d/w) + abs(c%w-d%w);
    //cout << p <<" " << q << endl;;
    res = min(res,p+q);
  }
  cout << res << endl;
}

Measured memory_bytes: 3104
#include <iostream>

using namespace std;

int main() {
    long long x;
    long long money = 100;
    cin >> x;
    

    for (int i = 1; i < 5000; ++i){
        money *= 1.01;
        if (money >= x) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3588
#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
    int n, k;
    cin >> n >> k;
    int h[n];
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    long long dp[n];
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; i++) {
        dp[i] = 2e18;
        for (int j = 1; j <= k; j++) {
            if (i - j < 0) break;
            else {
                dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
    }
}
}
cout << dp[n-1];
}

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

using namespace std;
int main() {
  string a, b;
  cin >> a >> b;
  bool isAHonest = (a == "H");
  bool isTHonest = false;

  if (isAHonest && b == "H" || isAHonest == false && b == "D") {
    isTHonest = true;
  }

  cout << (isTHonest ? "H" : "D") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
  
using namespace std;
  
#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
  
template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }
  
typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int matrix[25 * 25][25 * 25];
int vect[25 * 25];
bool gaussian(int W, int H){
  int N = W * H;
  int target = 0;
  REP(x, N){
    int pivot = target;
    FOR(y, target + 1, N) if(matrix[y][x] == 1) pivot = y;
    if(matrix[pivot][x] == 0) continue;
    REP(i, N) swap(matrix[pivot][i], matrix[target][i]);
    swap(vect[pivot], vect[target]);
    FOR(y, target + 1, N) if(matrix[y][x] == 1){
      FOR(i, x, N) matrix[y][i] ^= matrix[target][i];
      vect[y] ^= vect[target];
    }
    target ++;
  }
  FOR(y, target, N) if(vect[y] == 1) return false;
  return true;
}
  
int main(){
  int W, H, D;
  while (cin>>W>>H>>D && W) {
    memset(matrix, 0, sizeof(matrix));
    memset(vect, 0, sizeof(vect));
    REP(y, H)REP(x, W) cin>>vect[y * W + x];
    REP(y1, H)REP(x1, W){
      REP(y2, H)REP(x2, W){
        if(abs(y1 - y2) + abs(x1 - x2) == D || (x1 == x2 && y1 == y2)){
          matrix[y1 * W + x1][y2 * W + x2] = 1;
        }
      }
    }
    int N = W * H;
    bool ans = gaussian(W, H);
    if(ans) cout<<1<<endl;
    else cout<<0<<endl;
  }
  return 0;
}

Measured memory_bytes: 2696
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;


int main(void) {
	int n, i;
	string s;

	cin >> s;

	n = s.size();

	for (i = 0; i < n; i++) {
		if (s[i] != s[n - i - 1]) {
			cout << "No" << endl;
			return 0;
		}
	}

	for (i = 0; i < (n - 1) / 2; i++) {
		if (s[i] != s[(n - 1) / 2 - i - 1]) {
			cout << "No" << endl;
			return 0;
		}
	}

	for (i = (n + 1) / 2; i < n; i++) {
		if (s[i] != s[(n + 1) / 2 + n - 1 - i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}

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

int main()
{
	int n;
  	cin>>n;
  	string a,b;
  	cin>>a>>b;
  	int i=0,j=0;
  	string res="";
  	while(i<n && j<n)
    {
      res+=a[i];
      res+=b[j];
      i++;
      j++;
    }
  	cout<<res;
  	return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
a = [0]*(m+2)
a[m]=n+10
a[m+1]=n+10
for i in range(m):
  a[i]= int(input())
answer=[0]*(n+1)
answer[0]=1
if(n==1):
  if(a[0]==1):
    print(0)
  else:
    print(1)
else:
  answer[0] = 1
  if(a[0]==1):
    answer[1] = 0
    a.pop(0)
  else:
    answer[1] = 1
  for i in range(2,n+1):
    if(a[0]==i or a[1]==i):
      answer[i]=0
    elif(a[0]==i-1):
      answer[i]=answer[i-2]
      a.pop(0)
    else:
      answer[i]=answer[i-1]+answer[i-2]
    answer[i] = answer[i]%1000000007
  print(answer[n])

Measured memory_bytes: 13408
#include <cstdio>
#include <map>
using namespace std;
typedef long long int lli;
typedef map<int, int> M;

int main() {
  lli sum[4000];
  int gid[4000];
  int n, i, j, p, q, lid;
  M m;
  bool b;

  while (1) {
    scanf("%d", &n);
    if (!n) break;
    m.clear();
    for (j=0; j<n; j++) sum[j] = 0;
    for (j=0; j<n; j++) {
      scanf("%d %d %d", &i, &p, &q);
      lid = j;
      pair<M::iterator, bool> res = m.insert(M::value_type(i, lid));
      if (!res.second) {
        M::iterator it = m.find(i);
        lid = it->second;
      }
      gid[lid] = i;
      sum[lid] += (lli)p*q;
    }
    b = false;
    for (j=0; j<(int)m.size(); j++) {
      if (sum[j] >= 1000000) {
        printf("%d\n", gid[j]);
        b = true;
      }
    }
    if (!b) {
      printf("NA\n");
    }
  }

  return 0;
}

Measured memory_bytes: 1108
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>

using namespace std;

int main(){
  int n;
  cin >> n;
  long long ans = 0;
  long long a[100001];
  long long b[100000];
  for(int i = 0; i < n+1; i++){
    cin >> a[i];
  }
  for(int i = 0; i < n; i++){
    cin >> b[i];
  }
  for(int i = 0; i < n ; i++){
    if(a[i] >= b[i]){
      ans += b[i];
    }
    else if(a[i] + a[i+1] >= b[i]){
      ans += b[i];
      a[i+1] = a[i] + a[i+1] - b[i];
    }
    else{
      ans += a[i] + a[i+1];
      a[i+1] = 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

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

            char[] nc = new char[s.Length];
            for (int i = 0; i < s.Length; i++)
            {
                nc[i] = (char)((((s[i] - 'A') + N) % 26) + 'A');
            }

            Console.WriteLine(nc);
        }
    }
}



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

using namespace std;

int main()
{
    int w, l = 0, r = 0;
    cin >> w;
    for (int i = 0; ; i++) {        
        r += pow(3, i);
        if (l <= w && w <= r) {
            w -= pow(3, i);
            r -= pow(3, i);
            cout << '+';
            for (int j = i - 1; j >= 0; j--) {
                if (r - pow(3, j) < abs(w)) {
                    if (w > 0) {
                        w -= pow(3, j);
                        cout << '+';
                    } else {
                        w += pow(3, j);
                        cout << '-';
                    }
                } else {
                    cout << 0;
                }
                r -= pow(3, j);
            }
            cout << endl;
            break;
        }
        l = r + 1;
    }    
    return 0;
}

Measured memory_bytes: 1200
#include <iostream>

using namespace std;

int main(){

int a[5];
int sum=0,rest=0;
  
  for(int i=0;i<5;i++){
  cin >> a[i];
    int ceil=(a[i]+9)/10*10;
  sum+=ceil;
  rest=max(rest,ceil-a[i]);
  }
  cout << sum-rest <<endl;
}


Measured memory_bytes: 256
class Dest(object):
    def __init__(self, name):
        self.name = name
        self.count = 0

    def vote(self):
        self.count += 1




if __name__ == '__main__':
    while True:
        # ??????????????\???
        num_of_students, num_of_destinations = [int(x) for x in input().strip().split(' ')]
        if num_of_students == 0 and num_of_destinations == 0:
            break

        data = []
        for i in range(num_of_students):
            data.append(list(map(int, input().strip().split(' '))))

        # ??????????????????
        dests = []
        for i in range(num_of_destinations):
            dest_name = str(i+1)
            dests.append(Dest(dest_name))

        for d in data:
            for i, v in enumerate(d):
                if v:
                    dests[i].vote()

        dests.sort(key=lambda x:x.count, reverse=True)

        # ???????????????
        t = [d.name for d in dests]
        print('{0}'.format(' '.join(t)))

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

using namespace std;

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

  int n;
  cin >> n;

  int cmd, val;
  int lhd, rhd;

  multiset<int> s;
  multiset<int>::iterator it;
  for (int i = 0; i < n; i++) {
    cin >> cmd;
    switch (cmd) {
      case 0:
        cin >> val;
        s.insert(val);
        cout << s.size() << endl;
        break;

      case 1:
        cin >> val;
        cout << s.count(val) << endl;
        break;

      case 2:
        cin >> val;
        s.erase(val);
        break;

      case 3:
        cin >> lhd >> rhd;

        for (auto itr = s.lower_bound(lhd); itr != s.end() && *itr <= rhd;
             itr++) {
          cout << *itr << endl;
        }
        break;
    }
  }
}




Measured memory_bytes: 12492
local mmi, mma = math.min, math.max
local n = io.read("*n")
local edge = {}
local ccnt = {}
local nodetask = {}
local len = {}
for i = 1, n do
  ccnt[i] = 0
  edge[i] = {}
  nodetask[i] = {}
  len[i] = 0
end
for i = 2, n do
  local a = io.read("*n")
  table.insert(edge[i], a)
  ccnt[a] = ccnt[a] + 1
end
local tasks = {}
for i = 2, n do
  if ccnt[i] == 0 then
    table.insert(tasks, i)
  end
end
for i = 1, n do
  local src = tasks[i]
  if 0 < #nodetask[src] then
    table.sort(nodetask[src])
    local nts = nodetask[src]
    local v = nts[1] + 1
    for j = 2, #nts do
      v = 1 + mma(v, nts[j])
    end
    len[src] = v
  end
  local lensrc = len[src]
  for j = 1, #edge[src] do
    local dst = edge[src][j]
    local ccntdst= ccnt[dst]
    if 1 <= ccntdst then
      table.insert(nodetask[dst], lensrc)
      ccnt[dst] = ccntdst - 1
      if ccntdst == 1 then
        table.insert(tasks, dst)
      end
    end
  end
end
print(len[1])


Measured memory_bytes: 29376
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int n, k;
  cin >> n;
  cin >> k;
  vector<int64_t> H(n);
  for(int i=0; i<n; i++) {
    cin >> H[i];
} 
  if(k>=n) cout << 0 << endl;
  else {
    sort(H.begin(), H.end());
    int64_t ans = 0LL;
    for(int i=0; i<n-k; i++) ans += H[i];
    cout << ans << endl;
  }
  

} 

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long double LD; 
typedef long long ll; 
#define int ll 
#define ff(i,a,b) for (int i = a; i < b; i++) 
#define bf(i,a,b) for (int i = a; i >= b; i--) 
#define all(v) v.begin(),v.end() 
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define F first 
#define S second
#define pb push_back
#define mp make_pair
#define lb lower_bound   
#define ub upper_bound
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define one cout<<"-1"<<endl
#define pi 3.141592653589793238
#define intmx INT_MAX 
#define intmi INT_MIN
#define MOD 1000000007
int mod(int x){
    return ((x%MOD + MOD)%MOD);
}
int add(int a,int b){
    return mod(mod(a)+mod(b));
}
int mul(int a,int b){
    return mod(mod(a)*mod(b));
}
int power(int n,int m){
    int ans=1;
    if(m==0)
    return 1;
    while(m>0){
        if(m%2!=0){
            ans=(ans*n)%MOD;
        }
        n=(n*n)%MOD;
        m=m/2;
    }
    return (ans+MOD)%MOD;
}

void solve(){
   int n;
   cin>>n;
   if(n<2)
   cout<<"0";
   else
   cout<<(power(10,n)%MOD-2*power(9,n)%MOD+power(8,n)%MOD+MOD)%MOD<<endl;
}
signed main() {
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define INF 10**9

int main() {
    vector<int> E;
    E.push_back(1);
    int x;
    cin >> x;
    for (int i=2;i<33;i++){
        for (int j=2;j<10;j++){
            if (pow(i,j)<=x){
                E.push_back(pow(i,j));
            }
            else {
                break;
            }
        }
    }
    int l = E.size();
    sort(all(E));
    cout << E.at(l-1) << endl;
}

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

int main() {
    while (true) {
        int n, m;
        cin >> n >> m;
        
        if (n==0 && m==0) {
            break;
        }
        
        int p[n];
        int s = 0;
        
        for (int i=0; i<n; i++) {
            cin >> p[i];
            s += p[i];
        }
        
        sort(p, p+n, greater<int>());
        
        for (int i=1; i*m-1<n; i++) {
            s -= p[i*m-1];
        }
        
        cout << s << endl;
    }
}


Measured memory_bytes: 3088
from fractions import gcd
from functools import reduce
N, X = map(int, input().split())
x_list = list(map(int, input().split()))
x_list.append(X)
x_list.sort()
diff_list = [x_list[i + 1] - x_list[i] for i in range(len(x_list) - 1)]
print(reduce(gcd, diff_list))


Measured memory_bytes: 16280
h, w, k = [int(i) for i in input().split()]
table = [list(input()) for i in range(h)]

kotae = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        count = 0
        for a in range(h):
            for b in range(w):
                if(table[a][b] == "#" and (i >> a & 1 == 1) and (j >> b & 1 == 1)):
                    count += 1

        if(count == k):
            kotae += 1


print(kotae)

Measured memory_bytes: 68384
a,b = map(int,input().split())
n = input()
co = 0
if len(n) == a+b+1:
  for i in range(a+b+1):
    if n[i] == "-":
      if i != a:
        print("No")
        exit()
      else:
        co = 1
  if co == 1:
    print("Yes")
  else:
    print("No")
    
else:
  print("No")
  exit()


Measured memory_bytes: 3060
from itertools import accumulate
N = int(input())
S = input()
accNumBlack = [0] + list(accumulate([int(c == '#') for c in S]))

ans = float('inf')
for i in range(N+1):
  tmp = 0
  # i - 1 個目までを白にする
  tmp += accNumBlack[i] - accNumBlack[0]
  # i 個目からを黒にする
  tmp += (N - i) - (accNumBlack[N] - accNumBlack[i])
  ans = ans if ans < tmp else tmp
print(ans)

Measured memory_bytes: 13032
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double lod;
const int N=4e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
struct P{ int x,y; inline bool operator < (const P &b) const { return y<b.y; } }p[N];
int x[N],c[N];
int mn[N];
int main()
{
	int x1=gi(),y1=gi(),x2=gi(),y2=gi(),i;
	int n=gi(),t,k,sum=0,s;
	const lod pi=3.14159265358979323846;
	for (i=1;i<=n;i++)
		p[i].x=gi(),p[i].y=gi();
	if (x1>x2) { x1*=-1; x2*=-1; for (i=1;i<=n;i++) p[i].x*=-1; }
	if (y1>y2) { y1*=-1; y2*=-1; for (i=1;i<=n;i++) p[i].y*=-1; }
	for (i=1;i<=n;i++)
		if (p[i].x<x1||x2<p[i].x||p[i].y<y1||y2<p[i].y) p[i--]=p[n--];

	for (i=1;i<=n;i++) x[i]=p[i].x;
	sort(x+1,x+1+n);
	sort(p+1,p+1+n);
	for (i=1;i<=n;i++) {
		k=lower_bound(x+1,x+1+n,p[i].x)-x;
		s=0;
		for (t=k;t;t^=t&-t) s=max(s,c[t]);
		sum=max(sum,++s);
		for (t=k;t<=n;t+=t&-t) c[t]=max(c[t],s);
	}
	double ans=100LL*(x2-x1+y2-y1);
	ans=ans-20*sum+5*pi*sum;
 	if (sum==abs(x1-x2)+1||sum==abs(y1-y2)+1)
		ans=ans+5*pi;
	printf("%.15lf\n",ans);
	//cout<<100LL*(x2-x1+y2-y1)+(sum==min(y2-y1,x2-x1)+1?-(sum-1)*(20*5-pi)+10*pi-20:-sum*(20-5*pi));//);
	return 0;
}


Measured memory_bytes: 4992
def main():
    n, m = map(int, input().split())
    nums = []
    for i in range(n):
        a, b = map(int, input().split())
        nums.append((a, b))
    nums.sort()
    total = 0
    for i in range(n):
        if m <= 0:
            break
        a, b = nums[i]
        total += a * min(b, m)
        m -= min(b, m)
    print(total)


if __name__ == '__main__':
    main()


Measured memory_bytes: 16896
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> to(N+1);
    for (int i = 0; i < M; i++) {
        int _a, _b;
        cin >> _a >> _b;
        to[_a].push_back(_b);
        to[_b].push_back(_a);
    }

    queue<int> q;
    vector<int> last_one(N+1, -1);
    last_one[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int pos_now = q.front(); q.pop();
        for (auto child : to[pos_now]) {
            if (last_one[child] < 0) {
                last_one[child] = pos_now;
                q.push(child);
            }
        }
    }

    cout << "Yes" << endl;
    for (int i = 2; i <= N; i++) {
        cout << last_one[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 9692
a = [list(map(int, input().split())) for _ in range(3)]
n = int(input())

def judge(a):
    if a[0][0] == 0 and a[0][1] == 0 and a[0][2] == 0:
        return True
    elif a[1][0] == 0 and a[1][1] == 0 and a[1][2] == 0:
        return True
    elif a[2][0] == 0 and a[2][1] == 0 and a[2][2] == 0:
        return True
    elif a[0][0] == 0 and a[1][0] == 0 and a[2][0] == 0:
        return True
    elif a[0][1] == 0 and a[1][1] == 0 and a[2][1] == 0:
        return True
    elif a[0][2] == 0 and a[1][2] == 0 and a[2][2] == 0:
        return True
    elif a[0][0] == 0 and a[1][1] == 0 and a[2][2] == 0:
        return True
    elif a[0][2] == 0 and a[1][1] == 0 and a[2][0] == 0:
        return True
    return False
    

for i in range(n):
    num = int(input())
    for x in range(3):
        for y in range(3):
            if a[x][y] == num:
                a[x][y] = 0

if judge(a):
    print('Yes')
else:
    print('No')

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

int  main()
{
	string s; cin >> s;
	string t; cin >> t;
	int len = s.size();
	rep(i, len)
	{
		if (s == t)
			break;
		string tmp; tmp += s.back();
		s.insert(0, tmp);
		s.erase(len);
		// cout << s << endl;
	}
	if (s == t)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
using System;
public class Program {
  public static void Main() {
    var input = "";
    while(!string.IsNullOrEmpty((input = Console.ReadLine()))) {  
      var values = input.Split(' ');
      int a = int.Parse(values[0]);
      int b = int.Parse(values[1]);
      Console.WriteLine((a + b).ToString().Length);
    }
  }
}

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

int main() {

	int A, B;
	cin >> A >> B;

	int count=0;

	for (int i = A; i <= B; i++) {
		vector<int>num;
		vector<int>num2;
		int n = i;
		while (n) {
			num.push_back(n % 10);
			num2.push_back(n % 10);
			n = n / 10;
		}

		reverse(num.begin(), num.end());

		int same = true;

		for (unsigned int i = 0; i < num.size(); i++) {
			if (num[i] != num2[i]) {
				same = false;
			}
		}

		if (same == true) {
			count++;
		}
	}

	cout << count << endl;
	

	return 0;

}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
s = [input() for _ in range(h)]

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '#':
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

print(ans)


Measured memory_bytes: 156300
import collections
n,rev,q = int(raw_input()) ,False,collections.deque()

class Node(object):
	def __init__(self, val):
		self.val = val
		self.next = None
		self.prev = None

head = None
tail = None
for ai in map(int, raw_input().split()):
	if head is None:
		node = Node(ai)
		head = node
		tail = node
	else:
		node = Node(ai)
		if rev:
			head.prev = node
			node.next= head
			head = node
		else:
			tail.next = node
			node.prev=  tail
			tail = node
		rev ^=  True

cur = head 
temp = []
while(cur):
	temp.append(cur.val)
	cur = cur.next 
print ' '.join(map(str, temp[::-1 if rev else 1]))

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

using namespace std;

typedef long long ll;

int firstDigit(int n) { 
    while (n >= 10) {
        n /= 10; 
    }
    return n; 
} 

/*
    A(n), B(m) <= N
    return  no of pairs such that a[1] = b[m] = i, a[n] = b[1] = j
*/
ll solve(ll n) {
    ll total = 0;
    ll cnt[11][11];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n; ++i) {
        cnt[firstDigit(i)][i % 10]++;
    }
    for(int i = 1; i <= 9; ++i) {
        for(int j = 1; j <= 9; ++j) {
            total += cnt[i][j] * cnt[j][i];       
        }
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n;
    cin >> n;
    cout << solve(n) << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

    int dp[N];
    dp[0] = 0;
    dp[1] = abs(arr[1]-arr[0]);
    for(int i = 2; i < N; ++i){
        int step1 = dp[i-1] + abs(arr[i]-arr[i-1]);
        int step2 = dp[i-2] + abs(arr[i]-arr[i-2]);
        if (step1<=step2){
            dp[i] = step1;
        }
        else{
            dp[i] = step2;
        }
    }
    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
	long long int a,b,x;

	scanf("%lld %lld %lld",&a,&b,&x);

	if(a == 0){
		printf("%lld\n",(b/x)+1);
	}
	else{
		printf("%lld\n",(b/x) - ((a-1)/x));
	}

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF 1000000000000001
#define ll long long
using namespace std;

int main()
{
  ll N;
  cin >> N;
  ll min = INF;
  ll ans = 0;
  for (ll i = 0; i < N; ++i)
  {
    ll p;
    cin >> p;

    if (p < min)
    {
      ans += 1;
      min = p;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

int N, M;
int X, Y;
vector<int> Xs;
vector<int> Ys, tot;
int ans;
int val;

int main() {
	scanf("%d %d %d %d", &N, &M, &X, &Y);

	for(int i = 0; i < N; i++) {
		cin >> val;
		Xs.push_back(val);
		tot.push_back(val);
	}
	for(int i = 0; i < M; i++) {
		cin >> val;
		Ys.push_back(val);
		tot.push_back(val);
	}
	sort(Xs.begin(), Xs.end());
	sort(Ys.begin(), Ys.end());
	for(int i = 0; i < tot.size(); i++) {
		if(tot[i] <= Y && tot[i] > X && Xs[Xs.size() - 1] < tot[i] && tot[i] <= Ys[0]) {
			// cout << tot[i];
			ans = 1;
			break;
		}
		ans = 0 ;
	}	
	if(ans) {
		cout << "No War" << "\n";
	}
	else {
		cout << "War" << "\n";
	}
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + (ll)b) % mod
#define MUL(a, b) a = (a * (ll)b) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rer(i, a, b) for(int i = a - 1; i >= b; i--)
#define all(a) (a).begin(), (a).end()
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, pi> ppi;
typedef vector<ll> vec;

const int MAX_N = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;

void Debug() {cout << '\n'; }

template<class FIRST, class... REST> 
void Debug(FIRST arg, REST... rest) { cout << arg << " "; Debug(rest...); }

template<class T>
ostream& operator<< (ostream& out, const vector<T>& v) {
	out << "[";
	if(!v.empty()) {
		rep(i, 0, (int)v.size() - 1) out << v[i] << ", ";
		out << v.back();
	}
	out << "]";
  return out;
}

template<class S, class T>
ostream& operator<< (ostream& out, const pair<S, T>& v) {
	out << "(" << v.first << ", " << v.second << ")";
	return out;
}

///g++ -g3 -std=c++0x -DLOCAL -Wall -ftrapv -D_GLIBCXX_DEBUG -Wl,-stack,268435456 -o
///g++ -O2 -std=c++0x -DLOCAL -Wall -Wl,-stack,268435456 -o

///////////////////////////////////////////////////////////////////////

int N;
pi G[MAX_N];
int A[MAX_N];

ll ans[MAX_N];

int fd(const vector<int>& vec, int a) {
	return lower_bound(all(vec), a) - vec.begin();
}

void solve() {
	cin >> N;
	vector<int> vec;
	rep(i, 0, N) {
		cin >> A[i];
		vec.push_back(A[i]);
	}
	vec.push_back(0);
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	rep(i, 0, (int)vec.size()) {
		G[i].fst = inf;
	}
	rep(i, 0, N) {
		int n = fd(vec, A[i]);
		G[n].sec++;
		MIN(G[n].fst, i); 
	}
	ll sum = 0; int n = inf;
	for(int i = (int)vec.size() - 1; i > 0; i--) {
		sum += G[i].sec;
		MIN(n, G[i].fst);
		ans[n] += sum * (vec[i] - vec[i - 1]);
	}
	rep(i, 0, N) {
		cout << ans[i] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);	
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 3576
n, k = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)
first = 0
(0..n - 2).each do |index|
  (index + 1..n - 1).each do |index2|
    first += 1 if nums[index] > nums[index2]
  end
end

second = 0
nums_2 = nums + nums

(0..n * 2 - 2).each do |index|
  (index + 1..n * 2 - 1).each do |index2|
    second += 1 if nums_2[index] > nums_2[index2]
  end
end

second -= (first * 2)

avg = (k - 1) / 2
count = (avg * k)
if (k - 1).odd?
  count += k / 2
end

ans = first * k + second * count

puts ans % (10 ** 9 + 7)


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

int main()
{
    int w, h, c;
    int g;

    cin >> w >> h >> c;

    for (int i = 1; i <= 1000; i++) {
        if (w % i == 0 && h % i == 0) {
            g = i;
        }
    }

    cout << (w / g) * (h / g) * c << endl;

    return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<long long int,long long int>a,pair<long long int,long long int>b)
{
    if(a.first==b.first)
    {
        if(a.second<=b.second)
        return true;
        else
        return false;
    }
    if(a.first>b.first)
    return true;
    else return false;
}
long long int gcd(long long int bdda,long long int chota)
{
    if(chota==0)
        return bdda;
    return gcd(chota,bdda%chota);
}
void solve()
{
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.length();i++)
    {
        if(s==t)
        {
            cout<<"Yes";
            return;
        }
        s=s.back()+s.substr(0,s.length()-1);
    }
    cout<<"No";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;    
    t=1;

    //cin>>t;
    while(t--)
    {
        solve();
    }
}


Measured memory_bytes: 3660
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n;
char a,b,c;
int32_t main(){
CODE_START;
cin>>a>>b>>c;
if(a=='7'||b=='7'||c=='7'){
    cout<<"Yes"<<endl;
}else cout<<"No"<<endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=100005,INF=1<<28;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N;cin>>N;
        if(N==0) break;
        int a=0,b=0;
        int cnt=0;
        
        for(int i=0;i<N;i++){
            string S;cin>>S;
            if(S=="lu") a++;
            if(S=="ld") a--;
            if(S=="ru") b++;
            if(S=="rd") b--;
            
            if(cnt%2==0&&a==1&&b==1) cnt++;
            if(cnt%2==1&&a==0&&b==0) cnt++;
        }
        
        cout<<cnt<<endl;
    }
}



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

int main()
{
	int n = 1 , x;
	cin >> x;
	int store = x;
	
	
	while (x!=360)
	{
		x = x + store;
		n++;

		if (x > 360)
			x = x - 360;
	}

	cout << n;
	return 0;
	
}



Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int solve(void);
int getItr(const int pos, const int length, vector<string> &w);

int main(void) {

	//FILE* fpin = freopen("data.txt", "r", stdin);

	while (solve()) {}

	return 0;

}

int solve(void) {

	int n;
	int len[] = { 5,7,5,7,7 };

	cin >> n;
	if (!n) { return 0; }

	vector<string> w(n);

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

	for (int j = 0; j < n; j++) {
		int pos = -1 + j;
		for (int i = 0; i < 5; i++) {
			pos = getItr(pos, len[i], w);
			if (pos < 0) { break; }
			if (pos >= 0 && i == 4) {
				cout << j + 1 << endl;
				return 1;
			}
		}
	}

}

int getItr(const int pos, const int length, vector<string>& w)
{
	/*
		w???pos+1????????????????????????????????????
		?????????????????????????????????length????????£?????¨???,?????????????????????????????????????????????
		???????????????-1?????????
	*/
	int cnt = 0;
	for (int i = pos + 1; i < w.size(); i++) {
		cnt += w[i].length();
		if (cnt == length) { return i; }
	}
	return -1;
}

Measured memory_bytes: 3068
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp make_pair
#define F first
#define S second
#define pf pop_front
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1000005;
const ll inf=1e9+7;
typedef pair<ll,ll> pii;
ll k,a,b;
int main()
{
    while(cin>>k)
    {
        ll x=100;
        ll sum=0;
        while(x<k)
        {
            x=x+x*1/100;
            sum++;
            //cout<<x<<"\n";
        }
        cout<<sum<<"\n";
    }
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    cin>>N;

    int ans=10;
    int a0=9;
    int a7=8;
    rep(i,N-1){
        ans*=10;
        ans%=MOD;
        a0*=9;
        a0%=MOD;
        a7*=8;
        a7%=MOD;
    }
    ans=ans-a0*2+a7;
    while(ans<0){ans+=MOD;}

    ans%=MOD;
    cout<<ans<<endl;

    


    



}


Measured memory_bytes: 3608