akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	/**/
	public static void main(String[] args) {  
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		String S = I.next();
		int N = S.length();
		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum+=S.charAt(i)-'0';
			sum%=9;
		}
		O.pln(sum%9==0?"Yes":"No");
	}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x, long y) {return Math.abs(x-y);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return max(a,b);
		return GCD(max(a,b),max(a,b)%min(a,b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}


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

int main() {
    int n;
    cin >> n;
    priority_queue<double> q;
    rep(i,n) {
        int v;
        cin >> v;
        q.push(-v);
    }
    rep(i,n-1) {
        double a = -q.top(); q.pop();
        double b = -q.top(); q.pop();
        q.push(-(a+b)/2.0);
    }
    printf("%.10f\n",-q.top());
    return 0;
}

Measured memory_bytes: 256
#EDP-E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())

dp = [defaultdict(int) for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(wb, dp[i].get(vb, wb))
        tmp = min(wb + w, dp[i].get(vb+ v, wb + w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    dp[i][v] = min(dp[i].get(v, w), w)

#print(dp[-1].items())
print(max(dp[-1].keys()))


Measured memory_bytes: 286344
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<max(0,min(b,d)-max(a,c))<<endl;
}

Measured memory_bytes: 256
(let ((L (read))
      (R (read))
      (arr (make-array 0 :element-type 'integer
                         :adjustable t
                         :fill-pointer 0))
      (ans 10000))
     (loop for i from L upto (min R (+ L 4040))
           do (vector-push-extend (rem i 2019) arr))
     (setf arr (sort arr #'<))
     (loop for i from 0 below (1- (min (1+ (- R L)) 4040))
           do (loop for j from (1+ i) below (min (1+ (- R L)) 4040) while (not (zerop ans))
                    do (setf ans (min ans (rem (* (aref arr i) (aref arr j)) 2019)))))
     (princ ans))

Measured memory_bytes: 16484
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int p = 1e9 + 7;

int get_sum(int n, int k) {
    return (n * (n + 1) / 2 - (n - k) * (n + 1 - k) / 2) % p;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, k;
    cin >> n >> k;
    int ans = 0;

    for (int i = k; i <= n + 1; i++) {
        ans += (get_sum(n + 1, i) - get_sum(i, i) + p + 1) % p;
        ans = (ans + p) % p;
    }
    cout << ans << '\n';

    return 0;
}

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

 int main() {
     int n,x;
     cin >> n >> x;
     int ans =0;
     vector <int> a(n);
        for(int i=0;i<n;i++){
            cin >> a.at(i);
             x-=a.at(i);
            ans++;
        }

    sort(a.begin(),a.end());
    while (x>0){
        if(a.at(0)<=x){
            x-=a.at(0);
            ans++;
        }
        else {
            break;
        }
    }
    cout << ans << endl;
     }


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

		String input_line = input.readLine();

		//?????????????????°
		String half_Ring=input_line;

		//??????????????????????????????????????¨????????????
		StringBuilder sb = new StringBuilder();

		//?????????????????????????????????
		sb.append(half_Ring);

		//??????
		sb.append(half_Ring);

		//?????????????????¨???????????????????????????????????????????????????
		String str = new String(sb);

		//????????????????????????????´¢???????????????
		String Word=input.readLine();

		//????´¢???????????????????????°Yes??????
		if(str.contains(Word)){

			System.out.println("Yes");

		}else{

			System.out.println("No");
		}
		
	}

}

Measured memory_bytes: 24352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//#define int long long


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


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

using namespace std;

string s;
vector<pair<char, char>> a;

char simulate(int x) {
  for (auto p : a) {
    if (s[x] == p.first) {
      if (p.second == 'L') x--;
      if (p.second == 'R') x++;
      if (x == -1) return 'L';
      if (x == s.size()) return 'R';
    }
  }
  return '0';
}

int main() {
  int n,q;
  cin >> n >> q;
  cin >> s;
  a.resize(q);
  for (auto& p : a) cin >> p.first >> p.second;
  int la = 0;
  int ra = n-1;
  int lb = 0;
  int rb = n-1;

  while (la < ra) {
    int m = (la + ra) / 2;
    char c = simulate(m);
    if (c == 'L') {
      la = m + 1;
    } else {
      ra = m;
    }
  }

  while (lb < rb) {
    int m = (lb + rb+1) / 2;
    char c = simulate(m);
    if (c == 'R') {
      rb = m-1;
    } else {
      lb = m;
    }
  }
  int ans;
  if (la >= lb) {
    if (simulate(la) == '0') {
      ans = 1;
    } else {
      ans = 0;
    }
  } else {
    ans = lb-la+1;
  }
  cerr << la << " " << ra << " " << lb << " " << rb << endl;
  cout << ans;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
const int N=300005;
char s[N];
int a[N],tot=0,ans;
int main(){
	int n; scanf("%d",&n);
	scanf("%s",s+1);
	for (int i=n;i>=1;i--) if (s[i]=='E') tot++;
	ans=n;
	for (int i=1;i<=n;i++){
		if (s[i]=='E') tot--;
		ans=min(ans,tot);
		if (s[i]=='W') tot++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int h[] = new int[n + 1];
        boolean m[] = new boolean[n + 1];
        
        for(int i = 0; i < n; i++){
            h[i] = sc.nextInt();
            m[i] = true;
        }
        
        int innCounter = 0;
        
        for(int idx = 0; idx < n; idx++){
                for(int k = 0; k < idx; k++){
                    if(h[idx] < h[k]){
                        m[idx] = false;
                    }else{
                        //処理なし
                    }
                }
                if(m[idx]){
                    innCounter++;
                }
        } 
        System.out.println(innCounter);
        
    }
}


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

int main()
{

    int x ,y , max_, min_;
    string str="" ;

    cin >>x>>y ;

    max_= max(x,y) ;
    min_= min(x,y) ;
    char c = min_+48;

    for (int i=0 ; i<max_ ; ++i)
    {
        str+=c ;
    }
    cout << str;
    return 0;
}


Measured memory_bytes: 256
/**
 *    author        : Sudipta Banik Trisha 
 *    created       : August 04, 2020 4:12 PM
 *    Problem Name  : A - Kyu in AtCoder
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_a
 *    @genarated by : ai-virtual-assistant
**/

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

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

    int n;
    cin >> n;

    if( n >= 400 && n <= 599) cout << "8" << endl;
    else if( n >= 600 && n <= 799) cout << "7" << endl;
    else if( n >= 800 && n <= 999) cout << "6" << endl;
    else if( n >= 1000 && n <= 1199) cout << "5" << endl;
    else if( n >= 1200 && n <= 1399) cout << "4" << endl;
    else if( n >= 1400 && n <= 1599) cout << "3" << endl;
    else if( n >= 1600 && n <= 1799) cout << "2" << endl;
    else cout << "1" << endl;

    return 0 ;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const double pi = 3.14159265358979;

double a, b, h, m;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> a >> b >> h >> m;
	double mnt = pi / 30 * m;
	double hr = pi / 6 * h + m / 60 * pi / 6;
	pair<double, double> p1(b * sin(mnt), b * cos(mnt)), p2(a * sin(hr), a * cos(hr));
	cout << fixed << setprecision(10) << sqrt((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second)) << "\n"; 
	return 0;
}

Measured memory_bytes: 4152
#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

int main(){
  	long n, s;
    cin >> n;
    cin >> s;
    
  	if ( n == s) {
       cout << n+1 << endl;
      return 0;
    }
    else{
      long b = 2;
      bool resFlag = false;
      long bSum;	
      long q, r;
      while (b <= (int)sqrt(n)){
        bSum = 0;
        q = n;
        r = 0;
        while (q > 0) {
          r = q % b;
          q = q / b;
          bSum += r;
          if (bSum > s) {
            break;
          }
        }
        if (bSum == s) {
            resFlag = true;
            break;
        }
        b++;
      }
      
      if(!resFlag) {
        long p = (int)sqrt(n);
        while (p >= 1){
          if ((n-s) % p == 0){
            b = (n-s)/p + 1;
            if (b >= 2){
              bSum = 0;
              q = n;
              r = 0;
              while (q > 0) {
                r = q % b;
                q = q / b;
                bSum += r;
                if (bSum > s) {
                  break;
                }
              }
              if (bSum == s) {
                resFlag = true;
                break;
              }
            }
          }
          p--;
        }
      }

      long res = resFlag ? b : -1;
      cout << res << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i,n) for(int i = 0;  i < n ; ++i)
#define REP(i,a,b) for(int i = a ; i <= b ; ++i)
#define filei freopen("input.txt", "r", stdin);
#define fileo freopen("output.txt", "w", stdout);
#define gooi cout<<"Case #"<<i+1<<" :";
#define s(n) scanf("%d",&n)
#define rev(i,n) for(int i = n ; i >= 0 ; --i)
#define REV(i,a,b) for(int i = a ; i >= b ; --i)
#define miN(a,b) (((a)<(b))?(a):(b))
#define sc(n) scanf("%c",&n)
#define tr(c,i) for(typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define INF 1000000000
#define pii pair<long long int,long long int>
#define pb(a) push_back(a)
#define F first
#define S second
typedef long long ll;
using namespace std;
void pre(){}
void solve(){
    ll a,b,v,w,t;cin>>a>>v>>b>>w>>t;
    if( abs(a-b)>t*(v-w) ){
        cout<<"NO"<<"\n";
    }else{
        cout<<"YES"<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}





Measured memory_bytes: 3636
#include<cstdio>
using namespace std;

int N;
int h[111111];
int memo[111111];

int abs(int a){
	if(a < 0) return -a;
	else return a;
}

int min(int a, int b){
	if(a < b) return a;
	else return b;
}

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d", &h[i]);

	for(int i = 0; i < N; i++){
		if(i == 0) continue;
		else if(i == 1) memo[i] = abs(h[i] - h[i - 1]);
		else memo[i] = min(abs(h[i] - h[i - 1]) + memo[i - 1], abs(h[i] - h[i - 2]) + memo[i - 2]);
	}
	printf("%d\n", memo[N - 1]);
	return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
	int N = Integer.parseInt(scan.next());

	int[] count = new int[9];
	
	for (int i = 0; i < N; i++) {
	    int a = Integer.parseInt(scan.next());
	    int rate = a / 400;
	    rate = (rate > 8 ? 8 : rate);

	    count[rate]++;
	}

	int min = 0;
	for (int i = 0; i < 8; i++) {
	    if(count[i] > 0) min++;
	}
	int max = min + count[8];
	if(min == 0) min = 1;
	
	System.out.println(min + " " + max);
	scan.close();
    }
}


Measured memory_bytes: 21972
#include <iostream>

using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if (a==1) a+=13;
    if (b==1) b+=13;
    if(a>b){
        cout<<"Alice"<<endl;
    }else if(a==b){
        cout<<"Draw"<<endl;
    }else{
        cout<<"Bob"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define nl '\n'
// ROAD to...                                                                                                                                                                                                                Red

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;

int main () {
	SpeedForce;
	setIO();
	cin >> n;
	For (i, 1, n) {
	    int x;
	    cin >> x;
	    if(i&1 && x&1) ++ans;
	}
	cout << ans << nl;

	return Accepted;
}

// B...a

Measured memory_bytes: 17700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll q, h, s, d;
    ll n;
    cin >> q >> h >> s >> d;
    cin >> n;

    q = q * 8;
    h = h * 4;
    s = s * 2;

    ll sum = n / 2 * min(min(q, h), min(s, d));
    if(n % 2 == 1){
        sum += min(min(s / 2, h / 2), q / 2);
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

max_Li = -1
min_Ri = 10000000
for i in range(M):
    L_i, R_i = map(int, input().split())
    max_Li = max(max_Li, L_i)
    min_Ri = min(min_Ri, R_i)


print(max(0, min_Ri - max_Li + 1))


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

struct node{
    int key;
    struct node *left,*right,*par;
};
typedef struct node* node_pointer; 

node_pointer nil,root;

void insert(int);
void Preorder(node_pointer);
void Inorder(node_pointer);
int  search(int); //要素が見つかったら1を、見つからなかったら0を返す関数

int main(){
    int n,i;
    scanf("%d",&n);

    for(i=0; i<n; i++){
        char order[7];
        int num;
        scanf(" %s",order);

        if(strcmp(order,"insert") == 0 ){
            scanf("%d",&num);
            insert(num);
        }

        else if(strcmp(order,"find") == 0){
            scanf("%d",&num);
            if(search(num)) printf("yes\n");
            else printf("no\n");
        }

        else if(strcmp(order,"print") == 0){
            Inorder(root);
            printf("\n");
            Preorder(root);
            printf("\n");
        }
    }

    return 0;
}

void insert(int num){
    node_pointer a,b,c;
    a = root;
    b = nil;
    c = (node_pointer)malloc(sizeof(struct node));
    c->key = num;
    c->right = nil;
    c->left = nil;

    while(a != nil){
        b = a;       
        if(c->key < a->key) a = a->left;
        else a = a->right;
    }

    c->par = b;

    
    if(b == nil) root = c;
    else if(c->key < b->key) b->left = c;
    else b->right = c;
}

void Preorder(node_pointer a){
    if(a == nil) return;
    printf(" %d",a->key);
    if(a->left != nil) Preorder(a->left);
    if(a->right != nil) Preorder(a->right);
}

void Inorder(node_pointer a){
    if(a == nil) return;
    if(a->left != nil) Inorder(a->left);
    printf(" %d",a->key);
    if(a->right != nil) Inorder(a->right);
}

int search(int num){
    node_pointer a;
    a = root;

    while(1){
        if(a == nil) break;
        if(a->key == num) return 1;
        if(num < a->key) a = a->left;
        else if(num >= a->key) a = a->right;
    }

    return 0;
}


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

using namespace std;
vector < int > v , temp , temp2;

int main()
{
    int n;  cin >> n;
    v.resize(n);
    temp.resize(n);
    temp2.resize(n);
    for(int i = 0;i<n;i++)  cin >> temp[i];
    for(int i = 0;i<n;i++)  cin >> temp2[i];
    for(int i = 0; i<n;i++)  v[i] = i + 1;
    int a , b;  a = b = 0;
    int i = 1;
    do{
        if(temp == v)   a = i;
        if(temp2 == v)  b = i;
        i++;

    }while(next_permutation(v.begin() , v.end()));
    cout << abs(a - b);
    return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
mod=10**9+7
Fact=[0 for i in range(M+1)]
Finv=[0 for i in range(M+1)]
Fact[0]=1
def inv(x):
    return pow(x,mod-2,mod)
for i in range(M):
    Fact[i+1]=Fact[i]*(i+1)
    Fact[i+1]%=mod
Finv[M]=inv(Fact[M])
for i in range(M-1,-1,-1):
    Finv[i]=(i+1)*Finv[i+1]
    Finv[i]%=mod
def P(n,k):
    return (Fact[n]*Finv[n-k])%mod
def C(n,k):
    return (Fact[n]*Finv[n-k]*Finv[k])%mod
ans=0
for k in range(N+1):
    if k%2==0:
        ans+=C(N,k)*P(M-k,N-k)
    else:
        ans-=C(N,k)*P(M-k,N-k)
    ans%=mod
print((ans*P(M,N))%mod)


Measured memory_bytes: 48524
S = input()
l = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(l+1)]
dp[0][0] = 1

for i,s in enumerate(S):
    for j in range(13):
        if(s=="?"):
            for k in range(10):
                dp[i+1][((j*10)+k)%13] += dp[i][j]
                dp[i+1][((j*10)+k)%13]%=mod
        else:
            dp[i+1][((j*10)+int(s))%13] += dp[i][j]
            dp[i+1][((j*10)+int(s))%13]%=mod
print(dp[l][5])

Measured memory_bytes: 61916
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}



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




int main() {

	ll A, B;
	cin >> A >> B;

	ll h = 100;
	ll w = 100;

	char grid[101][101];

	repn(i, 100)repn(j, 50) {
		grid[i][j] = '#';
		grid[i][j+50] = '.';
	}
	
	ll I = 2;
	ll J = 2;
	repn(i,A-1){
		grid[I][J] = '.';
		I += 2;
		if (I == 100) { I = 2; J += 2; }
	}
	
	I = 2;
	J = 52;
	repn(i, B - 1) {
		grid[I][J] = '#';
		I += 2;
		if (I == 100) { I = 2; J += 2; }
	}
	
	cout << h << " " << w << endl;
	repn(i, 100) {
		repn(j, 100) {
			cout << grid[i][j];
		}
		cout << endl;
	}
	system("PAUSE");

}


Measured memory_bytes: 504
import Control.Monad

main::IO()
main=do
    n <- readLn::IO Int
    [d,x] <- map read . words <$> getLine
    as <- replicateM n $ read <$> getLine ::IO [Int] 
    print $ x + n +  (solve d as)

solve::Int-> [Int] -> Int
solve  d as = sum $ map (\x -> (d - 1) `div` x) as


Measured memory_bytes: 1020
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint zyo[20];
lint inf=123456789012345678LL;
lint cal(lint d,int x){
	if(d%9>0) return 0LL;d/=9;
	vector<lint> v;
	rep(i,x/2) v.pb((zyo[x-i-1]-zyo[i])/9);
	lint ret=1;
	//cout<<d<<endl;
	//cout<<v[0]<<' '<<d<<endl;
	rep(i,v.size()){
		lint mi=inf;int mij=0;
		REP(j,-9,10){
			lint now=d-j*v[i];
			if(now%zyo[i+1]!=0LL) continue;
			if(abs(now)<abs(mi)) mij=j,mi=now;
		}
		if(abs(mi)>=inf) return 0LL;
		if(i==v.size()-1 && mi!=0LL) return 0LL;
		//cout<<x<<' '<<mi<<' '<<mij<<endl;
		if(i==0) ret*=9-abs(mij);
		else ret*=10-abs(mij);
		d=mi;
	}
	//cout<<x<<endl;
	if(x%2>0) ret*=10;
	return ret;
}
int main()
{
	lint d,out=0;
	cin>>d;
	zyo[0]=1;rep(i,19) zyo[i+1]=zyo[i]*10;
	//out+=cal(d,9);
	REP(i,2,19) out+=cal(d,i);
	cout<<out<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = (a); i < (n); i++)
#define repr(i, n, a) for (int i = (n)-1; i >= (a); i--)
#define repit(it, v) for (auto(it) = (v).begin(); (it) != (v).end(); (it)++)
#define sortt(v) sort((v).begin(), (v).end())
#define sortr(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define co(x) cout << (x)
#define con(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define mkp make_pair
#define mkt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
// inline void fastio() { ios::sync_with_stdio(false), cin.tie(0); }
/******* Variable ************************************/
const int maxn = 1e6 * 50;
const int inf = 1e9 + 7;
const double pi = 3.141592653589;
/******* Function ************************************/
/******* Main ****************************************/
void Main() {
  int n;
  while (cin >> n) {
    if (n == 0) break;
    vi vec(n);
    double sum = 0;
    rep(i, 0, n) {
      cin >> vec[i];
      sum += vec[i];
    }
    double avg = sum / n;
    double total_div = 0;
    for (int v : vec) total_div += (v - avg) * (v - avg);
    cout << sqrt(total_div / n) << '\n';
  }
}

/******************************************************
  Smaile!
▕▔╲┊┊┊┊┊┊┊┊┊╱▔▏
┊╲┈╲╱▔▔▔▔▔╲╱┈╱┊
┊┊╲┈╭╮┈┈┈╭╮┈╱┊┊
┊┊╱┈╰╯┈▂┈╰╯┈╲┊┊
┊┊▏╭╮▕━┻━▏╭╮▕┊┊
┊┊╲╰╯┈╲▂╱┈╰╯╱
                    How`s it going?
                            |＼
                    　／￣＼　ヽ
                    ／　　　ヽ |_
                    ￣＼　　　　 ＼
                    ／￣　/|/| /ﾚ､ ヽ＿
                    ￣＼ Yヘ |/ヘ幺　∠
                    　＜_|(･> <･) 6) ／
                      　　 (ﾞ　_　ﾞ／＜
                      　　　＞､ーイ￣￣
                    　　／厂ヽ／￣/＼
                    　 ( ｜　(亀)(>　)▏

                            Take a rest before getting tired!
                                        　　 ●
                                        　　/⌒ヽ
                                        　 ｜ 　|/⌒ヽ(ヽ
                                        　 (｀　∥ー⌒) |
                                        　|￣||￣￣￣￣￣|
                                        　|―||―――――|
                                        　|　Ｕ　　　　　|
                                        　|￣￣￣￣￣￣￣|
                                        　|＿＿＿＿＿＿＿|
                                        　　|―――――|
                                        　　|―――――|
                                        ｗｗＷｗｗＷｗＷＷｗ

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


Measured memory_bytes: 3216
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include<map>
using namespace std;
#define REP(a,b) for(int a = 0;a < b;++a)
int dp[1001][1001] = {};
int main() {
	REP(i, 1001) {
		REP(j, 1001) {
			dp[i][j] = 9999999999;
		}
	}
	int n,m;
	scanf("%d%d", &n,&m);
	int distance[1001] = {};
	for (int i = 1;i <= n;++i) scanf("%d", &distance[i]);
	int cloud[1001] = {};
	for (int i = 1;i <= m;++i) scanf("%d", &cloud[i]);
	for (int i = 1;i <= m;++i) dp[1][i] = min(dp[1][i - 1], distance[1] * cloud[i]);
	for (int i = 2;i <= n;++i) {
		for (int j = i;j <= m;++j) {
			dp[i][j] = min(dp[i - 1][j - 1] + (distance[i] * cloud[j]), dp[i][j-1]);
		}
	}
	printf("%d\n", dp[n][m]);
}


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;
typedef vector<int> vi;

void solve(){
	
	int n, x, y; cin >> n >> x >> y;
	for(int i = x; i <= y; ++i){
		if(i%n == 0){
			cout << "OK\n";
			return;
		}
	}
	cout << "NG\n";
	
	return;
}

int main(){
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	solve();
	
	return 0;
}


Measured memory_bytes: 3612
import java.math.BigDecimal;
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 cnt = 0;

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

			BigDecimal e = new BigDecimal(c).multiply(new BigDecimal(c)).add(new BigDecimal(d).multiply(new BigDecimal(d)));
			BigDecimal f = new BigDecimal(b).multiply(new BigDecimal(b));

			if (e.compareTo(f) <= 0) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 60732
import java.io.*;
import java.util.*;

public class Main{
    static MyReader in = new MyReader();
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args){
        int[] a = in.ii();
        int b = a[0] < 10 && a[1] < 10 ? a[0]*a[1] : -1;
        out.println(b);
        out.flush();
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


Measured memory_bytes: 22612
w = STDIN.gets.chomp()
text = []
while true
    line = STDIN.gets.chomp()
    if line == "END_OF_TEXT" then
        break
    else
        line = line.downcase
        text << line
    end
end

# puts w
# puts text

count = 0
for i in 0..text.length - 1 do
    line = text[i]
    # puts line
    words = line.split(" ")
    # puts words
    for j in 0..words.length - 1 do
        if words[j] == w then
            count += 1
        end
    end
end

puts count

Measured memory_bytes: 6096
K = int(input())

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            total += gcd(gcd(a,b),c)

            
print(total)


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

long long f(long long N, long long gA, long long sA, long long bA, long long gB, long long sB, long long bB)
{
    vector<bool> need_search({gA < gB, sA < sB, bA < bB});

    long long ans = 0;
    long long g, s, b, score;
    if (N <= 5000)
    {
        for (g = 0; g <= (need_search[0] ? N : 0); g += gA)
        {
            for (s = 0; g + s <= (need_search[1] ? N : g); s += sA)
            {
                if (need_search[2])
                {
                    b = ((N - g - s) / bA) * bA;
                }
                else
                {
                    b = 0;
                }
                score = gB * (g / gA) + sB * (s / sA) + bB * (b / bA);
                score += N - g - s - b;
                ans = max(ans, score);
            }
        }
    }
    else
    {
        if (!need_search[0])
        {
            g = 0;
            for (s = 0; s <= (need_search[1] ? N : 0); s += sA)
            {
                if (need_search[2])
                {
                    b = ((N - s) / bA) * bA;
                }
                else
                {
                    b = 0;
                }
                score = gB * (g / gA) + sB * (s / sA) + bB * (b / bA);
                score += N - g - s - b;
                ans = max(ans, score);
            }
        }
        else if (!need_search[1])
        {
            s = 0;
            for (b = 0; b <= (need_search[2] ? N : 0); b += bA)
            {
                if (need_search[0])
                {
                    g = ((N - b) / gA) * gA;
                }
                else
                {
                    g = 0;
                }
                score = gB * (g / gA) + sB * (s / sA) + bB * (b / bA);
                score += N - g - s - b;
                ans = max(ans, score);
            }
        }
        else
        {
            b = 0;
            for (g = 0; g <= (need_search[0] ? N : 0); g += gA)
            {
                if (need_search[1])
                {
                    s = ((N - g) / sA) * sA;
                }
                else
                {
                    s = 0;
                }
                score = gB * (g / gA) + sB * (s / sA) + bB * (b / bA);
                score += N - g - s - b;
                ans = max(ans, score);
            }
        }
    }
    return ans;
}

int main()
{
    long long N, gA, sA, bA, gB, sB, bB;
    cin >> N >> gA >> sA >> bA >> gB >> sB >> bB;

    long long ans = f(N, gA, sA, bA, gB, sB, bB);

    ans = f(ans, gB, sB, bB, gA, sA, bA);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>

int main(){
  int a,b,c,d;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  c = a*b;
  d = 2*(a+b);
  printf("%d %d\n" , c,d);
  
  return 0;
 }


Measured memory_bytes: 2684
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;
using Graph = vector<vector<int>>;



int main(){
    int N,M;cin>>N>>M;
    Graph G(N);
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a!=0&&b!=0){
            G[a].push_back(b);
            G[b].push_back(a);
        }else if(a==0){
            G[a].push_back(b);
        }else{
            G[b].push_back(a);
        }
    }
    vector<int> mark(N);
    vector<int> dist(N,-1);
    queue<int> que;
    dist[0] = 0;
    que.push(0);
    
    while(!que.empty()){
        int v = que.front();
        que.pop();

        for(int next_v:G[v]){
            if(dist[next_v] != -1) continue;
            mark[next_v] = v + 1;
            dist[next_v] = dist[v] + 1;
            que.push(next_v);
        }
    }
    cout << "Yes" << endl;
    for(int i=1;i<N;i++){
        cout << mark[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 10552
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

N = z()
A = zz()
# A = sorted(A)
tmp =gcd(A[0], A[1])
for a in A[1:]:
    tmp = gcd(tmp, a)
ans = tmp
# for i in range(N):
#     for j in range(0, i):        
#         tmp = A[i] % A[j]
#         tmp = min(tmp, A[j]-tmp)
#         if (tmp != 0):
#             ans = min(ans, tmp)
print(ans)
            


Measured memory_bytes: 37876
#include<iostream>
#include<stdio.h>

int main() {
	int i;
	int n, m, x, y;
	int X[200], Y[200];
	int xmax = -100, ymin = 100;

	scanf("%d%d%d%d", &n, &m, &x, &y);

	for (i = 0; i < n; i++) {
		scanf("%d", &X[i]);
		if (X[i] > xmax) {
			xmax = X[i];
		}
	}

	for (i = 0; i < m; i++) {
		scanf("%d", &Y[i]);
		if (Y[i] < ymin) {
			ymin = Y[i];
		}
	}

	if (x < y && x < ymin && xmax < y && xmax < ymin) {
		printf("No War\n");
	}
	else {
		printf("War\n");
	}

	

	return 0;
}

Measured memory_bytes: 256
import collections
N,K = map(int,input().split())
A = [int(i) for i in input().split()]

List = collections.Counter(A)

cnt = list(List.values())
cnt.sort()

ans = 0
L = len(cnt)
for i in range(L):
    if L-i>K:
        ans += cnt[i]
    else:
        break
print(ans)

Measured memory_bytes: 32508
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  vector<long long> P(N),C(N);
  for(int i = 0;i < N;i++) {
    cin >> P[i];
    P[i]--;
  }
  for(int i = 0;i < N;i++) cin >> C[i];

  long long ans = -LONG_MAX;


  for(int i = 0;i < N;i++) {

    int cycle_num = 0;
    long long cycle_sum = 0;
    int idx = i;

    while(1) {
      cycle_num++;
      cycle_sum += C[idx];
      idx = P[idx];
      
      if(idx == i) break;
    }

    long long path = 0,cnt = 0;
    while(1) {
      cnt++;
      path += C[idx];

      if(cnt > K) break;

      int num = (K-cnt) / cycle_num;
      long long cost = path + max(0LL,cycle_sum)*num;
      ans = max(ans,cost);

      idx = P[idx];
      if(idx == i) break;

    }

  }

  cout << ans << endl;



}


Measured memory_bytes: 3736
N, K = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

mi = 1e10
for l in range(N - K + 1):
    r = l + K - 1
    mi = min(mi, abs(X[l]) + abs(X[r] - X[l]), abs(X[r]) + abs(X[r] - X[l]))
print(mi)

Measured memory_bytes: 14224
import java.util.Scanner;



public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());
		int sum = 0;
		for(int i = 0; i < k; i++) {
			if(a > 0) {
				sum += 1;
				a -= 1;
			}else if(b > 0) {
				b -= 1;
			}else if(c > 0){
				sum -= 1;
				c -= 1;
			}
		}
		System.out.println(sum);

	}
}


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

using namespace std;

typedef vector<int> vi;
typedef long long ll;

#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int vmax=100010;
vi graph[vmax];
int color[vmax];
ll black=0LL,white=0LL;

bool dfs(int v,int c){
	color[v]=c;
	if(c==1) black++;
	if(c==-1) white++;
	for(auto &v2:graph[v]){
		if(color[v2]==0&&dfs(v2,-c)==false) return false;
		if(color[v2]==color[v]) return false;
	}
	return true;
}

ll base=0LL;
ll num[100010];
ll dp[100010];

ll calc(ll v){
	clr(dp,-1);
	dp[0]=0LL;

	rep(i,v+1){
		if(num[i]==0) continue;
		rep(j,v+1){
			if(dp[j]>=0)
				dp[j]=num[i];
			else if(j<i || dp[j-i]<=0)
				dp[j]=-1;
			else
				dp[j]=dp[j-i]-1;
		}
	}
	ll all=0LL;
	rep(i,v+1){
		if(dp[i]>=0){
			ll white=base+i;
			ll black=v-white;
			all=max(all,white*black);
		}
	}
	return all;
}

int main(void){
	ll v,e;
	cin >> v >> e;
	rep(i,e){
		int a,b;
		cin >> a >> b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}

	bool ok=true;;
	rep(i,v){
		if(color[i]!=0) continue;
		int c=1;
		if(dfs(i,c)==false) ok=false;
		base+=min(black,white);
		num[max(black,white)-min(black,white)]++;
		black=0,white=0;
	}

	// ?????°??¶???????????¨????????????????§£???
	ll all=calc(v);
	if(ok)
		cout << all-e << endl;
	else
		cout << -1 << endl;
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
const ll mod = 1e9+7;
const ll inf = 1e17;
const int INF = 1e9;
const double PI = acos(-1);
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  int n;
  cin >> n;
  vi p(n);
  re(i, n) cin >> p[i];

  int cnt = 0;
  re(i, n-2) {
    if((p[i] < p[i+1] && p[i+1] < p[i+2]) || (p[i] > p[i+1] && p[i+1] > p[i+2])) {
        cnt++;
      }
  }
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
ll n,m,k,ans;
string s,t;
const ll powll = 1LL<<1;

bool cmp(P a, P b){
  return a.first+a.second < b.first+ b.second;
}

int main(void){
  int n; cin >> n;
  int a[n];
  rep(i,n) cin >> a[i];

  int ans = 0; int pj = a[0];
  
  rep(i,n){
    if(a[i] <= pj) ans++;
    pj = min(pj, a[i]);
  }

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

Measured memory_bytes: 1024
#include<stdio.h> 
#define MAX 100001
 
typedef struct Card{
  char mark;
  int num;
  int index;
}c;
 
int n;
 
int Partition(c A[],int p,int r){
  c t,u;
  int i,j,s;
  s=A[r].num;
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(A[j].num<=s){
      i++;
      t=A[i];        /*Exchange A[i] and A[j]*/
      A[i]=A[j];
      A[j]=t;
    }
  }
  u=A[i+1];          /*Exchange A[i+1] and A[r]*/
  A[i+1]=A[r];
  A[r]=u;
  return i+1;
}
 
void QuickSort(c Q[],int p,int r){
  int q;
  if(p<r){
    q=Partition(Q,p,r);
    QuickSort(Q,p,q-1);
    QuickSort(Q,q+1,r);
  }
}
 
int JudgeStability(c K[],int n){
  int i;
  for(i=1;i<n;i++){
    if((K[i-1].num==K[i].num) && (K[i-1].index>K[i].index)){
      return 0; /*Not Stable*/
    } 
  }
  return 1;
}
 
int main(){
  int i;
  c P[MAX];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c %d",&P[i].mark,&P[i].num);
    P[i].index = i;
  }
 
  QuickSort(P,0,n-1);
  if(JudgeStability(P,n)==1) printf("Stable\n");
  else if(JudgeStability(P,n)==0) printf("Not stable\n");
  for(i=0;i<n;i++){
    printf("%c %d\n",P[i].mark,P[i].num);
  }
  return 0;
}

Measured memory_bytes: 1776
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{int to, index;};
static const int MAX_V = 100000;
static const int MAX_E = 100000;

int V, E;
vector<edge> G[MAX_V];
bool visited[MAX_V], passed[MAX_E];
int ord[MAX_V], low[MAX_V];

void dfs(int u, int k){
	visited[u] = true;
	ord[u] = k;
	k++;
	low[u] = ord[u];
	for(int i = 0; i < G[u].size(); i++){
		if(!visited[G[u][i].to]){
			passed[G[u][i].index] = true;
			dfs(G[u][i].to, k);
			low[u] = min(low[u], low[G[u][i].to]);
		}else if(!passed[G[u][i].index]){
			low[u] = min(low[u], ord[G[u][i].to]);
		}
	}
}

int main(){
	scanf("%d %d", &V, &E);
	for(int i = 0; i < E; i++){
		int s, t;
		scanf("%d %d", &s, &t);
		G[s].push_back((edge){t, i});
		G[t].push_back((edge){s, i});
	}
	fill(visited, visited + V, false);
	fill(passed, passed + E, false);
	dfs(0, 0);
	vector<pair<int, int> > res;
	for(int i = 0; i < V; i++){
		for(int j = 0; j < G[i].size(); j++){
			if(!passed[G[i][j].index]) continue;
			if(ord[G[i][j].to] < ord[i]) continue;
			if(ord[i] < low[G[i][j].to]){
				res.push_back(make_pair(min(i, G[i][j].to), max(i, G[i][j].to)));
			}
		}
	}
	sort(res.begin(), res.end());
	for(int i = 0; i < res.size(); i++) printf("%d %d\n", res[i].first, res[i].second);
	return 0;
}



Measured memory_bytes: 6820
sub p{my($a,$b)=@_;$b?p($a**2%$=,$b>>1)*($b%2?$a:1)%$=:1}@s=map$%=($%+p$_,($==1e9+7)-2)%$=,1..<>;$\+=$_*($s[$i++]+$s[-$i]-1)%$=for glob<>;map$\=$\*++$j%$=,@s;print

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 10;
int N;
string ans;

void solve(int pos = 0, int k = 1) {
  if (pos == N) {
    cout << ans << endl;
    return;
  }

  REP(i,k) {
    ans += 'a' + i;
    if(i == k-1) {
      solve(pos+1, k+1);
    } else {
      solve(pos+1, k);
    }
    ans.pop_back();
  }
}

signed main()
{
  cin >> N;
  solve();
  return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { if (i) os << " "; os << v[i]; } return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a - mod; }

void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
      solve();
    }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  ll ans = INF;
  // 連続区間全部試す
  // 近い方行って, 反対行く
  rep(l, n - m + 1) {
    chmin(ans, min(abs(a[l + m - 1]), abs(a[l])) + a[l + m - 1] - a[l]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640