akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <vector>
const int inf=2147483647;
const int mo=1e9+7;
const int N=300005;
using namespace std;
int n,p[N];
bool check(int l,int r)
{
	int mx=0,mn=inf,lmx=0;
	for(int i=l;i<=r;i++) mx=max(mx,p[i]),mn=min(mn,p[i]);
	if(mn!=l || mx!=r) return false;
	mx=0;
	for(int i=l;i<=r;i+=2)
		if(mx<p[i]) mx=p[i];
		else 
		if(lmx<p[i]) lmx=p[i];
		else return false;
	return true;
}
int main()
{
	//freopen("arc102f.in","r",stdin);
	//freopen("arc102f.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	for(int i=2;i<n;i++)
		if(p[i-1]!=i-1 && p[i]!=i && p[i+1]!=i+1) return printf("No\n"),0;
	for(int i=1;i<=n;i++)
		if(p[i]!=i)
		{
			int x;
			for(x=i;x<=n-2;x+=2)
				if(p[x+1]!=x+1 || p[x+2]==x+2) break;
			if(!check(i,x)) return printf("No\n"),0;
			i=x;
		}
	printf("Yes\n");
}

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

int main(){
  int cards[4][13]={};
  int n, a, b;
  char c;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> c >> b;
    if(c=='S') a = 0; else if(c=='H') a=1; else if(c=='C') a=2; else a=3;
    cards[a][b-1]++;
  }
  
  for(int i=0; i<4; i++)
    for(int j=0; j<13; j++){
      if(cards[i][j]==0){
	if(i==0) c='S'; else if(i==1) c='H'; else if(i==2) c='C'; else c='D';
	cout << c << " " << j+1 << endl;
      }
    }

  return 0;
}

Measured memory_bytes: 1164
N, M, X = [int(i) for i in input().split()]
tolls = [int(i) for i in input().split()]

bigger = []
smaller = []
for t in tolls:
    if t > X :
        bigger.append(t)
    elif t < X :
        smaller.append(t)
        
print(min(len(bigger), len(smaller)))

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<cstdio>

#define fr(a, b, c) for(int a = b; a < c; a++)
using namespace std;

int main() {
    int h, w, a[505][505];
    vector<int> x, y, xd, yd;

    cin >> h >> w;
    fr(i, 0, h) fr(j, 0, w) cin >> a[i][j];
       
    int c = 0;
    fr(i, 0, h) fr(j, 0, w) {
        if (a[i][j] % 2 == 1 && j < w - 1) {
            --a[i][j];  ++a[i][j + 1];  ++c;
            y.push_back(i);  yd.push_back(i);
            x.push_back(j);  xd.push_back(j + 1);
        }
    }

    --w;
    fr(i, 0, h - 1) {
        if (a[i][w] % 2 == 1) {
            --a[i][w];  ++a[i + 1][w];  ++c;
            y.push_back(i);  yd.push_back(i + 1);
            x.push_back(w);  xd.push_back(w);
        }
    }

    cout << c << endl;
    fr(i, 0, c) {
        ++y[i]; ++x[i]; ++yd[i]; ++xd[i];
        printf("%d %d %d %d\n", y[i], x[i], yd[i], xd[i]);
    }
}

Measured memory_bytes: 5220
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
    S = input()

    print(S[0] + str(len(S)-2) +S[-1])


if __name__ == '__main__':
    main()

Measured memory_bytes: 62860
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ll unsigned long long int 
using namespace std;


int main()
{
  ll h,w,c;
  cin>>h>>w>>c;

  if(h+w>c)
    cout<<"No"<<endl;
  else
  {
  ll mid1=c-(h+w);
  ll ans=mid1*mid1;
  if((4*h*w)<ans)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
/*
 * Created By : pash123
 * 2020-08-23-17.55
*/


#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int M=1e9+7;

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

    int dp[n]={INT_MAX};   // dp[i] means min. cost to reach stone i.
    dp[0]=0;
    dp[1]=dp[0]+abs(h[1]-h[0]);
    for(int i=2;i<n;++i)
        dp[i]=min((dp[i-1]+abs(h[i]-h[i-1])),(dp[i-2]+abs(h[i]-h[i-2])));

    cout<<dp[n-1];
    return 0;
}


Measured memory_bytes: 4340
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

void main(){

    int a[];
    int n;
    while(readf("%d\n",&n)){
	//writef("input = %d\n",n);
	if(n == 0){
	    writeln(a[$-1]);
	    //writef("output = %d\n",a[$-1]);
	    a = a[0..$-1];
	}else{
	    a ~= n;
	}
    }
}

Measured memory_bytes: 2464
#include <iostream>
#include<stdio.h>
#include <cmath>
using namespace std;
//#define double PI = acos(-1);
int main(){

   double a,b;
    int c;
    cin>>a>>b>>c;
    double s,l,h;
    double PI = acos(-1);
   double rad = c * PI / 180;
    s=0.5*a*b*sin(rad);
    h=s/a * 2;
    l=sqrt(pow(a,2)+pow(b,2)-2*a*b*cos(rad));
    l=l+a+b;
    printf("%f\n%f\n%f\n",s,l,h);
    
return 0;
}



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

int main(){
	long long int A,B;
	while(1){
		cin>>A>>B;
		if(A==0&&B==0)break;

		int Q=B-A;
		int p=0,q=0,v=0;
		if(Q>=1000){v=Q/1000;Q=Q%1000;}
		if(Q>=500){q=Q/500;Q=Q%500;}
		if(Q>=100){p=Q/100;}

		printf("%d %d %d\n",p,q,v);
		
	}
	return 0;
}

Measured memory_bytes: 1144
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))

