akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? 1e9:1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){int b=0;for(auto itr :a){if(b++!=0)cout << " "; cout << itr;} }
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    vector<int>csum;
    int cnt = 1;
    for(;;){
        if(csum.size()&&csum.back()  > 1000000)break;
        csum.push_back(cnt*(cnt+1)*(cnt+2)/6);
        cnt ++;
    }
    csum.pop_back();
    int dp1[1000000+1];
    int dp2[1000000+1];
    rep(i,1000000+1)dp1[i] = dp2[i] = INF;
    dp1[0] = dp2[0] = 0;
    rep(i,1000000+1){
        if(dp1[i] == INF)continue;
        rep(j,csum.size()){
            if(i + csum[j] > 1000000 || csum[j]%2==0)continue;
            cmin(dp1[i+csum[j]],dp1[i]+1);
        }
    }
    rep(i,1000000+1){
        if(dp2[i] == INF)continue;
        rep(j,csum.size()){
            if(i + csum[j] > 1000000)continue;
            cmin(dp2[i+csum[j]],dp2[i]+1);
        }
    }
    int n;
    while(cin >> n,n){
        cout << dp2[n] << " " << dp1[n] << endl;
        
    }
}




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

int powInt(int a, int b) {
    int ans = 1;
    for (int i = 0; i < b; ++i) {
        ans *= a;
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    int ans = powInt(10, n - 1);
    if (n == 1) ans = 0;
    vector<pair<int, char>> constraint(m);
    for (int i = 0; i < m; ++i) {
        cin >> constraint[i].first >> constraint[i].second;
    }
    bool flag;
    for (int j = ans; j < powInt(10, n); ++j) {
        string s = to_string(j);
        flag = true;
        for (pair<int, char> k : constraint) {
            if (s[k.first - 1] != k.second) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << j << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}


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

int main(){
  int N;
  cin >> N;
  
  vector<bool> flag(N);
  for(int i = 0;i < N;i++){
    int d, e;
    cin >> d >> e;
    
    if(d == e) flag.at(i) = true;
  }
  
  for(int i = 2;i < N;i++){
    if(flag.at(i-2) && flag.at(i-1) && flag.at(i)){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  
  return 0;
}

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

public class Main {

    public static void main(String[] argv) throws IOException {
        //*
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            String s = in.readLine();
            if (s == null) {
                break;
            }
            f(s);
        }
        //*/
    }

    public static void f(String s) {
        String[] sp = s.split(" ");
        String ans = String.valueOf(Integer.parseInt(sp[0]) + Integer.parseInt(sp[1]));
        System.out.println(ans.length());
    }
}

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

int main() {
  int n;
  cin>>n;
  if(n<2) cout<<1<<endl;
  else if(n<4) cout<<2<<endl;
  else if(n<8) cout<<4<<endl;
  else if(n<16) cout<<8<<endl;
  else if(n<32) cout<<16<<endl;
  else if(n<64) cout<<32<<endl;
  else cout<<64<<endl;
}


Measured memory_bytes: 256
// Aizu Vol-10 1035: Sleeping Cats
// 2017.8.20 bal4u@uu

#include <stdio.h>
#include <string.h>

#define HASHSIZ 199
typedef struct { int id, k; } HASH;
HASH hash[HASHSIZ + 5], *hashend = hash + HASHSIZ;

int insert(int id, int k)
{
	HASH *p = hash + id % HASHSIZ;
	while (p->id) {
		if (p->id == id) return p->k;
		if (++p == hashend) p = hash;
	}
	p->id = id, p->k = k;
	return k;
}

char wall[103]; int W;
typedef struct { int id, s, e; } T; 
T cat[103]; int used;

int place(int w)
{
	int i, j;

	for (i = 0; i < W; i++) {
		if (!wall[i]) {
			for (j = 0; i+j < W && j < w && !wall[i+j]; j++);
			if (j >= w) return i;
		}
	}
	return -1;
}

int main()
{
	int Q, id, w;
	int i, j, k, s;
	char a[10];

	while (scanf("%d%d", &W, &Q) && (W||Q)) {
		memset(hash, 0, sizeof(hash));
		memset(wall, 0, sizeof(wall));
		used = 0;
		for (i = 0; i < Q; i++) {
			scanf("%s", a);
			if (a[0] == 's') {
				scanf("%d%d", &id, &w);
				if ((s = place(w)) < 0) { puts("impossible"); continue; }
				k = insert(id, used);
				if (k == used) used++;
				cat[k].id = id, cat[k].s = s, cat[k].e = s+w;
				for (j = s; j < s+w; j++) wall[j] = 1;
				printf("%d\n", s);
			} else {
				scanf("%d", &id);
				k = insert(id, 0);
				for (j = cat[k].s; j < cat[k].e; j++) wall[j] = 0;
			}
		}
		puts("END");
	}
	return 0;
}

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

ll N, K, X;
vector<int> u, v;

ll rec(ll n, ll x)
{
    if (n == 0)
        return (x <= 0 ? 0 : 1);
    ll p = (1LL << n) - 1;
    if (x <= 2 * p)
        return rec(n - 1, x - 1);
    return p + 1 + rec(n - 1, x - 2 * p - 1);
}

int main()
{
    cin >> N >> X;
    cout << rec(N, X) << endl;
}

Measured memory_bytes: 256
///   ***   ---   |||         In the name of ALLAH        |||   ---   ***   ///



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


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

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

const int mx = 2e5+123;
ll a[mx];


int main()
{
    optimize();

    vl v;

    int n;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        v.PB ( a[i] );
    }


    sort ( all ( v ) );

    ll ans = v.back();
    v.pop_back();

    int cnt = 2;
    while ( cnt < n ) {
        //dbg(cnt, v.back());
        ans += ( v.back() );
        ll d = v.back();
        v.pop_back();
        cnt++;
        if ( cnt == n ) continue;

     //   dbg(cnt, d);
        cnt++;
        ans += ( d );


    }

    cout << ans << endl;


    return 0;
}


















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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<int,int>;

const int MOD = 1e9 + 7;

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

    int h, w;
    cin >> h >> w;

    if(h % 2 == 1 && w % 2 == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
def gcd(x,y):
    if x<y:x,y =y,x
    if y==0: return x
    return gcd(y,x%y)
N = int(input())
A = list(map(int,input().split()))
L = [0]
R = [0]
M = []
for i in range(N):
    L.append(gcd(L[i],A[i]))
    R.append(gcd(R[i],A[N-i-1]))
R.reverse()
print(max([gcd(L[i],R[i+1])for i in range(N)]))

Measured memory_bytes: 14584
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define mod 1000000007

int main() {
	long long int n, p;
	string s;
	cin >> n >> p >> s;
	if (p == 2 || p == 5) {
		long long int ans = 0;
		for (int i = 0; i < n; i++) {
			if ((s[i] - '0') % p == 0) {
				ans += i + 1;
			}
		}
		cout << ans << endl;
		return 0;
	}
	map<long long int, long long int> cnt;
	long long int now = 0;
	long long int modpow10[200001];
	modpow10[0] = 1;
	for (int i = 1; i <= n; i++) {
		modpow10[i] = (modpow10[i - 1] * 10) % p;
	}
	long long int ans = 0;
	cnt[0] = 1;
	for (int i = n - 1; i >= 0; i--) {
		now = (now + (s[i] - '0') * modpow10[n - i - 1]) % p;
		if (cnt.find(now) != cnt.end()) {
			ans += cnt[now];
			cnt[now]++;
		} else {
			cnt[now] = 1;
		}
		// cout << i << " " << now << " " << ans << endl;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2564
#include <iostream>
#include <cstring>
#include <set>
#pragma GCC optimize("O2")
#define all(c) c.begin(), c.end()
#define pb push_back
#define ll long long
const int MAXN = 1e2 + 5;
const int mod = 1e9 + 7;

using namespace std;

ll dp[4][4][4][4][MAXN];
string s = "ACGT";
set<string> imp = {"AGTC","ATGC","TAGC","AGCT", "ACGT", "TACG", "GACT","TGAC"};

ll rec(int n, char a, char g, char c, char t) {
	string m = ""; m+=a;m+=g;m+=c;m+=t;
	if (imp.find(m) != imp.end()) return 0;
	if (n == 0) return 1;
	if (a == '#')
		return ((rec(n-1,g,c,t,'A')+rec(n-1,g,c,t,'C'))%mod+(rec(n-1,g,c,t,'G')+rec(n-1,g,c,t,'T'))%mod)%mod;
	int i = s.find(a), j = s.find(g), k = s.find(c), l = s.find(t);
	auto &ret = dp[i][j][k][l][n];
	if (ret != -1) return ret;
	return ret = ((rec(n-1,g,c,t,'A')+rec(n-1,g,c,t,'C'))%mod+(rec(n-1,g,c,t,'G')+rec(n-1,g,c,t,'T'))%mod)%mod;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int ans[4] = {0,4,16,61};
  memset(dp,-1,sizeof dp);
  for (string k : imp) {
  	int id = k.find('T');
  	if (id == string::npos) continue;
  	for (int i = 0; i < 3; i++) {
  		k[id] = s[i];
  		imp.insert(k);
  	}
  }
  if (n <= 3) cout << ans[n];
  else cout << rec(n,'#','#','#','#');
  return 0;
}

Measured memory_bytes: 512
/*input
8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8
*/

// Nihesh Anderson - knandy

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

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
ll MOD=1000000000000000007;

#define endl '\n'
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
ll INF = 2000000000000000001;
long double EPS = 1e-9;
ll power(ll a, ll n, ll md){if(n==0){return 1;}else{ll res=power(a,n/2,md);res=(res*res)%md;if(n%2!=0){res=(res*a)%md;}return res;}}
random_device rndm;
mt19937 grndm(rndm());
void mix(ll* a, ll* b){shuffle(a,b,grndm);}

const ll MX = 51;

bitset<MX> edge[21];
ll n, m;
vector<ll> graph[MX];
map<pair<ll,ll>, ll> edge_id; 
bool found;

void dfs(ll node, ll par, ll need, ll id) {
	if(need == node) {
		found = true;
	}
	if(found) {
		return;
	}
	for(auto child: graph[node]) {
		if(child != par) {
			if(!found)
				edge[id][edge_id[{min(node, child), max(node, child)}]] = 1;
			dfs(child, node, need, id);
			if(!found)
				edge[id][edge_id[{min(node, child), max(node, child)}]] = 0;
		}
	}
}

int main(){
	fast_cin();
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
	cin >> n;
	for(ll i = 0; i < n - 1; i++) {
		ll a, b; cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		edge_id[{min(a, b), max(a,b)}] = i;
	}
	cin >> m;
	for(ll i = 0; i < m; i++) {
		ll u, v; cin >> u >> v;
		found = false;
		dfs(u, -1, v, i);
	}
	ll ans = 0;
	for(ll i = 0; i < ((ll)1 << m); i++) {
		ll set_bits = __builtin_popcount(i);
		bitset<MX> cur(0);
		for(ll j = 0; j < m; j++) {
			if((i & ((ll)1 << j))) {
				cur |= edge[j];
			}
		}
		ll num_ways = ((ll)1 << (n - 1 - cur.count()));
		if(set_bits & 1) {
			ans = (ans - num_ways + MOD) % MOD;
		}
		else {
			ans = (ans + num_ways) % MOD;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		String s=scan.next();
		String t=scan.nextLine();
		int a=scan.nextInt();
		int b=scan.nextInt();
		String h=scan.next();
		if(s.contains(h))
		{
			System.out.println((a-1)+" "+b);
		}
		else 
		{
			System.out.println(a+" "+(b-1));
		}
	}

}


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef priority_queue<int> pqi;
typedef priority_queue<int, vi, greater<int>> mpqi;

#define IOS std::ios::sync_with_stdio(false); cin.tie(0);
#define F0R(i,a) for(int i = 0; i < a; i++)
#define R0F(i,a) for(int i = a - 1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define ins insert
#define ft front()
#define bk back()
#define f first
#define s second
#define trav(a,x) for(auto& a : x)
#define ALL(x) (x).begin(), (x).end()

const int MOD = 1000000007;
const int MX = 2e5+2;
const ll INF = 1000000000000000000;
const ld PI = 4*atan((ld)1);
const pi dir[4] = {{1,0}, {0,1}, {-1,0}, {0,-1}};

// -----------

int n, k;
string str;
ll r, p, s;
ll total;
bool used[100001];

int main(){
    IOS;
    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> str;
    F0R(i,n){
        if(i < k){
            if(str[i] == 'r') total += p;
            if(str[i] == 'p') total += s;
            if(str[i] == 's') total += r;
            used[i] = true;
        }
        else if(str[i] != str[i-k]){
            if(str[i] == 'r') total += p;
            if(str[i] == 'p') total += s;
            if(str[i] == 's') total += r;
            used[i] = true;
        }
        else if(!used[i-k]){
            if(str[i] == 'r') total += p;
            if(str[i] == 'p') total += s;
            if(str[i] == 's') total += r;
            used[i] = true;
        }
    }
    cout << total;
    return 0;
    // You should actually read the notes to self.
}

/* NOTES TO SELF:
    Int overflow? Array bounds?
    Edge cases? (n = 1, n = 0)
    Don't be dumbosity please pace yourself.
*/

Measured memory_bytes: 592
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7


Yes = 'Yes'
No = 'No'

def main():
    A,V=mis()
    B,W=mis()
    T=ii()

    if A > B:
        A,B=B,A
    
    if B+W*T <= A+V*T:
        print('YES')
    else:
        print('NO')



main()



Measured memory_bytes: 9948
H,W=map(int,input().split())

if (W%2==0 or H%2==0) and W>2 and H>2 :
    print(int(H*W/2))
else :
    if H==1 or W==1 :
        print(1)
    else :
        print(int((H*W//2)+1))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P pair<int,int>
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

signed main(){
  int x,n;
  cin >> x >> n;
  vint p(n);
  rep(i,0,n){
    cin >> p[i];
  }
  vint list(1000);
  rep(i,0,1000){
    list[i] = -500 + i;
  }
  rep(i,0,1000){
    rep(j,0,n){
      if(list[i] == p[j]){
        list[i] = INF;
      }
    }
  }
  int ans = -INF;
  int dis = INF;
  rep(i,0,1000){
    int DDD = abs(list[i] - x);
    if(DDD < dis){
      dis = DDD;
      ans = list[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3600
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Map<String,String> m = new HashMap<String,String>();
    String preString = sc.next();
    char lastChar = preString.charAt(preString.length() - 1);
    m.put(preString,preString);

    for(int i=1;i<N;i++){
      String string = sc.next();
      if(string.charAt(0) != lastChar || m.containsKey(string)){
        System.out.println("No");
        return;
      }
      lastChar = string.charAt(string.length() - 1);
      m.put(string,string);
    }
    System.out.println("Yes");
    return;
  }
}


Measured memory_bytes: 20948
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n,m,k,sum=0,a=0,b=0;
  long long mod = 1000000007;
  cin >> n >> k;
  for (long long i=k-1;i<=n;i++){
    a = i*(i+1)/2;
    b = n*(n+1)/2 - (n-i-1)*(n-i)/2;
    sum += b - a + 1;
    sum %= mod;
  }
  cout << sum << endl;
}



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

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size()/2; i++) cout << s[2*i];
    if (s.size()%2 == 1) cout << s[s.size()-1];
    cout << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>


#define rep(p,q) for(int i = p;i < q;i++)
#define ll long long

using namespace std;

//127 D
bool pairCompare(const pair<ll,ll> firstElof, const pair<ll,ll> secondElof)
{
    return firstElof.second > secondElof.second;
}
 
int main(void) {
	ll n, m;
	cin >> n >> m;
	vector<ll> a = vector<ll>(n);
	ll minNum = 1e9 + 9;
	ll ans = 0;
	rep(0, n) {
		ll num;
		cin >> a[i];
		//a[num]++;
		minNum = min(num, minNum);
		ans += a[i];
	}
	sort(a.begin(), a.end());
	vector<pair<ll, ll>> bc = vector<pair<ll, ll>>();
	rep(0, m) {
		ll b, c;
		cin >> b >> c;
		bc.push_back(make_pair(b, c));
	}
	sort(bc.begin(), bc.end(), pairCompare);

	ll index = 0;
	rep(0, m) {
		ll b = bc[i].first;
		ll c = bc[i].second;
		
		while (b > 0 && index < n && a[index] < c) {
			ans += c - a[index];
			index++;
			b--;
		}
	}
	cout << ans << endl;
}

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

int main(){
  int n;
  std::cin >> n;
  std::vector<ll> a(n);
  rep(i,n){
    std::cin >> a[i];
  }
  sort(a.rbegin(),a.rend());
  // std::cout <<"max:"<<a[0] << '\n';

  ll ans=0;

  ll la=0;
  rep(i,n){

    ll add=0;
    if(i==0);
    else if(i*2<=n){
      if(i==1)add=a[0];
      else {
        add=min(a[i-1],a[i-2]);
      }
    }else{
      // std::cout << a[i] << ':';
      add=a[la+1];
      la++;
    }
    // std::cout << add << '\n';
    ans+=add;
  }

  std::cout << ans << '\n';


  return 0;
}


Measured memory_bytes: 4836
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
int count =0,max =0;
cin>>s;
for(int i=0;i<s.size();i++)
{   count =0;
   while(i<s.size() && s[i]=='R')
   {count++;
    i++;    
   }
   if(count > max)
    max =count;
}
cout<<max<<endl;

return 0;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

typedef long long LL;
using namespace std;
int n;

LL Get_sqrt(LL x) 
{
	LL l = 1, r = 1e9 + 10;
	LL ans = 0;
	while(l <= r) {
		LL mid = (l + r) >> 1;
		if(mid * mid <= x) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}

int main() 
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		LL A, B; scanf("%lld%lld", &A, &B);
		LL ans = 0;
		LL t = Get_sqrt(A * B - 1);
		if(t * (t + 1) > A * B - 1) ans = 2 * t - 1; 
		else ans = 2 * t;
		if(A * A <= A * B - 1) ans--; if(B * B <= A * B - 1) ans--;
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

using namespace std;

typedef long long ll;


int main(){

    ll N;

    bool tf = true;

    cin >> N;

    vector<ll> A_(N);

    rep(i, N) cin >> A_.at(i);

    sort(A_.begin(), A_.end());

    rep(i, N-1) {
        if(A_.at(i) == A_.at(i+1)) {
            tf = false;
            break;
        }

    }

    if(tf) cout << "YES";
    else cout << "NO";

    return 0;

}

Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val n = readInt()
    val a = readLongList()

    var ans = 1000L
    for (i in 0 until n - 1) {
        if (a[i + 1] - a[i] > 0) {
            val numBuy = ans / a[i]
            ans += (a[i + 1] - a[i]) * numBuy
        }
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

Measured memory_bytes: 36580
require 'prime'
require 'set'
require 'tsort'
include Math
ALP = ('a'..'z').to_a
INF = 0xffffffffffffffff
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def pr?(num);              Prime.prime?(num)                          end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end

str=gsf
k=gif
sets=[]
set=Set.new
ALP.each do |alp|
  idxies = []
  offset=0
  while tidx=str.index(alp,offset)
    offset=tidx+1
    idxies << tidx
  end

  idxies.sort_by! {|a|
    str[a..(str.size-1)]
  }

  idxies.each do |idx|
    repl idx,str.size-1 do |en|
      break if sets.size > k
      sub=str[idx..en]
      next if set.include?(sub)
      sets << sub
      set.add(sub)
    end
  end
end

sets.sort!
puts sets[k-1]


Measured memory_bytes: 2680
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int cnt = 0;
  if (a%2 == 0 && a == b && b == c) cnt = -1;
  else {
    while (a%2 == 0 && b%2 == 0 && c%2 == 0) {
      int x, y, z;
      x = b/2+c/2; y = a/2+c/2; z = a/2+b/2;
      a = x; b = y; c = z;
      cnt++;
    }
  }
  dump(cnt);
  return 0;
}


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

int main() {
  int N,M;
  cin >> N;
  vector<string> s(N);
  
  for(int i=0;i<N;i++)
    cin >> s.at(i);
  
  cin >> M;
  vector<string> t(M);
  for(int i=0;i<M;i++)
    cin >> t.at(i);
  int k=0;
  for(int i=0;i<N;i++){
    int cnt=0;
      for(int j=0;j<N;j++){
        if(s.at(i)==s.at(j))
   	      cnt++;
      }
      for(int j=0;j<M;j++){
        if(s.at(i)==t.at(j))
          cnt--;
      }
    k=max(k,cnt);
  }
  cout << k << endl;
}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int main()
{
    int n,c,k;
    scanf(" %d %d %d", &n, &c, &k);
    vector<int> t(n);
    rep(i,n) scanf(" %d", &t[i]);
    sort(all(t));
    
    int ans=0;
    int idx=0;
    while(idx<n)
    {
        int start = t[idx];
        int s_idx=idx;
        ++ans;

        while(idx<n && start+k>=t[idx])
        {
            ++idx;
            if(idx-s_idx==c) break;
        }
    }

    printf("%d\n", ans);
    return 0;
}


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

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

  int a, b, c, d; cin >> a >> b >> c >> d;
  if (abs(a-c) <= d || abs(a-b) <= d && abs(b-c) <= d)
    cout << "Yes\n";
  else
    cout << "No\n";
}

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

int main(void){
    int N, X;
    cin >> N >> X;
    int sweet[N];
    int min = 10000;

    for(int i = 0; i < N; i++){
        cin >> sweet[i];
        X -= sweet[i];
        if(min > sweet[i])
            min = sweet[i];
    }

    int make = N;

    while(X-min >= 0){
        X -= min;
        make++;
    }

    cout << make << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BTimeLimitExceeded solver = new BTimeLimitExceeded();
        solver.solve(1, in, out);
        out.close();
    }

    static class BTimeLimitExceeded {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            int n = in.ints(), t = in.ints();
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int c = in.ints(), j = in.ints();
                if (j <= t) {
                    min = Math.min(min, c);
                }
            }
            out.println(min == Integer.MAX_VALUE ? "TLE" : Integer.toString(min));
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

    }
}



Measured memory_bytes: 21328
using static System.Console;

class Program
{
    static void Main()
    {
        var s = ReadLine();
        var ans = 0;

        for (var i = 0; i < s.Length; i++)
        {
            if (s[i] == '1')
            {
                ans += 1;
            }
        }
        WriteLine(ans);
    }
}


Measured memory_bytes: 11092
#include <iostream>

using namespace std;

int main(){
    int n, m, c;
    cin >> n >> m >> c;
    int b[m];
    int a[n][m];
    for(int i = 0; i < m; i++) cin >> b[i];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        int x = 0;
        for(int j = 0; j < m; j++){
            x += a[i][j] * b[j];
        }
        x += c;
        if(x > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

def sub(x):
    """x個の最大値・個数
    """
    val = (sum(v[-x:]), x)
    tmp = v[-x]
    n0 = 0
    n1 = 0
    for i in range(n-x, n):
        if v[-x]==v[i]:
            n1 += 1
        else:
            break
    for i in range(n-x-1, -1, -1):
        if v[-x]==v[i]:
            n0 += 1
        else:
            break
    # cmb(n0+n1, n1)
    num = 1
    for i in range(1,n1+n0+1):
        num *= i
    for i in range(1, n1+1):
        num //= i
    for i in range(1, n0+1):
        num //= i
    return val, num
ans = None
for x in range(a, b+1):
    val, num = sub(x)
    if ans is None:
        ans = (val, num)
    else:
        if ans[0][0]*val[1]==ans[0][1]*val[0]: # 0/1
            ans = (ans[0], num+ans[1])
        elif ans[0][0]*val[1]<ans[0][1]*val[0]:
            ans = (val, num)
ans = (ans[0][0]/ans[0][1], ans[1])
print("\n".join(map(str, ans)))

Measured memory_bytes: 67784
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define int long long
#define mod 1000000007
using namespace std;
signed main() {
	int m, n, ans, p;
	while (cin >> n >> m, m) {
		m /= n; ans = 0;
		for (int i = 0; i < n; i++) {
			cin >> p;
			ans += min(m, p);
		}cout << ans << endl;
	}
}


Measured memory_bytes: 3100
import java.util.Scanner;
import java.util.Arrays;


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


        int p = sc.nextInt();
        int q = sc.nextInt();
        int r = sc.nextInt();

        int dist[] = new int[3];
        dist[0] = p;
        dist[1] = q;
        dist[2] = r;

        Arrays.sort(dist);

        System.out.println(dist[0]+dist[1]);

        sc.close();
    }
}

Measured memory_bytes: 23764
N = int(input())
A = list((map(int, input().split())))
# 400区切り

over = 0
under = [False]*8 
for a in A:
  if a < 3200:
    under[a//400] = True
  else:
    over += 1

min_ = max(sum(under), 1)
max_ = sum(under)+over

print(min_, max_)    

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

using namespace std;

map<int, int> req;

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    
    int N;
    cin >> N;
    for(int a = 0; a < N; a++){
        int x;
        cin >> x;
        req[x]--;
    }
    int M;
    cin >> M;
    for(int a = 0; a < M; a++){
        int x;
        cin >> x;
        req[x]++;
    }
    for(auto p : req){
        if(p.second > 0){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}

Measured memory_bytes: 9600
package main

import "fmt"

func main() {
	var h, n int
	fmt.Scan(&h, &n)

	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}

	dp := make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, h+1)
		for j := 0; j <= h; j++ {
			dp[i][j] = 1e10
		}
	}
	dp[0][0] = 0

	for i := 0; i < n; i++ {
		for j := 0; j <= h; j++ {
			dp[i+1][j] = min(dp[i+1][j], dp[i][j])

			hp := min(h, j+a[i])
			dp[i+1][hp] = min(dp[i+1][hp], dp[i+1][j]+b[i])
		}
	}

	fmt.Println(dp[n][h])
}

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


Measured memory_bytes: 83456
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


ll gcd(ll x, ll y){
  if(x%y==0)return y;
  return gcd(y,x%y);
}
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll n;
  cin >> n;
   vector<int>a(n);
  rep(i,n) cin >> a[i];
  int ans=0;
  rep(i,n-2){
    if((a[i]<a[i+1] && a[i+1]<a[i+2])||(a[i]>a[i+1] && a[i+1]>a[i+2]))ans++;
  }
  cout << ans << endl;
}


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


int main()
{
	int n; cin >> n;
	for (int i = 0; i < 100; ++i)
		for (int j = 0; j < 100; ++j)
			if (4*i + 7*j == n)
			{
				cout << "Yes" << endl;
				return 0;
			}
	cout << "No" << endl;
}


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

typedef long long ll;

vector<int> adj[200010];
int n, dp[800100], A[200010];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        dp[v] = 0;
    } else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        dp[v] = max(dp[v*2], dp[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr) {
        return dp[v];
    }
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm))
           , query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        dp[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        dp[v] = max(dp[v*2], dp[v*2+1]);
    }
}

int lis[200010];

struct CoordinateCompression {
    vector<ll> cc {};

    void insert(ll x) {
        cc.push_back(x);
    }

    void make() {
        sort(cc.begin(), cc.end());
        cc.resize( unique(cc.begin(), cc.end()) - cc.begin() );
    }

    int get_pos(ll x) {
        return lower_bound(cc.begin(), cc.end(), x) - cc.begin();
    }

    ll get_val(int p) {
        return cc[p];
    }
};

CoordinateCompression C;

void dfs(int u, int p) {
    //update dp pos
    int pos = C.get_pos(A[u]);
    int prev = query(1, 0, n - 1, pos, pos);

    int mx = query(1, 0, n - 1, 0, pos - 1) + 1;
    update(1, 0, n - 1, pos, mx);

//    cout << "u " << u << endl;
//    cout << "pos " << pos << endl;
//    cout << "mx " << mx << endl;
//    cout << endl;

    lis[u] = max(mx, query(1, 0, n - 1, 0, n - 1));

    for(auto v : adj[u]) {
        if(v == p) continue;
        dfs(v, u);
    }

    //rollback dp pos
    update(1, 0, n - 1, pos, prev);
}

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

    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> A[i];
        C.insert(A[i]);
    }

    C.make();

    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0, -1);
    build(1, 0, n - 1);

    for(int i = 0; i < n; i++) cout << lis[i] << endl;
    cout << endl;
}


