akhauriyash/Code-Regression huggingface dataset:
/*
Submitted With (^^) by -> Hossam ^_^
_____________________
|     ___     ___     |
|    (^_^)   (^_^)    |
|   /( | )\_/( | )\   |
|_____|_|_____|_|_____|
*/

#include <bits/stdc++.h>

using namespace std;

inline void prep()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
};

#define X first
#define Y second
#define endl '\n'
#define ll long long
#define inf (0x7fffffffffffffff)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << (x) << "\n";
#define ZXC cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl;

const int mod = (int)1e9 + 7;
// const int mod = 998244353;
const int MX = (int)5e5 + 10;

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


    puts((a & 1) && (b & 1) ? "Yes" : "No");

    // ZXC
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
const int MAX=1e5+10;

int N, M;
vi work[MAX];
void input(){
    cin>>N>>M;
    rep(i,N){
        int A,B;
        cin>>B>>A;
        if(M-B+1>=1)work[M-B+1].pb(A);
    }
}

int ans;
void solve(){
    multiset<int> ev;
    for(int i=M; i>=1; i--){
        rep(j,sz(work[i])){
            ev.insert(work[i][j]);
        }
        if(!ev.empty()){
            auto ite=ev.end();
            ite--;
            ans+=*ite;
            ev.erase(ite);
        }
    }
}

void output(){
    cout<<ans<<endl;
}

int main(){
  input();
  solve();
  output();
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	uint64_t x; cin>>x;
	uint64_t a=100,ans=0;
	while(a<x)a+=a/100,++ans;
	cout<<ans<<"\n"s;
}

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

int main() {
  double W, H, x, y;
  cin >> W >> H >> x >> y;
  int ans = 0;
  if (W/2 == x && H/2 == y) ans = 1;
  cout << W*H / 2 << " " << ans << endl;
}

Measured memory_bytes: 256
//abc164_d.cpp
//Sun Apr 26 20:56:43 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	ll n=s.length();

	ll count[2030];
	fill(count,count+2030,0);
	ll amari[n];
	fill(amari,amari+n,0);

	ll first = ll(s[n-1]-'0');

	count[first]++;
	amari[n-1] = first;

	ll keta = 1;
	for (ll i=n-2;i>=0;i--){
		keta = (10*keta)%2019;
		ll tmp = ll(s[i]-'0');
		amari[i] = (tmp*keta+amari[i+1])%2019;
		count[amari[i]]++;
	}

	ll ans = 0;
//	for (int i=0;i<n;i++){
//		cout << i << " " << amari[i] << endl;
//	}
	for (int i=0;i<2019;i++){
		ans += count[i]*(count[i]-1)/2;
	}

	cout << ans+count[0] << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 5304
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll dp [110][100100] = {0};
int  main(){
ll n,w;
ll weight [110],value [110];
cin >> n >> w;
for(int i=0;i<n;i++)cin >> weight[i]>>value[i];
for(int i=0;i<n;i++){
    for(int sum=0;sum<=w;sum++){
        if(sum-weight[i]>=0){
            chmax(dp[i+1][sum],dp[i][sum-weight[i]]+value[i]);
        }
        chmax(dp[i+1][sum],dp[i][sum]);
    }
}
cout << dp[n][w]<<endl;
}



Measured memory_bytes: 79360
# ABC097-B
ans_list = [1]
for i in range(2, 10):
    ans_list.append(2 ** i)
for i in range(2, 7):
    ans_list.append(3 ** i)
for i in range(2, 5):
    ans_list.append(5 ** i)    
for i in range(2, 4):
    ans_list.append(6 ** i)
    ans_list.append(7 ** i)
    ans_list.append(10 ** i)
num = [11,12, 13, 14, 15, 17, 18, 19, 20, 21, 22,  23,24, 25, 26, 27, 28,  29, 30,  31]
for i in num:
    ans_list.append(i ** 2)
X = int(input())
for i in range(X, 0, -1):
    if i in ans_list:
        ans = i
        break
print(ans)

Measured memory_bytes: 3064
// Problem: https://atcoder.jp/contests/abc160/tasks/abc160_b
// Type: Math / Greedy

#include <bits/stdc++.h>

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

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

	int x;
	cin >> x;
	
	int mh = (x / 500) * 1000 + ((x % 500) / 5) * 5;
	
	cout << mh;

	return 0;
}


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

string s;

int main(void){
	cin >> s;
	int ans = INT_MAX;
	for(int i = 0; i < s.size()-2; i++){
		ans = min(ans, abs(stoi(s.substr(i, 3))-753));
	}
	cout << ans << endl;
	return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    double v;
    while (cin >> v)
    {
        double t = v / 9.8;
        double y = 4.9 * t * t;
        OP(ceil((y + 5) / 5))
    }
    return 0;
}


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