fgcd, ftmp = [], a[0]
for i in a:
    ftmp = gcd(ftmp, i)
    fgcd.append(ftmp)

bgcd, btmp = [], a[-1]
for i in a[::-1]:
    btmp = gcd(btmp, i)
    bgcd.append(btmp)
bgcd = bgcd[::-1]

egcd = [bgcd[1]] + [0] * (n - 2) + [fgcd[n - 2]]
for i in range(1, n - 1):
    egcd[i] = gcd(fgcd[i - 1], bgcd[i + 1])
print(max(egcd))


Measured memory_bytes: 16152
fn main() {
    let n = read::<u8>();
    let s = read::<String>();

    println!("{}",
             s.chars().map(|c| ((c as u8 - 65 + n) % 26 + 65) as char)
             .collect::<String>()
    );
}

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


Measured memory_bytes: 4352
#include <iostream>
#define MAX 1000
using namespace std;

int main(void){
  int K,A,B;
  cin >> K;
  cin >> A >> B;
  int under = A/K;
  int top = B/K;
  for(int i=1;i*K <= MAX;i++){
    int num = i*K;
    if(A <= num && num <= B){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG"<< endl;
  return 0;
}


Measured memory_bytes: 3632
// C.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

typedef long double LD;

int main(int argc, char* argv[]) {
	LD l;
	cin >> l;
	LD a = l / 3;
	LD ans = a * a * (l - 2 * a);
	printf("%.9lf\n", (double)ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

void swap(int&, int&);

int main(){
  int x, y;

  while(cin >> x >> y){
    if(x < y) swap(x, y);

    while(y != 0){
      x %= y;
      swap(x, y);
    }

    cout << x << endl;
  }
  return 0;
}

void swap(int& x, int& y){
  int z;
  z = x;
  x = y;
  y = z;
}

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

using namespace std;
#define ll long long
#define pb push_back

int main()
{
    int m, n_min, n_max;
    vector<int> x;
    while (1)
    {
        cin >> m >> n_min >> n_max;
        if (m == 0)
        {
            break;
        }
        int sum = 0;
        int total = 0;
        vector<int> a(m);
        for (int i = 0; i < m; i++)
        {
            cin >> a[i];
        }
        int cnt = 0;
        int difference = 0;
        // 平均をずらしていく
        for (int i = n_min-1; i < n_max; i++)
        {
            int tmp_diff = abs(a[i] - a[i+1]);
            // cout << a[i]  << a[i+1] << endl;
            if (tmp_diff >= difference)
            {
                difference = tmp_diff;
                cnt = i + 1;
            }
        }
        x.push_back(cnt);
    }
    for (int i = 0; i < x.size(); i++)
    {
        cout << x[i] << endl;
    }
}



Measured memory_bytes: 3108
import java.util.*;

public class Main{
    static Scanner sc = new Scanner(System.in);

    static int n = sc.nextInt();
    static int[] arr = new int[n];

    static int[][] x = new int[n][];
    static int[][] y = new int[n][];


    public static void main(String[] args){

        for (int i=0; i<n; i++){
            arr[i] = sc.nextInt();
            x[i] = new int[arr[i]];
            y[i] = new int[arr[i]];
            for (int j=0; j<arr[i]; j++){
                x[i][j] = sc.nextInt()-1;
                y[i][j] = sc.nextInt();
            }
        }

        int[] condition = new int[n];
        int cnt = 0;

        for (int bit=0; bit<(1<<n); bit++){
            int tmp = 0;
            for (int i=0; i<n; i++){
                if ((bit&(1<<i))>0){
                    condition[i] = 1;
//                    System.out.println("E");
                }else {
                    condition[i] = 0;
                }
            }

            if (check(condition)){
                for (int i=0; i<n; i++){
                    if (condition[i]==1) {
                        tmp++;
//                        System.out.println(tmp);
                    }
                }
            }

            cnt = Math.max(cnt, tmp);
        }
        System.out.println(cnt);

    }

    public static boolean check(int[] condition){
        for (int i=0; i<n; i++){
            if (condition[i]==1){
                for (int j=0; j<arr[i]; j++){
                    if (condition[x[i][j]]!=y[i][j]){
                        return false;
                    }
                }
            }
        }
        return true;
    }

}

Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<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; }


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char s;cin>>s;
    if(isupper(s)){
        cout<<"A"<<endl;
    }else{
        cout<<"a"<<endl;
    }
}

Measured memory_bytes: 3612
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		char[] s = sc.next().toCharArray();
		int N = s.length;
		
		for(int i=0; i<((N-1)/2+1)/2; i++) {
			if(s[i] != s[(N-1)/2-1-i] || s[i] != s[(N-1)/2+1+i] || s[i] != s[N-1-i]) {
				System.out.println("No");
				sc.close();
				return;
			}
		}
		System.out.println("Yes");

		sc.close();
	}
}


Measured memory_bytes: 25172
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;


int main(){
  int n, a, b;
  cin >> n >> a >> b;
  int ans = min(b, n * a);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a-1);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