Measured memory_bytes: 30772
s = input()
l = []
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    l.append(i)
a = [0] * len(s)
if len(l) == 1:
  a[l[0]] = (l[0]+2)//2 + (len(s)-l[0]-1)//2
  a[l[0]+1] = (l[0]+1)//2 + (len(s)-l[0])//2
  print(' '.join(map(str,a)))
  exit()
a[l[0]] = (l[0]+2)//2 + (l[1]-l[0])//2
a[l[0]+1] = (l[0]+1) // 2 + (l[1]-l[0]+1)//2
i = 2
while True:
  if i == len(l)-1:
    break
  a[l[i]] = (l[i]-l[i-1]+1)//2 + (l[i+1]-l[i])//2
  a[l[i]+1] = (l[i]-l[i-1])//2 + (l[i+1]-l[i]+1)//2
  i += 2
a[l[-1]] = (l[-1]-l[-2]+1)//2 + (len(s)-l[-1]-1)//2
a[l[-1]+1] = (l[-1]-l[-2])//2 + (len(s)-l[-1])//2
print(' '.join(map(str,a)))

Measured memory_bytes: 14532
#include <bits/stdc++.h>
using namespace std;
#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    long N, D; 
    cin >> N >> D;
    D *= D;
    int count = 0;
    REP(i, 0, N){
        long x, y;
        cin >> x >> y;
        long d = x * x + y * y;
        if(d <= D) count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 3632
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [-1] *(N+2)
    ckc = [True] * (N+2)
    for i in a:
        ckc[i] = False

    def f(n: int):
        if(dp[n] != -1):
            return dp[n]

        if n <= 0:
            dp[n] = 0
        else:
            if not ckc[n-1] and not ckc[n-2]:
                dp[n] = 0
            elif not ckc[n-1]:
                dp[n] = f(n-2) % MOD
            elif not ckc[n-2]:
                dp[n] = f(n-1) % MOD
            else:
                dp[n] = (f(n-1) + f(n-2)) % MOD
            
        return dp[n]

    dp[0] = 1
    f(N)
    print(dp[N])
    # print(dp)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 109284
n, x = map(int, input().split())

heights = [1]
putties = [1]
for _ in range(50):
    heights.append(heights[-1] * 2 + 3)
    putties.append(putties[-1] * 2 + 1)

def burger(l, y):
    if l == 0:
        return y
    if y <= l:
        return 0
    hl = heights[l]
    if y >= hl - l:
        return putties[l]

    if hl // 2 + 1 <= y:
        return putties[l - 1] + 1 + burger(l - 1, y - (hl // 2 + 1))

    return burger(l - 1, y - 1)


print(burger(n, x))


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

ll k;

double s(ll num) {
	string s = to_string(num);
	double res = 0;
	for (int i = 0; i < s.length(); i++) {
		res += s[i] - '0';
	}

	return res;
}

ll dm(ll num, ll d) {
	string a = to_string(d);
	string b = to_string(num);
	b[b.length() - a.length()] = '9';

	return stoll(b);
}

int main() {
	cin >> k;


	ll ans = 1;
	ll d = 1;
	for (int i = 0; i < k; i++) {
		if (ans/s(ans) > (ans+d)/s(ans+d)) {
			ans = dm(ans, d);
			d *= 10;
		}

		cout << ans << endl;
		ans += d;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n,k;
  cin >> n >> k;
  ll ans=k;
  for(ll i=1;i<n;i++) {
    ans*=(k-1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int num[100000] = {0};
    int ans = 0;
    for(int i = 0; i < n; i++){
        if (a[i] > 100000) ans++;
        else num[a[i]-1]++;
    }
    for(int i = 0; i < 100000; i++){
        if (num[i] < i+1) ans += num[i];
        else ans += num[i] - (i + 1);
    }
    printf("%d\n", ans);
    
    
    
}

Measured memory_bytes: 896
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <bitset>
#include <iterator>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <random>
#include <numeric>
#include <set>
#include <cassert>
#include <cmath>
#include <cinttypes>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}
template<class T> T read_val() { throw 1; }
template<> int read_val() { int tmp; scanf("%" PRId32, &tmp); return tmp; }
template<> long long read_val() { long long tmp; scanf("%" PRId64, &tmp); return tmp; }
auto read_int = read_val<int>; auto read_long = read_val<long long>;
template<class T> void scanf_vec(vector<T>& vec) { for (int i = 0; i < vec.size(); i++) vec[i] = read_val<T>(); }

#define MOD 1000000007
#define inf 2000000000
#define FWT_SIZE 2000000
#define pii pair<int,int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define sort_all(x) sort(all(x))
#define make_unique(x) (x).erase(unique(all(x)), (x).end())



int main() {

#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n = read_int(), k = read_int();
//	cin >> n >> k;
	vector<int> p(n);
	scanf_vec(p);
	//cin >> p;
	stack<int> min_p;
	int nearest = n, ans = 0, been_none=0;

	stack<pii> max_a, max_b;

	for (int j = p.size() - 1; j >= 0; j--)
	{
		while (min_p.size() > 0 && p[min_p.top()] >= p[j])
			min_p.pop();

		bool changes = false;
		if (min_p.size() > 0 && p[j] > p[min_p.top()])
		{
			changes = min_p.top() < j + k;
			nearest = min(nearest, min_p.top());
		}
		int curr_max = 0;
		if (max_a.size() > 0) curr_max = max(curr_max, max_a.top().second);
		if (max_b.size() > 0) curr_max = max(curr_max, max_b.top().second);
		if (j + k < n && p[j + k] < curr_max)
			changes = true;

		min_p.push(j);

		if (j + k - 1 < n && nearest < j + k && (j+k==n || changes))
		{
			ans++;
		}

		if (j + k - 1 < n && nearest >= (j + k))
			been_none = 1;

		if (k > 1)
		{
			if (max_a.size() > 0) max_a.push({ p[j], max(p[j],max_a.top().second) });
			else max_a.push({ p[j], p[j] });
			if (max_b.size() == 0)
			{
				int max_v = 0;
				while (max_a.size() > 0)
				{
					max_v = max(max_v, max_a.top().first);
					max_b.push({ max_a.top().first, max_v });
					max_a.pop();
				}
			}
			while (max_a.size() + max_b.size() > (k - 1))
				max_b.pop();
		}
	}
	printf("%d", ans + been_none);
//	cout << ans+been_none;

	return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());

using ll = long long int;
const ll MOD = 1000000007;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

ll mod_add(ll a, ll b) {
    return (a + b) % MOD;
}

ll mod_sub(ll a, ll b) {
    return (a + MOD - b) % MOD;
}

ll mod_mul(ll a, ll b){
    return (a * b) % MOD;
}

ll mod_pow(ll base, ll po) {
    if(po == 0)
        return 1;
    else if(po == 1)
        return base;
    ll new_base = mod_pow(base, po / 2);
    return mod_mul(mod_mul(new_base, new_base), po % 2 == 0 ? 1 : base);
}

ll mod_div(ll a, ll b){
    return mod_mul(a, mod_pow(b, MOD - 2));
}

int main(){
    int n;
    cin >> n;
    double sum = 0.0;
    rep(i, n) {
        double a;
        cin >> a;
        sum += 1 / a;
    }
    cout << 1 / sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

ll gcd(ll a, ll b)
{
    if (b==0) return a;
    return gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
    return (a/gcd(a, b))*b;
}

int main(){
    int x;
    cin >> x;
    
    int z = lcm(x, 360);

    int ans = z/x;
    
    cout << ans << endl;
    return 0;
}


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

const int MAXN = 20;
const int mod = 1000000007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int n, m, K;
int lim[MAXN], out[MAXN], f[2][1 << MAXN - 1];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> m >> K; --n;
	for (int i = 1, a, b, c; i <= K; ++i) {
		std::cin >> a >> b >> c; --a, --b;
		lim[a] |= 1 << b, out[a] |= c << b;
	}
	int now = 1, lst = 0;
	f[now][0] = 1;
	const int U = 1 << n;
	for (int T = 0; T < m; ++T)
		for (int j = 0; j != n; ++j) {
			std::swap(lst, now);
			memset(f[now], 0, U << 2);
			for (int k = 0; k != U; ++k) if (int t = f[lst][k]) {
				if ((~lim[T] >> j & 1) || (out[T] >> j & 1) == 0) {
					if (~k >> j & 1) reduce(f[now][k] += t - mod);
				}
				if ((~lim[T] >> j & 1) || (out[T] >> j & 1) == 1) {
					if (k >> j & 1) reduce(f[now][k] += t - mod);
					else {
						int nx = k >> j ? __builtin_ctz(k >> j) + j : 30;
						int tx = (k & (1 << j) - 1) | (k >> nx + 1) << nx + 1 | 1 << j;
						reduce(f[now][tx] += t - mod);
					}
				}
			}
		}
	int ans = 0;
	for (int i = 0; i != U; ++i) reduce(ans += f[now][i] - mod);
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<math.h>
#include<queue>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
const int mod = 1000000007;
const int INF = 1000000000;
const long long LINF = 1e18;
const int MAX = 510000;
int main(){
	int n, m;
	int ans = 0;
	bool f = 1;
	cin >> n >> m;
	vector<int> k(n);
	
	vector<vector<int>> a(n, vector<int>(m));

	for (int i = 0; i < n; i++) {
		cin >> k.at(i);
		for (int j = 0; j < k.at(i); j++) {
			int b;
			cin >> b;
			a.at(i).at(b-1) = 1;
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (a.at(j).at(i) == 0)f = 0;
			
		}
		if (f == 1)ans++;
		f = 1;
	}
	cout << ans << endl;
		return 0;

	
}

Measured memory_bytes: 3644