int main() {
    int64_t A, B, C;
    cin >> A >> B >> C;
    if ((A == B && B != C) || (B == C && C != A) || (C == A && A != B)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  string S,T; cin>>S>>T;
  cout<<T<<S<<endl;
  }



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

int main(){
  
  int a,b,day;
  int tuki[12];
  string days[7];
  tuki[0]=31,tuki[1]=29,tuki[2]=31,tuki[3]=30;
  tuki[4]=31,tuki[5]=30,tuki[6]=31,tuki[7]=31;
  tuki[8]=30,tuki[9]=31,tuki[10]=30,tuki[11]=31;
  days[0] = "Wednesday";
  days[1] = "Thursday";
  days[2] = "Friday";
  days[3] = "Saturday";
  days[4] = "Sunday";
  days[5] = "Monday";
  days[6] = "Tuesday";

  while(1){
    day=0;
    cin >> a >> b;
    if(a == 0)break;
    for(int i=1;i<a;i++){
      day += tuki[i-1];
    }
    day += b;
    day %= 7;
    cout << days[day] << endl;
  }
  return 0;
}
  

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

bool isInclude3(int n) {
  while(n != 0) {
    if(n % 10 == 3) {
      return true;
    }
    n /= 10;
  }
  return false;
}

int main()
{
  int n;
  cin >> n;
  for(int i = 3; i <= n; i++) {
    if(i % 3 == 0) cout << " " << i;
    else if(isInclude3(i)) cout << " " << i;
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3096
#include <stdio.h>

int dp[50];

int fib(int n){
  if(n == 0 || n==1) return dp[n]=1;
  if(dp[n]!=-1) return dp[n];
  return dp[n]=fib(n-1)+fib(n-2);
  
}

int main(){

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

  for(i=0;i<50;i++) dp[i] = -1;

  printf("%d\n",fib(n));

  return 0;
  
}



Measured memory_bytes: 2132
#include<stdio.h>
int main(){
    int sei[31]={0},i,a;
    for(i=1;i<29;i++){
        scanf("%d",&a);
        sei[a]=1;
    }
    for(i=1;i<31;i++){
        if(sei[i]==0)printf("%d\n",i);
    }
    return 0;
}

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

int main() {
  
  string S;
  cin >> S;
  
  int l = size(S);
  char x = S.at(l-1);
  
  if(x != 's') cout << S << "s" << endl;
  else cout << S << "es" << endl;

}

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

//template
#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 ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//end

constexpr ll c=300000000000000000LL;
int N; ll x[11000],y[11000];
bool que(ll n,ll r){if(n<0||r<0||n<r)return 0; return (n&r)==r;}
bool col(ll a){
   bool res=0;
   rep(i,0,N)if(a>=x[i])res^=que(c-x[i]-y[i],a-x[i]);
   return res;
}
ll calc(ll n,ll t,int r){
   if(t<0)return 0;
   chmin(t,n); ll dp[64][3][2]={}; dp[60][0][1]=1;
   rrep(i,59,-1)rep(j,0,3)rep(k,0,2)if(dp[i+1][j][k]){
      rep(nxt,0,2){
         if((n>>i&1)==0&&nxt)continue;
         if(k&&nxt&&(t>>i&1)==0)continue;
         int nj=(j+(nxt?(i&1?2:1):0))%3,nk=k;
         if(nxt==0&&(t>>i&1))nk=0;
         dp[i][nj][nk]+=dp[i+1][j][k];
      }
   } return dp[0][r][0]+dp[0][r][1];
}
ll rng(ll n,ll lb,ll rb,int r){return calc(n,rb,r)-calc(n,lb,r);}
bool flag(ll lb,ll rb,int r){
   bool res=0;
   rep(i,0,N)res^=rng(c-x[i]-y[i],lb-x[i],rb-x[i],((r-x[i])%3+3)%3)&1;
   return res;
}

//reference:https://physics0523.hatenablog.com/entry/2019/02/26/190724
int main(){
   scanf("%d",&N); rep(i,0,N)scanf("%lld%lld",&x[i],&y[i]);
   ll lb=-c/2,rb=c/2; int r=-1;
   rep(i,0,3)if(flag(lb,rb,i)){r=i; break;}
   //assert(r>=0);
   while(rb-lb>1){
      ll mid=(lb+rb)>>1;
      if(flag(lb,mid,r))rb=mid; else lb=mid;
   } assert(col(rb));
   ll x1=rb,x2=rb;
   rrep(k,62,-1){
      if(col(x1-(1LL<<k)))x1-=1LL<<k;
      if(col(x2+(1LL<<k)))x2+=1LL<<k;
   } printf("%lld %lld\n",x1,c-x2);
   return 0;
}


Measured memory_bytes: 384
n, h = map(int, input().split())
A, B = [], []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

Amax = max(A)
B.sort(reverse=True)

ans = 0
for b in B:
    if b > Amax:
        h -= b
        ans += 1
    if h <= 0:
        print(ans)
        break
else:
    if h % Amax == 0:
        print(ans + h//Amax)
    else:
        print(ans + h//Amax + 1)


Measured memory_bytes: 11348
/*╔═══╗──╔╗╔╗───────────────────╔╗────────╔═══╦═══╗
  ║║─║╠╗╠╗╔╣╚═╦══╦═╗╔╦╗╔═╗╔══╦══╣╚═╦╦══╦══╣║─║║║─╚╝
  ║╔═╗║╚╝║╚╣║║║╚╝║║─╔╦╗║║║║╚╝║╚╝║╚╝║║║═╬══║╔═╗║╚╩═║
  ╚╝─╚╩══╩═╩╝╚╩══╩╝─╚╩╝╚╝╚╩══╩══╩══╩╩══╩══╩╝─╚╩═══╝*/

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

#define f(i,k,n) for(i=k;i<n;i++)
#define fd(i,k,n) for(i=k;i>n;i--)
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvll vector<vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define all(c) c.begin(),c.end()
#define sz(c) (int)c.size()
#define lb lower_bound
#define ub upper_bound
#define gi greater<int>
#define rev reverse
#define ff first
#define ss second
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define imp cout << "IMPOSSIBLE" << endl;
#define nl cout << endl
#define hello cout << "hello" << endl;
#define sp(x) fixed << setprecision(x)
#define re return

void dbg_out(){cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

const double pi = 3.14159265359;
const ll mod = 1000000007;
const ll modc = 998244353;

ll inline power(ll a, ll b, ll p){
    a %= p;
    ll ans = 1;
    while(b>0){
        if(b & 1)
            ans = (ans*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return ans;
}

ll mod_inv(ll n, ll p){
    return power(n,p-2, p);
}

bool inline isPrime(ll n) {
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (ll i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
}
template<typename... T>
void W(T&&... args)
{
	((cout << sp(9) <<  args << " "), ...);
	nl;
}
template<typename... T>
void R(T&&... args)
{
	((cin >> args), ...);
}
ll ston(string s) 
{
	ll a = 0;
	reverse(s.begin(),s.end());
	ll pow = 1;
	for(int i=0;i<s.size();i++)
	{
		a += pow*(s[i]-'0');
		pow*=10;
	}
	return a;
}
template <class T>
string to_binary(T n) 
{
	string binaryNum;
	int i = 0;
	while (n > 0) {
		binaryNum.pb((n % 2)+'0');
		n = n / 2;
		i++;
	}
	reverse(binaryNum.begin(),binaryNum.end());
	return binaryNum;
}
template<class T>
bool perfectSq(T n)
{
	if(sqrt(n) == floor(sqrt(n)))
		return true;
	else
		false;
}
template<class T>
void wv(T &v)
{
	for(auto x : v)
		cout << x << " " ;
	nl;
}
template<class T>
void rv(T &v)
{
	for(int i=0;i<sz(v);i++)
		cin >> v[i];
}
void solve()
{
	int i,j;ll sum = 0,prod = 1;ll maxl = LONG_MIN,minl = LONG_MAX;int maxi = INT_MIN,mini = INT_MAX;
	vi a(5);
	rv(a);
	for(i=0;i<5;i++)
		if(a[i] == 0)
		{
			W(i+1);
			re;
		}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t = 1;
	while(t--)
	{
		solve();
	}
}


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

int main(){
int N,X,min;
cin>>N>>X;
int m[N];
for(int i = 0; i<N;i++){
    cin>>m[i];
    X = X -m[i];
}
min = 0;
if(X >0){
for(int i = 0;i < N; i++){
  if(min < X/m[i]){
    min = X/m[i];
  }
}
}
  cout<<N+min;
    return 0;
}

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


using namespace std;

using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a,b) make_pair(a,b)
#define pbk(a) push_back(a)

int main() {
	ll n;
	cin >> n;
	ll cur = n;
	set<ll> ps;

	for(ll i = 1; i * i <= n; i++) {
		if (cur % i == 0) {
			ps.insert(i);
			ps.insert(n / i);
		}
	} 
	ll ans = 0;
	for (ll p : ps) {
		ll cur = p - 1;
		if (cur <= 1) continue;
		if (n / cur == n % cur) {
			ans += cur;
		} 
	}
	cout << ans << endl;

	
	return 0;
}

Measured memory_bytes: 512
m = int(input())
n = int(input())
edges = [[] for _ in range(m)]
for _ in range(n):
    x,y = map(int,input().split())
    edges[x-1].append(y-1)
L = []
visited = [False]*m
def visit(node):
    if not visited[node]:
        visited[node] = True
        for nn in edges[node]:
            visit(nn)
        L.append(node)
for node in range(m):
    visit(node)
for e in L[::-1]:
    print(e+1)


Measured memory_bytes: 5600
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;
template <class T> struct SegTree {
	int n, N; vector <T> tree, lazy;
	const T ID = MAX;
	void init(int _n) { n = _n, N = 4 * _n; tree.assign(N, _n), lazy.assign(N, MAX); }
	T comb(T a, T b) { return min(a, b); }
	void prop(int i, int st, int en) {
		tree[i] = comb(tree[i], lazy[i]);
		if(st != en) {
			lazy[2 * i] = comb(lazy[2 * i], lazy[i]);
			lazy[2 * i + 1] = comb(lazy[2 * i + 1], lazy[i]);
		}
		lazy[i] = MAX;
	}
	void _update(int i, int st, int en, int l, int r, T val) {
		if(lazy[i] != MAX) prop(i, st, en);
		if(en < l || st > r) return;
		if(l <= st && en <= r) {
			lazy[i] = val;
			prop(i, st, en);
			return;
		}
		int mid = (st + en) / 2;
		_update(2 * i, st, mid, l, r, val);
		_update(2 * i + 1, mid + 1, en, l, r, val);
		tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
	}
	T _query(int i, int st, int en, int l, int r) {
		if(lazy[i] != MAX) prop(i, st, en);
		if(en < l || st > r) return ID;
		if(l <= st && en <= r) return tree[i];
		int mid = (st + en) / 2;
		return comb(_query(2 * i, st, mid, l, r), _query(2 * i + 1, mid + 1, en, l, r));
	}
	T query(int l, int r) { return _query(1, 1, n, l, r); }
	void update(int l, int r, T val) { _update(1, 1, n, l, r, val); }
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n, q;
	cin >> n >> q;
	ll ans = 1LL * (n - 2) * (n - 2);
	SegTree <int> row, col;
	row.init(n), col.init(n);
	while(q --) {
		int t, x;
		cin >> t >> x;
		if(t == 1) {
			int y = col.query(x, x);
			ans -= (y - 2);
			row.update(1, y - 1, x);
		}
		else {
			int y = row.query(x, x);
			ans -= (y - 2);
			col.update(1, y - 1, x);
		}
	}
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 15868
while True:
  n, h = map(int, input().split())
  if n == 0:
    break
  hit = set()
  for _ in range(h):
    c, a, b = input().split()
    if c == "xy":
      add = {(int(a), int(b), z) for z in range(1, n + 1)}
    elif c == "xz":
      add = {(int(a), y, int(b)) for y in range(1, n + 1)}
    elif c == "yz":
      add = {(x, int(a), int(b)) for x in range(1, n + 1)}
    hit = hit | add
  print(n ** 3 - len(hit))



Measured memory_bytes: 15916
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


S = int(input())
mod = 10 ** 9 + 7

if S < 3:
    print(0)
    exit()

res = 1
for i in range(2, S+1):
    if i * 3 > S:
        continue
    n = S - i * 3 + (i-1)
    r = i - 1
    res += combinations_count(n, r)

print(res % mod)


Measured memory_bytes: 9132
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int main(){
    ll n,m,d;
    cin >> n >> m >> d;
    double ans = 0.0;
    ans = (double)(2*(n-d))/((double)n*(double)n);
    if(d==0)ans/=2.0;
    cout <<fixed << setprecision(15) << ans *(m-1) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define N (100000+1000)
#define LL long long
using namespace std;

LL n,e,t,f[N],a[N],Segt[N<<2],p;

void Update(LL now,LL l,LL r,LL x,LL v)
{
	if (l==r) {Segt[now]+=v; return;}
	LL mid=(l+r)>>1;
	if (x<=mid) Update(now<<1,l,mid,x,v);
	else Update(now<<1|1,mid+1,r,x,v);
	Segt[now]=min(Segt[now<<1],Segt[now<<1|1]);
}

LL Query(LL now,LL l,LL r,LL l1,LL r1)
{
	if (l>r1 || r<l1) return 1e17;
	if (l1<=l && r<=r1) return Segt[now];
	LL mid=(l+r)>>1;
	return min(Query(now<<1,l,mid,l1,r1),Query(now<<1|1,mid+1,r,l1,r1));
}

int main()
{
//	freopen("data.in","r",stdin);
//	freopen("datam.out","w",stdout);
	scanf("%lld%lld%lld",&n,&e,&t);
	for (int i=1; i<=n; ++i)
		scanf("%lld",&a[i]);
	for (int i=1; i<=n; ++i)
	{
		while (p<=i-1 && 2*(a[i]-a[p])>=t)
			Update(1,1,n,p,-2*a[p]),p++;
		LL temp=1e17;
		temp=min(temp,Query(1,1,n,1,p-1));
		if (p<=i-1) temp=min(temp,Query(1,1,n,p,i-1)+t-2*a[i]);
		f[i]=min(temp+3*a[i],f[i-1]+a[i]-a[i-1]+t);
		Update(1,1,n,i,-a[i-1]+f[i-1]);
	}
	printf("%lld\n",f[n]+e-a[n]);
}

Measured memory_bytes: 4992
#include <vector>
#include <string>
#include <iostream>

using mass_t = std::vector<std::vector<std::string>>;

const std::string empty { "." };
const std::string bomb { "#" };

const std::vector<std::pair<int, int>> diffs = {
  { 0, -1 },  // 上
  { 0, 1 },   // 下
  { -1, 0 },  // 左
  { 1, 0 },   // 右
  { 1, -1 },  // 斜め右上
  { -1, -1 }, // 斜め左上
  { 1, 1 },   // 斜め右下
  { -1, 1 },  // 斜め左下
};

mass_t make_mass(int H, int W) {
  mass_t mass;
  for (int h = 0; h < H; ++h) {
    std::vector<std::string> v;
    std::string s;
    std::cin >> s;
    for (int w = 0; w < W; ++w) {
      v.push_back(s.substr(w, 1));
    }
    mass.push_back(v);
  }
  return mass;
}

void solve(int H, int W) {
  const mass_t mass = make_mass(H, W);
  std::vector<std::vector<int>> v;

  for (int h = 0; h < H; ++h) {
    std::vector<int> t(W, 0);
    v.push_back(t);
  }

  for (int h = 0; h < H; ++h) {
    for (int w = 0; w < W; ++w) {
      if (mass[h][w] == bomb) {
        continue;
      }
      for (auto && d : diffs) {
        const auto hi { h + d.first };
        const auto wi { w + d.second };
        if (hi < 0 || H <= hi) {
          continue;
        }
        if (wi < 0 || W <= wi) {
          continue;
        }
        if (mass[hi][wi] == bomb) {
          v[h][w] += 1;
        }
      }
    }
  }

  for (int h = 0; h < H; ++h) {
    for (int w = 0; w < W; ++w) {
      if (mass[h][w] == bomb) {
        std::cout << bomb;
      } else {
        std::cout << v[h][w];
      }
    }
    std::cout << std::endl;
  }
}

int main()
{
  int H, W;
  std::cin >> H >> W;
  solve(H, W);
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
ld a,b,x,A,ans;
int main(void){
    cin>>a>>b>>x;
    if(a*a*b<=2*x){
        A=a*a*b-x;
        ans=180*(atan(2*A/(a*a*a)))/M_PI;
    }
    else{
        ans=180*(atan(a*b*b/(2*x)))/M_PI;
    }
    cout<<setprecision(10)<<ans<<endl;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
	x += y;
	if( x >= m )
		x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
	x -= y;
	if( x < 0 )
		x += m;
}

int main() 
{
	#ifdef gupta_samarth
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	fastio();

	int n,q;
	cin>>n>>q;

	fenwick_tree<ll> ft(n+1);

	vector<ll>a(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		ft.add(i,a[i]);
	}

	while(q--)
	{
		int t, l, r;
		cin>>t>>l>>r;

		if( t == 0 )
		{
			ft.add(l,r);
		}
		else
		{
			cout<<ft.sum(l,r),nl;
		}
	}

	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}


Measured memory_bytes: 12172
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	string s,t;
	int res=0;
	cin >> s >> t;
	for(int i=0;i<s.size();i++)
		if(s[i]!=t[i])
			++res;
	cout << res;
}

Measured memory_bytes: 3880
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n; cin>>n;
	ll a[n][n], dp[n][n];
	rep(i,n){
		rep(j,n){
			cin>>a[i][j]; dp[i][j]=a[i][j];
		}
	}
	rep(k,n){
		rep(i,n){
			rep(j,n){
				if(i==j||j==k||k==i||dp[i][k]==INF||dp[k][j]==INF) continue;
				if(dp[i][k]+dp[k][j]==a[i][j]) dp[i][j]=INF;
				else if(dp[i][k]+dp[k][j]<a[i][j]){
					cout<<-1<<endl;
					return 0;
				}
			}
		}
	}
	ll ans=0;
	rep(i,n){
		rep(j,n){
			if(dp[i][j]!=INF) ans+=dp[i][j];
		}
	}
	cout<<ans/2<<endl;
	return 0;
}


Measured memory_bytes: 2172
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
#define fu(i,a,b)   for(ll i=a;i<b;i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<" "
#define pr2(a,b)    cout<<a<<" "<<b<<" "
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(a.begin(),a.end(),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()						
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define se          second
#define fi          first 
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
void inline minize(ll& a,ll b){a=(a>b?b:a);};
void inline maxize(ll& a,ll b){a=(a<b?b:a);};
double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e5;

ll arr[MAXN+5],arrcnt[2*MAXN+5];
pll arrsort[MAXN+5];
class cmp_r{
	public: bool operator()(pll a,pll b){
		re a.se>b.se;
	}
};

ll Solves(){
//	INPUT;
	ll n,k,m,cnt=0,ans=oo,x,y,p=1,moreone=0,minus=0,sumpress=0;
	// PROCESSING IN HERE
	priority_queue<pll,vector<pll>,cmp_r> pq;
	sc2(n,m);
	fu(i,0,n){
		sc(arr[i]);
		if(i){
			if(arr[i]!=arr[i-1])moreone=1;
			if(arr[i]>=arr[i-1])arrsort[i]=mp(arr[i-1],arr[i]),sumpress+=arr[i]-arr[i-1];
			else arrsort[i]=mp(arr[i-1],arr[i]+m),sumpress+=arr[i]+m-arr[i-1];
		}
	}
	sort(arrsort+1,arrsort+n);
	
	fu(i,1,2*m){
		minus=0;
		while(pq.size() and pq.top().se<i)minus+=pq.top().se-pq.top().fi-1,pq.pop();
		arrcnt[i]=arrcnt[i-1]+pq.size()-minus;
		if(i>m)arrcnt[(i-1)%m+1]+=arrcnt[i];
		while(p<n and arrsort[p].fi+1==i)pq.push(arrsort[p++]);
	}
	fu(i,1,m+1)minize(ans,sumpress-arrcnt[i]);
	//if(ans==oo)ans=0;
	pr(ans);
	re 0;
	// Hack it if you can :)
}
int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Solves();
}

Measured memory_bytes: 5872
from math import pi
from decimal import Decimal, ROUND_HALF_UP


def resolve():
    r = float(input())

    a = Decimal(r * r * pi).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP)
    c = Decimal(r * 2 * pi).quantize(Decimal('0.000010'), rounding=ROUND_HALF_UP)
    print(a, c)


resolve()


Measured memory_bytes: 6476
#define SUBMIT

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef SUBMIT
    auto& in = cin;
#else
    stringstream in(R"(19 0
)");
#endif
    int A, B;
    in >> A >> B;
    auto ans = (A + B) % 24;
    cout << ans << endl;
    return 0;
}

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

 
int main(){
   long long int n,sum=0;
   scanf("%lld", &n);
   for(int i=1;i<=n;i++){
     if(i%3==0 || i%5==0){
     	;
     }else{
        sum = i+sum;
     }
   }
   printf("%lld", sum);
   return 0;
 
}

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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列 -92
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}



int main(){
    int k;
    cin >> k;
    ll ans = 0;

    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            ll x = gcd(i,j);
            for(int s=1;s<=k;s++){
                ans += gcd(x,s);
            }
        }
    }

    cout << ans << endl;
}

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

int A[210];
int B[210];

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

  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  for (int j = 0; j < M; ++j) {
    cin >> B[j];
  }

  sort(A, A + N, greater<int>());
  sort(B, B + M);

  bool can = false;

  for (int k = X+1; k <= Y; ++k) {
    if ((k > A[0]) && (k <= B[0])) {
      can = true;
    }
  }

  if (can) {
    cout << "No War" << endl;
  } else {
    cout << "War" << endl;
  }
}

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

int main()
{
    string s;
    string ans;
    cin >> s;

    if( s == "Sunny"){
    printf("Cloudy");
    }else if(s == "Cloudy" ){
    printf("Rainy");
    }else{
    printf("Sunny");
    }
}

Measured memory_bytes: 256
n,m = map(int,input().split())
l = []
for i in range(n):
    l.append(list(map(int,input().split())))
l = sorted(l)
p = 0
d = 0
i = 0
while(d < m):
    s = min(l[i][1],m-d)
    d += s
    p += l[i][0] * s
    i += 1
print(p)

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

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

    ll ans = 1;
    bool overflow = false;
    rep(i, n) {
        ll a;
        cin >> a;
        if (a == 0) {
            cout << 0 << endl;
            return 0;
        }
        ll now = ans;
        ans *= a;
        if (now != ans / a) overflow = true;
    }

    if (overflow || ans > 1000000000000000000)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
using namespace std;
 
int main() {
	char s[2000001];
	long int bb[2000001];
	cin >> s;
	long int n = 0, l = 0;
	while (s[n]) {
		if (s[n] == 'B') {
			bb[l] = n;
			l++;
		}
		n++;
	}
	long int i;
	long int sum = 0;
	for (i = 1; i <= l; i++) {
		sum += (n - i) - bb[l - i];
	}
	cout << sum << endl;
}

Measured memory_bytes: 5888
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  
  for(int i=0;i<5;i++){
    cout << s.at(i);
  }
  
  cout << " ";
  
  for(int i=6;i<13;i++){
    cout << s.at(i);
  }
  
  cout << " ";
  
  for(int i=14;i<19;i++){
    cout << s.at(i);
  }
  
}
  

Measured memory_bytes: 256
from collections import Counter

N, M = map(int, input().split())

adj = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

group = [0] * N
ng = 1
for i in range(N):
    if group[i] == 0:
        group[i] = ng
        stack = [i]
        while stack:
            pos = stack.pop()
            for nv in adj[pos]:
                if group[nv] == 0:
                    group[nv] = ng
                    stack.append(nv)
        ng += 1

print(max(v for k, v in Counter(group).items()))

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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define X first
#define Y second

typedef pair<int,int> P;
int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};

void solve(int N) {
    int max_x=0, min_x=0, max_y=0, min_y=0;
    vector<P> data; 
    data.pb(mp(0,0));
    rep(i,N-1) {
        int n,d; cin>>n>>d;
        int x = data[n].X + dx[d];
        int y = data[n].Y + dy[d];
        data.pb(mp(x,y));
        max_x = max(max_x, x);
        max_y = max(max_y, y);
        min_x = min(min_x, x);
        min_y = min(min_y, y);
    }
    int width = max_x - min_x + 1;
    int height = max_y - min_y + 1;
    cout << width << " " << height << "\n";
}

int main() {
    int N;
    while(cin>>N, N) solve(N);
    return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define x first
#define y second
#define u(i,a,b) for(int i=a;i<b;i++)
using namespace std;
pair<int,int> p[12];
bool t[1010][1010],v[1010][1010];
queue<pair<int,pair<int,int> > >Q;
int main(){
	int h,w,k,a=0,dx[]={0,1,0,-1},dy[]={1,0,-1,0};cin>>h>>w>>k;
	u(i,0,h)u(j,0,w){t[i][j]=1;char z;cin>>z;
		if(z=='X')t[i][j]=0;if(z=='S')p[0]=make_pair(i,j);
		if(z>'0'&&z<='9')p[z-'0']=make_pair(i,j);
	}
	u(r,0,k){Q.push(make_pair(0,p[r]));u(i,0,h)u(j,0,w)v[i][j]=0;v[p[r].x][p[r].y]=1;
		while(1){int L=Q.front().x,Y=Q.front().y.x,X=Q.front().y.y;
			if(Y==p[r+1].x&&X==p[r+1].y){a+=L;break;}
			u(i,0,4){int f=Y+dy[i],g=X+dx[i];if(f+1&&f<h&&g+1&&g<w){
				if(t[f][g]==1&&v[f][g]==0){v[f][g]=1;Q.push(make_pair(L+1,make_pair(f,g)));}
			}}Q.pop();
		}while(!Q.empty())Q.pop();
	}cout<<a<<endl;return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  int n2 = n / 2;
  if (n % 2 == 1) {
    cout << b[n2] - a[n2] + 1 << endl;
  } else {
    cout << b[n2] + b[n2 - 1] - a[n2] - a[n2 - 1] + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 4852
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;
int main() {
  int a,b;  
  string c;
  cin >> a >> b >> c;
  b--;
  if (c[b] == 'A') {
    c[b] = 'a';
  } else if(c[b] =='B'){
    c[b] = 'b';
  }else{
    c[b] = 'c';
  }

  cout << c;
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
  //配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


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

using namespace std;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int k, n;
	cin >> k >> n;

	vector<int> a(n + 5), f(n + 5);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		f[i] = a[i] - a[i - 1];
	}

	f[n + 1] = k - a[n] + f[1];
	f[1] = f[n + 1];

	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++) {
		ans = min(ans, k - max(f[i], f[i + 1]));
	}

	cout << ans;

	return 0;
}



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

count = 0
ans = 1
bef = 0
buff = True
for i in A:
    if count == 0:
        count = 1
    elif count == 1:
        if bef < i:
            count += 1
            buff = True
        elif bef > i:
            count += 1
            buff = False
        else:
            pass
    else:
        if buff:
            if bef <= i:
                pass
            else:
                ans += 1
                count = 1
        else:
            if bef >= i:
                pass
            else:
                ans += 1
                count = 1
    bef = i
print(ans)


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

long long n,mod,l,DP[5005][5005];
string s;

long long sqr(long long x){
    return (x*x)%mod;
}

long long pangkat(long long a,long long b){
    if(b==1)
        return a;
    if(b==0)
        return 1;
    if(b%2==0)
        return sqr(pangkat(a,b/2))%mod;
    if(b%2==1)
        return (a*sqr(pangkat(a,(b-1)/2))%mod)%mod;
}


long long bit(long long x,long long y){
    if(y==0){
        if(x==l)
            return 1;
        else
            return 0;
    }
    if(DP[x][y]==-1){
        if(x>0)
            DP[x][y]=((2*bit(x+1,y-1))%mod+bit(x-1,y-1)%mod)%mod;
        else
            DP[x][y]=((2*bit(x+1,y-1))%mod+bit(x,y-1)%mod)%mod;
    }
    return DP[x][y];
}

int main(){
    cin>>n;
    cin>>s;
    memset(DP,-1,sizeof DP);
    mod=1e9+7;
    l=s.length();
    //cout<<pangkat(3,4);
    cout<<(((bit(0,n))%mod)*(pangkat(2,(l*(mod-2)))%mod))%mod<<"\n";
}


Measured memory_bytes: 196224
#include <iostream>
#include <set>

using namespace std;

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  int N;
  set<int> ds;
  cin >> N;
  for (int i=0; i<N; ++i) {
    int d; cin >> d;
    ds.insert(d);
  }

  cout << ds.size() << "\n";
  return 0;
}

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

int reverse(int i) {
  int rev_i = 0;
  while (i != 0) {
    rev_i *= 10;
    rev_i += i % 10;
    i /= 10;
  }
  return rev_i;
}

int main() {
  int a, b;
  cin >> a >> b;
  int num = 0;
  for (int i = a; i <= b; i++) {
    if (reverse(i) == i) {
      num++;
    }
  }
  cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>


using namespace std;

int main() {
	int n;
	cin >> n;
	vector<string> v;
	vector<int> snum;
	string ans;
	for (int i = 0; i < n; i++)
	{
		string tmp;
		cin >> tmp;
		v.emplace_back(tmp);
	}
	for (size_t i = 0; i < n; i++)
	{
		snum.emplace_back(v[i].length());
	}
	auto itrrrr = min_element(snum.begin(), snum.end());

	size_t index = std::distance(snum.begin(), itrrrr);

	iter_swap(v.begin(), v.begin() + index);


	for (size_t i = 0; i < v[0].length(); i++)
	{
		if (n == 1)
		{
			ans = v[0];
			break;
		}
		bool flag = false;
		for (size_t j = 0; j < v.size()-1; j++)
		{
			auto itrr = v[j + 1].find(v[0].at(i));
			if (itrr != -1)
			{
				v[j + 1].erase(v[j + 1].begin() + itrr);
			}
			else
			{
				break;
			}
			if (j == v.size()-2)
			{
				ans.push_back(v[0].at(i));
			}
		}
	}

	sort(ans.begin(), ans.end());
	cout << ans << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define N 100010
using namespace std;
bool ip[N+10];
int sum[N+10],p[N+10];
void pre(){
	for (int i=2;i<=N;++i){
		if (!ip[i]) p[++p[0]]=i;
		for (int j=1;j<=p[0];++j){
			if (i*p[j]>N) break;
			ip[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}
int main(){
//	freopen ("1.in","r",stdin);
	pre();
	for (int i=2;i<=N;++i){
		sum[i]=sum[i-1];
		if ((i%2==1)&&(!ip[i])&&(!(ip[(i+1)/2])))sum[i]++;
	}
	int Q,l,r;scanf ("%d",&Q);
	while (Q--){
		scanf ("%d%d",&l,&r);
		printf ("%d\n",sum[r]-sum[l-1]);
	}
	return 0;
}

Measured memory_bytes: 1152
from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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


def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=l//x

print(ans%m)

Measured memory_bytes: 6132
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define _USE_MATH_DEFINES
#define mp       make_pair
#define pb       push_back
#define fst      first
#define snd      second
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const int MOD=1000000007;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};


int main()
{
    map<string,int> cards;

    int N; cin >> N;
    string s;
    rep(i,N) {
        cin >> s;
        if(cards.find(s) == cards.end())
            cards[s] = 0;
        cards[s]++;
    }

    int M; cin >> M;
    string t;
    rep(i,M) {
        cin >> t;
        if(cards.find(t) == cards.end())
            cards[t] = 0;
        cards[t]--;
    }

    int ans = 0;
    for(auto p : cards) {
        ans = max(ans, p.second);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define PII pair<int, int>
using namespace std;
int main(){
    LL k;scl(k);
    if(k%2==0||k%5==0)cout<<"-1"<<endl;
    else{
        int cnt=1;
        LL bas=7;
        while(1){
            if(bas%k==0){
                cout<<cnt<<endl;
                break;
            }
            bas=bas*10+7;
            bas=bas%k;
            cnt++;
        }
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 3824
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;
#define MOD 1000000007
#define ll long long
const long long INF = 1LL << 60;

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

class UnionFind {
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int find(vector<long long> &arr, long long obj) {
	if (arr[arr.size() - 1] < obj)return arr.size()-1;
	if (arr[0] > obj)return -1;

	int min = 0; int max = arr.size() - 1;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[min+(max-min) / 2] > obj) {
			max = min + (max - min) / 2;
		}
		else {
			min = min + (max - min) / 2;
		}
		if (max - min == 1) {
			return min;
		}
	}


}

//約数求める //約数
void divisor(ll n,vector<ll> &ret) {
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(ret.begin(), ret.end());
	
}
//階乗
long long factorial(long long n, long long mod) {
	long long ret = 1;
	for (long long i = 1; i <= n; i++) {
		ret = (ret * i) % mod;
	}
	return ret;
}
//モジュラ逆数
long long inv_mod(long long n, long long mod) {
	long long a = n % mod, b = mod - 2, ret = 1;
	while (b > 0) {
		if (b & 1) ret = (ret * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ret;
}

long long nPr(long long n, long long r, long long mod) {
	long long ret = 1;
	for (long long i = n; i >= n - r + 1; i--) {
		ret = ret * (i % mod) % mod;
	}
	return ret;
}

long long nCr(long long n, long long r, long long mod) {
	return nPr(n, r, mod) * inv_mod(factorial(r, mod), mod) % mod;
}



int main() {
	int A, B;
	cin >> A >> B;
	if (A % 2 == 1 && B % 2 == 1) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}


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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

int main() {
  int N; cin>>N;
  int Z = 0;
  map<pair<ll,ll>,P> M;
  rep(i,N){
      ll x,y; cin>>x>>y;
      if(x==0&&y==0){
          Z++;
          continue;
      }
      ll g = gcd(x,y);
      x /= g;
      y /= g;

      if(y<0) x = -x, y = -y;
      if(y==0&&x<0) x = -x, y = -y;
      bool rotation = (x<=0);//第二象限
      if(rotation){
          ll tmp = x;
          x = y;
          y = -tmp;
      }
      if(rotation)M[{x,y}].second++;
      else M[{x,y}].first++;
  }

  mint res = 1;
  for(auto p: M){
      ll x = p.first.first, y = p.first.second;
      int s = p.second.first;
      int t = p.second.second;
      mint tmp = 1;
      tmp += mint(2).pow(s) - 1;
      tmp += mint(2).pow(t) - 1;
      res *= tmp;      
  }
  res = res + Z - 1;
  cout<<res<<endl;
}


Measured memory_bytes: 15976