const int INF = 1e18;
const int MOD = 1e9+7;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef string str;
typedef vector<str> vstr;
void print() {cout<<endl;}template<class Head,class...Tail>void print(Head&&head,Tail&&...tail){cout<<head;if(sizeof...(tail)!=0)cout<<" ";print(forward<Tail>(tail)...);}template<class T>void print(vector<T>&vec){for(auto&a:vec){cout<<a;if(&a!=&vec.back())cout<<" ";}cout<<endl;}template<class T>void print(vector<vector<T>>&df){for(auto&vec:df){print(vec);}}
template<class T=int>T in() {T x;cin>>x;return(x);}
template<class T=int>vector<T> input_to_vector(int n) {vector<T>x;rep(i,n){T a;cin>>a;x.push_back(a);}return(x);}

signed main(){
    int n = in();
    vint L = input_to_vector(n);
    sort(all(L));
    int tmp = 0;
    rep(i, n-1){
        tmp += L[i];
    }
    if (L.back() < tmp){
        print("Yes");
    } else {
        print("No");
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n;
  cin >> n;
  ll res = 0, max = 0;
  rep(i, n) {
    ll a;
    cin >> a;
    if (max <= a) {
      res++;
      max = a;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

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

    int n;

    cin >> n;

    vector<int> a(n);

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

    int max = a[0];

    for(int i = 1; i < n; i++){
        if(max < a[i]){
            max = a[i];
        }
    }
    
    int h = max/2;


    
    int dist = ((max != a[0])?
                            (a[0] <= max/2? a[0] : max - a[0]):
                            (a[1] <= max/2? a[1] : max - a[1]));
    int result = max != a[0]?
                            a[0] :a[1] ;

    for(int i = 1; i < n; i++){
        if(a[i] <= max/2){
            if(dist < a[i]){
                dist = a[i];
                result = a[i];
            }
        }else{
            int tmp = max - a[i];
            if(dist < tmp){
                dist = tmp;
                result = a[i];
            }
        }
    }

    cout << max << " ";
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 640
N = int(input())

T, A = [int(i) for i in input().split()]

h_list = map(int, input().split())

temp_list = [(i, abs(A - (T-x*0.006))) for i, x in enumerate(h_list, 1)]

ans = min(temp_list, key=lambda x: x[1])

print(ans[0])


Measured memory_bytes: 9292
#include<bits/stdc++.h>
#define ll long long int 
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
using namespace std;
int main(){
#ifndef ONLINE_JUDGE 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans=-1e18;
	ans=max(ans,a*c);
	ans=max(ans,a*d);
	ans=max(ans,b*c);
	ans=max(ans,b*d);
	cout<<ans;

	
	
}

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

int main(){
	ll l,r;
	cin >> l >> r;
	if(r-l >= 2019){
		cout << 0 << endl;
		return 0;
	}
	l %= 2019;
	r %= 2019;
	if(r >= l){
		ll ans(2019);
		for(int i(l);i<=r-1;++i){
			for(int j(l+1);j<=r;++j){
				if(ans > (i*j)%2019) ans = (i*j)%2019;
			}
		}
		cout << ans << endl;
	}else{
		cout << 0 << endl;
	}
	return 0;
}

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

int main(){
    int A, B;
    cin >> A >> B;
    int ans = 1;
    if(B == 1) {
      ans = 0;
    } else {
      int count = A;
      while(count < B){
        ans++;
        count += A-1;
      }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
s = input()
import numpy as np
s_int = np.array([0]*n)
for i in range(n):
  if s[i] == 'L':
    s_int[i] = -1
  else:
    s_int[i] = 1
    

for l in range(1, n-1):
  if k == 0:
    break
  if s_int[l] != s_int[l-1]:
    for r in range(l+1, n):
      if s_int[r] == s_int[l-1]:
        part = s_int[l:r]
        s_int[l:r] = part[::-1] * -1
        k -= 1
        break

if k > 0:
  print(n-1)
  exit()
ans = n-1
for i in range(1, n):
  if s_int[i] != s_int[i-1]:
    ans -= 1
print(ans)

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

using namespace std;

int y;
int n;
long long init;

int main() {
	int m; cin >> m;
	while (m--) {
   		cin >> init;
		cin >> y;
		cin >> n;
		long long money[n];
		for (int i = 0; i < n; i++) {
			int type; cin >> type;
			double rate; cin >> rate;
			int pay; cin >> pay;
			if (type == 0) {
				money[i] = init;
				long long interest = 0;
				for (int j = 0; j < y; j++) {
					interest += money[i] * rate;
					money[i] -= pay;
				}
				money[i] += interest;
			} else {
				money[i] = init;
				for (int j = 0; j < y; j++) {
					money[i] *= (rate + 1);
					money[i] -= pay;
				}
			}
		}

		long long max_money = money[0];
		for (int i = 1; i < n; i++) 
			max_money = max(max_money, money[i]);

		cout << max_money << endl;
	}
	return 0;
}

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

static const int N = 1000;

int lcs(string X, string Y) {
  int c[N + 1][N + 1];
  int m = X.size();
  int n = Y.size();
  int maxl = 0;

  X = ' ' + X; // X[0] に空文字を挿入
  Y = ' ' + Y;
  for (int i = 0; i <= m; i++) c[i][0] = 0;
  for (int j = 0; j <= n; j++) c[0][j] = 0;

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i] == Y[j]) c[i][j] = c[i - 1][j - 1] + 1;
      else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
      maxl = max(maxl, c[i][j]);
    }
  }

  return maxl;
};

int main(){
  string s1, s2;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s1 >> s2;
    cout << lcs(s1, s2) << endl;
  }
}



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

int main() {
	int h, w;
	cin >> h >> w;
	
	vector<string> a(h);
	for (int i = 0; i < h; ++i) {
		cin >> a[i];
	}
	
	vector<bool> row(h, false);
	vector<bool> col(w, false);
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (a[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}
	
	for (int i = 0; i < h; ++i) {
		if (row[i]) {
			for (int j = 0; j < w; ++j) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}


Measured memory_bytes: 256
# import sys 
# import os
# path = os.path.join(os.getcwd(),'input.txt')
# input = open(path).readline

import numpy as np
S = input()
cand = np.zeros(2019,dtype=int)
rem = 0
order = 1
mod = 2019
for s in S[::-1]:
    rem += (int(s)*order)%mod
    rem %= mod
    cand[rem] +=1
    order *= 10
    order %=mod
ans = cand[0]
cand = cand[cand>1]
for c in cand:
    ans += c*(c-1)/2
print(int(ans))

Measured memory_bytes: 27324
#include <stdio.h>
#include <string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail +1)%LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head+1)%LEN;
  return x;
}

int min(int a, int b) {return a < b ? a : b;}

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n+1;

  while(head != tail)
    {
      u = dequeue();
      c = min(q,u.t);
      u.t -= c;
      elaps += c;
      if(u.t>0) enqueue(u);
      else printf("%s %d\n",u.name,elaps);
    }  
  return 0;
}



Measured memory_bytes: 11880
s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:    
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
           
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0 :
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] +ans
        i -= 1
        j -= 1
print(ans)


Measured memory_bytes: 113116
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define LLint long long int
#define Lint long int
#define Ldouble long double

// class UnionFind;

// bool sortBySec(const pair<int, int>& a, const pair<int, int>& b);
// int modExp(int x, int n, int m);
// int mmi(int x, int m);

int a, b, c, d;

void solve() {
    cin >> a >> b >> c >> d;
    while (true) {
        c -= b;
        if (c <= 0) {
            cout << "Yes";
            return;
        }
        a -= d;
        if (a <= 0) {
            cout << "No";
            return;
        }
    }
}

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

    solve();

    return EXIT_SUCCESS;
}

// Helpers.
/*
bool sortBySec(const pair<int, int>& a, const pair<int, int>& b) {
    return (a.second < b.second);
}
*/
// Modular arithmetic.
/*
int modExp(const int x, const int n, const int m) {
    if (n == 0) {
        return 1;
    }
    LLint u = modExp(x, n / 2, m);
    return n % 2 == 0 ? (u * u) % m : (((u * u) % m) * x) % m;
}
*/
/*
int mmi(const int x, const int m) { return modExp(x, m - 2, m); }
*/
// Union find data structure.
/*
class UnionFind {
   public:
    vector<int> link;
    vector<int> size;

    UnionFind(int n) {
        link = vector<int>(n);
        size = vector<int>(n);
        for (int i = 0; i < n; i++) {
            link[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        while (x != link[x]) {
            x = link[x];
        }
        return x;
    }

    bool same(int a, int b) { return find(a) == find(b); }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (size[a] < size[b]) {
            swap(a, b);
        }
        size[a] += size[b];
        link[b] = a;
    }
};
*/


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

#define rep(i,l,n) for(int (i)=(l);(i)<(n);(i)++)
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
#define abs(a) (a)>0?(a):-(a)
#define llong long long

int main(){
	int R; scanf("%d",&R);
	printf("%f",2*R*M_PI);
	return 0;
}


Measured memory_bytes: 1752
#include <stdio.h>
#include <cstdio>
#include <string>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>


int No = 0;
int Two = 0;
int Four = 0;

int main()
{
	int N;
	long long int buf;

	scanf("%d", &N);

	for (int a = 0; a < N; ++a)
	{
		scanf("%lld", &buf);
		if (buf % 2 == 0)
		{
			if (buf % 4 == 0) Four++;
			else Two++;
		}
		else No++;
	}

	if (Two >= 2) Two = 1;

	if (Two + No <= Four + 1) puts("Yes");
	else puts("No");

	return 0;
}

Measured memory_bytes: 256
require "prime"
max = 1120
arr = Array.new(max + 1){Hash.new(0)}
Prime.each(max){|prime|
    (max - prime).downto(0){|i|
        arr[i].each{|k, v|
            arr[prime + i][k + 1] += v if k <= 14
        }
    }
    arr[prime][1] += 1
}

while true
    n, k = gets.chomp.split.map(&:to_i)
    break if [n, k] == [0, 0]
    puts arr[n][k]
end


Measured memory_bytes: 7652
#include <stdio.h>

int n, m, a;

int main() {
    while (1) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
}


Measured memory_bytes: 2600
import sys
from collections import deque
import copy
import math

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    A = []
    input_raw = read_func().strip().split()
    A.append(int(input_raw[0]))
    input_raw = read_func().strip().split()
    A.append(int(input_raw[0]))
    input_raw = read_func().strip().split()
    A.append(int(input_raw[0]))
    input_raw = read_func().strip().split()
    A.append(int(input_raw[0]))
    input_raw = read_func().strip().split()
    A.append(int(input_raw[0]))


    max_idx = 0
    max_mod = 0
    for i in range(5):
        if abs(10 - A[i] % 10)% 10> max_mod:
            max_mod = abs(10 - A[i] % 10) % 10
            max_idx = i
    time = 0
    for i in range(5):
        if i != max_idx:
            time += A[i] + (abs(10 - A[i] % 10)% 10)
    time += A[max_idx]
    print time


if __name__ == '__main__':
    main()


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

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

  vector<ll> h(n);
  for (ll i = 0; i < n; i++) cin >> h[i];
  
  vector<ll> dp(n, __INT_MAX__);
  dp[0] = 0;
  for (ll i = 0; i < n; i++) {
    ll j1 = min(i + 1, n - 1);
    ll j2 = min(i + 2, n - 1);
    dp[j1] = min(dp[j1], dp[i] + abs(h[i] - h[j1]));
    dp[j2] = min(dp[j2], dp[i] + abs(h[i] - h[j2]));
  }

  cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <climits>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#define y0 qvya13579
#define y1 qvyb24680
#define j0 qvja13579
#define j1 qvjb24680
#define next qvne13579xt
#define prev qvpr13579ev
#define INF 1000000007
#define PI acos(-1.0)
#define endl "\n"
#define IOS cin.tie(0);ios::sync_with_stdio(false)
#define M_P make_pair
#define P_B push_back
#define U_B upper_bound
#define L_B lower_bound
#define P_Q priority_queue
#define FIR first
#define SEC second
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP_R(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZ(x) ((int)(x).size())
#define COUT(x) cout<<(x)<<endl
#define CIN(x) cin>>(x)
#define CIN2(x,y) cin>>(x)>>(y)
#define CIN3(x,y,z) cin>>(x)>>(y)>>(z)
#define CIN4(x,y,z,w) cin>>(x)>>(y)>>(z)>>(w)
#define SCAND(x) scanf("%d",&(x))
#define SCAND2(x,y) scanf("%d%d",&(x),&(y))
#define SCAND3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define SCAND4(x,y,z,w) scanf("%d%d%d%d",&(x),&(y),&(z),&(w))
#define SCANLLD(x) scanf("%lld",&(x))
#define SCANLLD2(x,y) scanf("%lld%lld",&(x),&(y))
#define SCANLLD3(x,y,z) scanf("%lld%lld%lld",&(x),&(y),&(z))
#define SCANLLD4(x,y,z,w) scanf("%lld%lld%lld%lld",&(x),&(y),&(z),&(w))
#define PRINTD(x) printf("%d\n",(x))
#define PRINTLLD(x) printf("%lld\n",(x))
typedef long long int lli;
using namespace std;

int ctoi(char c)
{
  if( c >= '0' and c <= '9' )
    {
      return (int)(c-'0');
    }

  return -1;
}

int alphabet_pos(char c) 
{
  if( c >= 'a' and c <= 'z' )
    {
      return (int)(c-'a');
    }

  return -1;
}


int alphabet_pos_capital(char c)
{
  if( c >= 'A' and c <= 'Z' )
    {
      return (int)(c-'A');
    }

  return -1;
}


vector<string> split(string str, char ch)
{
  int first = 0;
  int last = str.find_first_of(ch);
  
  if(last == string::npos)
    {
      last = SIZ(str);
    }

  vector<string> result;

  while( first < SIZ(str) )
    {
      string Ssubstr(str, first, last - first);
      result.push_back(Ssubstr);
      first = last + 1;
      last = str.find_first_of(ch, first);

      if(last == string::npos)
	{
	  last = SIZ(str);
	}
    }
  
  return result;
}

/*--------------- the end of the template --------------------*/



int numfac( int N )
{
  int cnt = 0;
  
  FOR(n,1,N+1)
    {
      if( N % n == 0 )
	{
	  ++ cnt;
	  
	}
    }
  
  return cnt;
  
}





int main()
{
  //IOS; /* making cin faster */
  int N,i;
  SCAND(N);
  int cnt = 0;
  
  for( i = 1 ; i <= N ; i += 2 )
    {
      if( numfac(i) == 8 )
	{
	  ++ cnt;
	  
	}
    }

  PRINTD(cnt);
  
  

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0; i<(int)(n); ++i)
#define REP(i,m,n) for(ll i=(ll)(m); i<(ll)(n); ++i)
#define F first
#define S second
const double PI=acos(-1);
//fixed<<setprecision(11)<<

char in[120];
pair<pair<string,int>,int> p[110];
int main(){
  int a;
  cin>>a;
  rep(i,a){
  int t;
  cin>>in>>t;
  string tmp=in;
  p[i]=make_pair(make_pair(in,-t),i);
  }
  sort(p,p+a);
  rep(i,a) cout<<p[i].second+1<<endl;
}

Measured memory_bytes: 3548
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

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

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }

#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


using pint = pair<int,int>;
int N;
vector<vector<pint>> v;



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

    while (cin >> N) {
        v.assign(N, vector<pint>());
        for (int i = 0; i < N; ++i) {
            int a; cin >> a;
            v[i].resize(a);
            for (int j = 0; j < a; ++j) {
                cin >> v[i][j].first >> v[i][j].second;
                --v[i][j].first;
            }
        }

        int res = 0;
        for (int bit = 0; bit < (1<<N); ++bit) {
            bool ok = true;
            for (int i = 0; i < N; ++i) {
                if (!(bit & (1<<i))) continue;

                for (auto p : v[i]) {
                    if (p.second == 1) {
                        if (!(bit & (1<<p.first))) ok = false;
                    }
                    else {
                        if (bit & (1<<p.first)) ok = false;
                    }
                }
            }
            if (ok) {
                int con = 0;
                for (int j = 0; j < N; ++j) if (bit & (1<<j)) ++con;
                res = max(res, con);
            }
        }
        cout << res << endl;
    }
}


















Measured memory_bytes: 256
/*----- || Hare Krishna || -----*/

/*  "WHY DO WE FALL, BRUCE?"  */

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define pb push_back
#define pf push_front
#define PI 3.1415926535897932384
#define MOD 1000000007
using namespace std;

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

int t;

ll S;

ll dp[2001];

ll solve(ll idx, ll prev_sum){
	
	
	if(prev_sum==S){
		return 1;
	}
	if(prev_sum>S){
		return 0;
	}
	if(dp[prev_sum]!=-1){
		return dp[prev_sum];
	}
//	cout << idx << ' ' <<prev_sum << endl;
	ll ans=0;
	
	for(int i=3; i<=S; i++){
		ans += (solve(idx+1, prev_sum+i)+MOD)%MOD;
	}
	
	return dp[prev_sum]=(ans+MOD)%MOD;
	
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    
    cin >> S;
    memset(dp,-1,sizeof(dp));
    cout << solve(0,0);
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
#define ALL(a) a.begin(),a.end()
#define IN(a, x, b) (a<=x && x<b)
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void OUT(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void OUT(T t,Ts... ts){cout<<t<<" ";OUT(ts...);}
template<typename T=int>vector<T>mv(size_t a){return vector<T>(a);}
template<typename T=int,typename... Ts>auto mv(size_t a,Ts... ts){return vector<decltype(mv<T>(ts...))>(a,mv<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type FILL(T&t,const V&v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type FILL(T&t,const V&v){for(auto &e:t)FILL(e,v);}
constexpr long long INF = 1e18;

signed main(){
	int N;
	cin>>N;
	if(N<3)cout << "No" << endl;
	else{
		int t = (N+1)%4;
		int bitCount = 0;
		REP(i,60)if(N&(1ll<<i))bitCount++;
		if(t==1&&bitCount==1){
			cout << "No" << endl;
			return 0;
		}
		cout << "Yes" << endl;
		if(t==0){
			REP(i,N*2-1){
				OUT(i+1,i+2);
			}
			return 0;
		}
		N-=t;
		REP(i,N-1)OUT(i+1,i+2);
		OUT(N,N+1+t);
		REP(i,N-1)OUT(N+t+i+1,N+t+i+2);
		int n = (N+t)^(N+t-4);
		if(t==1){
			OUT(N-2,N+1);OUT(2*(N+t),N+t+n);
			return 0;
		}
		OUT(N+t+1,N+2);OUT(N+1,N+2);
		OUT(N+t+1,N+t+N+1);OUT(N+t+N+2,N+t+N+2-1);
		if(t==3){OUT(N+t+2,N+t+N+3);OUT(N+2,N+3);}
	}
}	


Measured memory_bytes: 2816
N = int(input())
SP = []
for i in range(N):
  c, p = input().split()
  SP.append([i+1, c, int(p)])
SP = sorted(SP, key=lambda x:x[2], reverse=True)
SP = sorted(SP, key=lambda x:x[1])
for s in SP:
  print(s[0])

Measured memory_bytes: 3060
#include <stdio.h>

int main(void) {
    int i, j, H, W;
    while(scanf("%d %d", &H, &W), H || W) {
        for(i = 0; i < H; i++) {
            for(j = 0; j < W; j++) {
                printf("%c", (i + j) % 2 ? '.' : '#');
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

typedef pair<int,int> pii;
typedef long long int ll;

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int n,m;
int a,b;
set<int> first;
set<int> second;
set<int> result;
int main(){
  scanf("%d %d",&n,&m);
  REP(i,m){
    scanf("%d %d",&a,&b);
    if(a==1) first.insert(b);
    if(a==n) second.insert(b);
    if(b==1) first.insert(a);
    if(b==n) second.insert(a);
  }
  set_intersection(first.begin(),first.end(),second.begin(),second.end(),inserter(result,result.end()));
  if(result.size()>0){
    printf("POSSIBLE\n");
  }else{
    printf("IMPOSSIBLE\n");
  }
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;

const int maxn = 2005;
const int mod = 1000000007;
struct edge {
	int u, v, w;
	bool operator < (const edge &e) const {
		return w < e.w;
	}
} e[maxn];
int pa[maxn], n, m, le, eq, ge, ans;
ll now, X;

inline int power(int x, int p) {
	int res = 1;
	while (p) {
		if (p & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod; p >>= 1;
	}
	return res;
}

inline int getpa(int x) {
	return pa[x] == x ? x : pa[x] = getpa(pa[x]);
}

ll MST() {
	ll res = 0;
	rep (i, 1, n) pa[i] = i;
	rep (i, 0, m)
		if (getpa(e[i].u) != getpa(e[i].v)) {
			pa[getpa(e[i].u)] = getpa(e[i].v);
			res += e[i].w;
		}
	return res;
}

int main() {
	scanf("%d%d", &n, &m); 
	scanf("%lld", &X);
	rep (i, 1, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + m + 1);
	rep (i, 1, m) {
		e[0] = e[i];
		now = MST();
		if (now < X) le++;
		if (now == X) eq++;
		if (now > X) ge++;
	}
	if (!eq) return puts("0"), 0;
	ans = (le ? 2ll * (power(2, eq) + mod - 1) : power(2, eq) + mod - 2) * power(2, ge) % mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
def func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
import sys
sys.setrecursionlimit(1000000)
n,m = map(int, input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n))

Measured memory_bytes: 89668
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());

	long long ans = 0;
	int now = 0;
	for (int i = 0; i < n; i++) {
		if (m - now >= a[i].second) {
			ans += (long long)a[i].first * a[i].second;
			now += a[i].second;
		}
		else {
			ans += (long long)a[i].first * (m - now);
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main(){
  ll n;
  cin>>n;
  string key;
  map<string, int> score;
  rep(i,n){
      cin>>key;
      if (score.count(key)) {
 
}
else {
  score[key]=1;
}
  }
  cout<<score.size()<<endl;
}
   



Measured memory_bytes: 19208
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define per(i,x,y) for (int i=(x);i>=(y);i--)
#define ll long long
#define inf 1000000001
using namespace std;
int read(){
	char ch=getchar();int x=0,op=1;
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') op=-1;
	for (;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
#define N 200005
#define mod 1000000007
#define inv2 500000004
int n,a[N],cnt[N],val0[N],val1[N],val2[N],val3[N],pos[N],ans;
int ksm(int x,int p){
	int ret=1;
	for (;p;p>>=1,x=(ll)x*x%mod) if (p&1) ret=(ll)ret*x%mod;
	return ret;
}
int getinv(int x){return ksm(x,mod-2);}
void upd(int &x,int y){x+=y;x-=x>=mod?mod:0;}
struct bit{
	int t[N];
	void clr(){memset(t,0,sizeof(t));}
	void add(int x,int val){
		for (int i=x;i<=n;i+=i&-i) upd(t[i],val);
	}
	int qry(int x){
		int ret=0;
		for (int i=x;i;i-=i&-i) upd(ret,t[i]);
		return ret;
	}
}tr;
int main(){
	n=read();
	rep (i,1,n) cnt[a[i]=read()]++;
	per (i,n-1,1) cnt[i]+=cnt[i+1]-1;
	rep (i,1,n) if (cnt[i]<=0){puts("0");exit(0);}
	val0[0]=val1[0]=1;
	rep (i,1,n){
		val0[i]=(ll)val0[i-1]*cnt[i]%mod;
		val1[i]=(ll)val1[i-1]*max(cnt[i]-1,1)%mod;
		val2[i]=(ll)val0[i]*getinv(val1[i])%mod;
		val3[i]=(ll)val1[i]*getinv(val0[i])%mod;
	}
	tr.clr();
	pos[n]=n;
	per (i,n-1,1) pos[i]=cnt[i+1]==1?i:pos[i+1];
	per (i,n,1){
		int val=(tr.qry(pos[a[i]])+mod-tr.qry(a[i]-1))%mod;
		upd(ans,(ll)val*val2[a[i]]%mod);
		tr.add(a[i],val3[a[i]]);
	}
	tr.clr();
	pos[1]=1;
	rep (i,2,n) pos[i]=cnt[i]==1?i:pos[i-1];
	per (i,n,1){
		int val=(tr.qry(a[i]-1)+mod-tr.qry(pos[a[i]]-1))%mod;
		upd(ans,(mod-(ll)val*val3[a[i]]%mod)%mod);
		tr.add(a[i],val2[a[i]]);
	}
	ans=(ll)ans*inv2%mod;
	tr.clr();
	per (i,n,1){
		upd(ans,tr.qry(a[i]-1));
		tr.add(a[i],1);
	}
	ans=(ll)ans*val0[n]%mod;
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,m;
  cin>>N>>m;
  
  vector<int>A(m);
  vector<int>B(m);
  for(int i=0;i<m;i++){
    cin>>A.at(i)>>B.at(i);
  }
  
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  if(B.at(0)-A.at(m-1)+1<=0){
    cout<<0<<endl;
    return 0;
  }
  cout<< B.at(0)-A.at(m-1)+1 <<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c;
  while(cin >> a >> b >> c && (a||b||c)) {
    if(c==0) {
      if(a!=1)cout << a << " " << b << " " << 1 << " " << 0 << endl;
      else cout << a << " " << max(b,0) << " " << 1 << " " << min(b,0) << endl;
      continue;
    }
    for(int r=1; r<=a; r++) {
      if(a%r) continue;
      int p=a/r;
      for(int s=-10000; s<=10000; s++) {
    if(s==0) continue;
    if(c%s) continue;
    int q=c/s;
    if(p>0 && r>0 && (p>r || (p==r && q>=s))) {
      if(p*s+q*r==b) {
        cout << p << " " << q << " " << r << " " << s << endl;
        goto end;
      }
    }
      }
    }
    cout << "Impossible" << endl;
    end:;
  }
  return 0;
}


Measured memory_bytes: 1164
#include<stdio.h>
int main()
{
   

    int N;
  
    scanf("%d", &N);
  	long B[N-1];
   	long A[N];
  int i=0;
  for(i=0;i<N-1;i++){
  scanf("%ld",&B[i]);
  }
  
  
  
  for(i=0;i<N;i++){
	A[i] = 0;
  }
  
  for(i=0;i<N-1;i++){
   if(i==0){
    A[i] = B[i];
   }
     if(i > 0 && A[i] > B[i]){
	A[i] = B[i];
   
  }
     A[i+1] = B[i];
  }
  
  long ans = 0;
    for(i=0;i<N;i++){
	ans = ans + A[i];
  }
  printf("%ld",ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll                  long long
#define dl                 double
#define pb                push_back
#define F                  first
#define S                  second
#define endl              "\n"
#define rep(i,a,b)       for(i=a;i<b;i++)
#define all(v)             v.begin(),v.end()
#define allr(v)            v.rbegin(),v.rend()
#define mod              1000000007LL
#define CIN(V,s,n)      for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n)   {for(int i=s;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define CLEAR(V);      for(ll i=0;i<V.size();i++) V[i] = 0;
#define N                  150
#define tmod             998244353LL
using namespace std;

bool sBs(const pair<int,int> &a,const pair<int,int> &b)
{   return (a.second < b.second);   }

ll SUMD(ll n);
ll BS(vector<pair< ll ,ll > > &PS,ll s,ll e,ll ser);
ll MI(ll a, ll m);
//bool P[N+1];
void Sieve(int n=N);
ll Powb(ll b,ll n,ll m);

vector<vector<int> > G(200005);
vector<ll> A(200005),ans(200005,1);

void DFS(ll s,ll p,ll &l,vector<ll> &V)
{
    ll ol = l,ov;
    auto it = lower_bound(V.begin(),(V.begin()+l),A[s]);
    if(it==V.begin()+l) V[l++] = A[s];
    else {ov = (*it); *it = A[s];}
    ans[s] = l;
    for(auto it:G[s]) if(it!=p) DFS(it,s,l,V);
    if(ol==l) *it = ov;
    else l--;
}

int main()
{
fast;
ll q=1,t;
//cin >> q;
while(q--)
{
    ll i,j,n,m,k,l,r,a,b,c=0,d=0,e,g,p,q,u,v,w,x,y,flag=1;
    //n=m=k=i=j=l=r=a=b=c=d=u=v=w=p=x=y=0;
    cin >> n >> m;
    ll tm = (n-1)/2;
    vector<pair<int,int> >  V;
    vector<ll> A;
    for(i=1;i<=(tm+1)/2;i++)
    {
        A.pb(i); A.pb(i+tm+1);
    }
    for(i=tm;i>=1;i--)
    {
        V.pb({A[tm-i],A[tm-i]+i});
    }

    for(i=1;i<=m;i++)
    {
        cout << V[i-1].F << " " << V[i-1].S<<endl;
    }


}
    return 0;
}

//*****************************************************************************************************************************************

ll Powb(ll b,ll n,ll m)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2,m);
    if(n%2==0){return (temp*temp)%m;}
    else{return (b*((temp*temp)%m))%m;}
}

ll SUMD(ll n)
{   ll sum=0;
    while(n>0){sum += n%10;n = n/10;}
    return sum;

}
ll BS(vector<pair<ll,ll> > &PS,ll s,ll e,ll ser)
{
    if(s>e)
        return s;
    ll mid = (s+e)/2;
    if(PS[mid].F==ser)
    {
        return mid;
    }
    else if(PS[mid].F > ser)
    {
        return BS(PS,s,mid-1,ser);
    }
    else
        return BS(PS,mid+1,e,ser);
}
ll MI(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
      return 0;
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
       x += m0;
    return x;
}
/*
void Sieve(int n)
{
    memset(P,true,sizeof(P));
    P[0] = false;
    P[1]= false;
    for(ll i=2;i*i<=n;i++)
    {
        if(P[i])
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                P[j]=false;
            }
        }
    }

}

*/


Measured memory_bytes: 13352
# AOJ 0546: Lining up the cards
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

def rec(i, m):
	global n, k, ans
	if i >= k:
		if m not in dic:
			ans += 1
			dic[m] = 1
		return
	for j in range(n):
		if f[j]: continue
		f[j] = 1
		if c[j] < 10: rec(i+1, m*10 + c[j])
		else:         rec(i+1, m*100+ c[j])
		f[j] = 0

while True:
	n, k = int(input()), int(input())
	if n == 0: break
	dic = {}
	f = [0]*12
	c = [int(input()) for i in range(n)]
	ans = 0
	rec(0, 0)
	print(ans)


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

int main() {
  
  int64_t H; cin >> H;
  
  int count = 0; int64_t ans = 1; int64_t tmp = 1;
  
  while (true) {
    
    if (H == 1) break;
    
    H /= 2; count++;
    
  }
  
  for (int i = 0; i < count; i++) {
    
    tmp *= 2; ans += tmp;
    
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		int[] road = new int[a];

		for(int i = 0; i < a; i++) {
			road[i] = 0;
		}

		for(int i = 0; i < b; i++) {
			int c = sc.nextInt()-1;
			int d = sc.nextInt()-1;

			road[c] += 1;
			road[d] += 1;
		}

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

	}

}


Measured memory_bytes: 20948
function Main(input) {
  const numbers = input.split(' ').map(n => Number(n));
  const x = numbers[0];
  const a = numbers[1];
  const b = numbers[2];

  if (Math.abs(x - a) > Math.abs(x - b)) {
    console.log('B');
  } else {
    console.log('A');
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
  
  int a,b,c,d,x,y;
  cin >> a >> b >> c >> d;
  
  if ( a >= b ){
    x = b;
  }else{
    x = a;
  }
  
  if ( c >= d ){
    y = d;
  }else{
    y = c;
  }
  
  cout << x + y << endl;
  
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()

int main() {
	char a;
	int b, c;
	cin >> b >> a >> c;
	if (a == '+') cout << b + c << endl;
	else cout << b - c << endl;
}

Measured memory_bytes: 256