akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static List<int>[] li;
	static bool[] b;
	static int[] h;
	static int k,ans=0;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.Ia;
		int n=s[0];
		k=s[1];
		li=new List<int>[n+1];
		b=new bool[n+1];
		h=new int[n+1];
		var a=sc.Ia2;
		for(int i=1;i<=n;i++){li[i]=new List<int>();}
		for(int i=2;i<=n;i++){
			li[a[i]].Add(i);
		}
		Fu(1,1);
		if(a[1]!=1){ans++;}
		Console.WriteLine("{0}",ans);
	}
	static int Fu(int a,int g){
		b[a]=true;
		int p=1;
		for(int i=0;i<li[a].Count;i++){
			if(!b[li[a][i]]){
				p=Max(Fu(li[a][i],a)+1,p);
			}
		}
		if(p==k&&g!=1){
			ans++;
			p=0;
		}
		return p;
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 43680
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
int n , mod , now , ans , base = 1;
string s;
map<int , int>vis;
signed main()
{
	cin >> n >> mod >> s ;
	if(mod == 2 || mod == 5)
	{
		for(int i = 0 ; i < n ; i ++)
		{
			int x = s[i] - '0';
			if(x % mod == 0) ans += i + 1 ;
		}
		return cout << ans << '\n' , 0;
	}
	reverse(s.begin() , s.end()) , vis[0] = 1;	
	for(auto i : s)
	{
		int x = i - '0';
		now = (now + x * base) % mod;
		ans += vis[now]; 
		vis[now] ++ , base *= 10 , base %= mod;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 1028
N = int(input())
h = list(map(int, input().split()))

def dp(n):
  a, b = 0, abs(h[1]-h[0])
  if n == 0:
    return a
  for i in range(2, n+1):
    a, b = b, min(a+abs(h[i]-h[i-2]), b+abs(h[i]-h[i-1]))
  return b
 
print(dp(N-1))

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

int main()
{
ll n , x ;
cin >> n >> x ;
ll a=x,b=n-x;
ans+=n;
while(1){
  if(b>a){
    ans+=b/a*2*a;
    b=b%a;
  }
  else{
    ans+=a/b*2*b;
    a=a%b;
  }
  if(a*b==0){
    ans-=max(a,b);
    break;
  }
}
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
l = input().split()
stack = []
for op in l:
    if op.isdigit():
        stack.append(int(op))
    elif op == '+':
        stack.append(stack.pop() + stack.pop())
    elif op == '-':
        stack.append(- stack.pop() + stack.pop())
    elif op == '*':
        stack.append(stack.pop() * stack.pop())
print(stack[-1])

Measured memory_bytes: 7684
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int i,j;
char reval(int num)
{
 if(num>=0 && num<=9) return (char)(num +'0');
    else return (char)(num-10+'A');
}
char* fromdeci(char res[],int base,int inputnum)
{
    int index=0;
    while(inputnum>0)
    {
        res[index++]=reval(inputnum%base);
        inputnum/=base;
    }
    res[index]='\0';
    return res;
}
main()
{
int inputnum=282,base=16;
cin>>inputnum>>base;
char res[100];
//cout<<"Equivalent of "<<inputnum<<" in base "<<
fromdeci(res,base,inputnum);
cout<<strlen(res)<<endl;

}



Measured memory_bytes: 256
if __name__ == '__main__':
    n, = map(int, input().split())
    # print(n)
    q = list(range(1, 10))
    count = 0
    while True:
      a = q.pop(0)
      count += 1
      if count == n:
        print(a)
        break
      end = a % 10
      end_1 = end - 1
      end_2 = end + 1
      if end_1 >= 0:
        q.append(10*a + end_1)
      q.append(10*a + end)
      if end_2 <= 9:
        q.append(10*a + end_2)
      

Measured memory_bytes: 19348
import fractions
N, X = map(int, input().split())
array = list(map(int, input().split()))
diff = [0] * N
if N == 1:
    print(abs(array[0] - X))
    exit()
for i in range(N):
    diff[i] = abs(array[i] - X)
ans = diff[0]
for i in range(1,N):
    ans =fractions.gcd(ans,diff[i])
print(ans)

Measured memory_bytes: 16296
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  string j = "Three";
  for (int i =0; i < N; i++) {
    char c;
    cin >> c;
    if(c == 'Y') {
      j = "Four";
      break;
    }
  }
  cout << j << endl;
}

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

int main(){
   
    int N;
    cin>>N;
    vector<long long int> S(3*N);
    for(int i=0;i<3*N;i++){
        cin>>S[i];
    }
    sort(S.begin(),S.end());
    long long int ans=0;
    for(int i=3*N-2;i>=N;i-=2){
        ans+=S[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
        int cardCount = (int)inpt[0];

        long xPoint = inpt[1];
        long yPoint = inpt[2];

        inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
        long ans = 0;
        if(cardCount==1) {
            ans = Math.Abs(inpt[0] - yPoint);
        } else {
            ans = Math.Max(Math.Abs(inpt.Last() - yPoint), Math.Abs(inpt[inpt.Length - 2] - inpt.Last()));
        }
        Console.WriteLine(ans);
    }

    public class Reader
    {
        private static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"





3 100 100
10 1000 100




";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 13420
#pragma GCC optimize("O2")
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <functional>
#include <numeric>
#include <algorithm>
using namespace std;
#define mod 1000000007

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n , m ;
	cin >> n >> m ;
	vector<long long> h(n);
	for (int i = 0 ; i < n ; i++) {
		cin >>  h[i] ;
	}
	vector<int> ans(n, 1);
// vector<int> a(m+1) , b(m+1) ;
	for (int i = 0 ; i < m ; i++) {
		int l , r ;
		cin >> l >>  r ;
		--l , --r ;
		if (h[l] <= h[r]) ans[l] = 0 ;
		if (h[l] >= h[r]) ans[r] = 0 ;

	}
	cout << accumulate(ans.begin(), ans.end(), 0) << "\n";



	return 0 ;
}


Measured memory_bytes: 4484
Program Batcoder4;
//uses crt;
var A:array[1..100,1..100] of longint;
    n,d,i,j,k,sum,cnt :longint;
    f:text;
//------------------------------------
begin
//clrscr;
//assign(f,'Batcoder4.inp');
//reset(f);
readln(n,d);
for i:=1 to n do begin
                 for j:=1 to d do begin
                                  Read(A[i,j]);
                                  end;
                 end;
for i:=1 to n-1 do
for j:=i+1 to n do begin
                   sum:=0;
                   for k:=1 to d do begin
                                    sum:=sum+sqr(A[i,k]-A[j,k]);
                                    end;
                   if sqr(trunc(sqrt(sum)))=sum then inc(cnt);
                   end;
Writeln(cnt);
//readln;
end.


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll n;
    cin >> n;
    ll a[n];
    rep(i, n) { cin >> a[i]; }
    ll q;
    cin >> q;
    ll b[q], c[q];
    rep(i, q) { cin >> b[i] >> c[i]; }

    ll ans = 0;
    map<ll, ll> m;
    rep(i, n) {
        ans += a[i];
        m[a[i]]++;
    }

    rep(i, q) {
        ll num_before = b[i], num_after = c[i];

        ans -= num_before * m[num_before];
        ans += num_after * m[num_before];

        m[num_after] += m[num_before];
        m[num_before] = 0;

        cout << ans << endl;
    }

    return 0;
}



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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for (int i = a; i < (int)b; ++i)
#define rrep(i, n) for (int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
    
    return 0;
}



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



int main() {
	string s;
	char before;
	bool frag = false;
	cin >> s;
	before = s[0];
	for (int i = 1; i < 4; i++) {
		if (s[i] == s[i - 1]) {
			cout << "Bad" << endl;
			frag = true;
			break;
		}
	}
	if (!frag) {
		cout << "Good" << endl;
	}
}


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

int main(){
	int X;
	cin >> X;
	int p = sqrt(X);
	if (X == p*p) {
		cout << X << endl;
		return 0;
	}
	int ans = 1;
	for (int i = 2; i <= p; i++) {
		int test = 1;
		int j = 2;
		while (test <= X) {
			test = pow(i,j);
			j++;
		}
		ans = max(ans,test/i);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4052
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
    public static void Main()
    {
        var n = ReadLine().Split().Select(int.Parse).ToArray();
        if(n[1] < 1)
        {
            WriteLine(n[0]);
            return;
        }
        HashSet<int> list = new HashSet<int>();
        for(int i = -1; i <= 102; i++)
        {
            list.Add(i);
        }
        var m = ReadLine().Split().Select(int.Parse).ToArray();
        for(int i = 0; i < m.Length; i++)
        {
            list.Remove(m[i]);
        }
        if(list.Contains(n[0]))
        {
            WriteLine(n[0]);
            return;
        }
        for(int i = 1; i <= 102; i++)
        {
            if(n[0] - i >= -1)
            {
                if(list.Contains(n[0] - i))
                {
                    WriteLine(n[0] - i);
                    return;
                }
            }
            if(n[0] + i <= 102)
            {
                if(list.Contains(n[0] + i))
                {
                    WriteLine(n[0] + i);
                    return;
                }
            }
        }
    }
}


Measured memory_bytes: 20340
#include<iostream>

using namespace std;

int main() {
	int n, day, x, *ai, choco = 0, i, value;
	
	cin >> n >> day >> x;

	ai = new int[n];

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

	choco = n + x;

	for (i = 0; i < n; i++) {
		choco += (day - 1) / ai[i];
	}

	cout << choco;

	return 0;
}

Measured memory_bytes: 384
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
// #define int unsigned long long int
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int mul1 = 1003, mul2 = 5, mul3 = 8;
const int MOD3 = 179424673, MOD2 = 982451653, MOD1 = 1190494759;
const ld EPS = 1e-9;
 
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=10*xx+ch-'0';ch=getchar();}
    return xx*ff;
}
 
ull hasher(ull a, ull b) {
    return 14831553208299411291ull * (a ^ 16184882973064831860ull) + b;
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n;
const int LIM = 2e5+5;
string s[LIM];
map<ull, int> m;
 
int main(){
    fastio;
 
    cin>>n;
 
    ll ans = -n;
 
    forn(i,n){
        cin>>s[i];
        reverse(s[i].begin(), s[i].end()); 
        
        ull h1 = 0;
        forn(j,s[i].length()){
            h1 = hasher(h1, s[i][j]);
        }
        ++m[h1];
    }


    forn(i,n) {
        int num[26] = {0};
        forn(j,s[i].length()){
            ++num[s[i][j]-'a'];
        }

        ull h1 = 0;
        forn(j,s[i].length()){
            forn(k,26){
                if (num[k]) {
                    ull n1 = hasher(h1, k+'a');
                    
                    auto it = m.find(n1);
                    if (it != m.end())
                        ans += (*it).second;
                }
            }
            h1 = hasher(h1, s[i][j]);
            --num[s[i][j]-'a'];
        }
    }
 
    cout<<ans<<ln;
    return 0;
}


Measured memory_bytes: 22264
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		int first = 0;
		int second = 0;
		int third = 0;
		int input;
		while(cin.hasNextInt()) {
			input = cin.nextInt();
			
			if(input > third) {
				if(input > second) {
					if(input > first) {
						third = second;
						second = first;
						first = input;
					} else {
						third = second;
						second = input;
					}
				} else {
					third = input;
				}
			}
		}
		
		System.out.println(first);
		System.out.println(second);
		System.out.println(third);
	}
}

Measured memory_bytes: 12000
//----AUTHOR:kkdrummer----/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include<ext/rope>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> P;
#define X real()
#define Y imag()
ld restant(P p){return abs(p);}
//polar(x,y) mag=l,arg=y
//typedef unordered_set<ll> usll;
//typedef unordered_multiset<ll> umsll;
typedef multiset<ll> msll;
typedef set<ll> sll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pair<ll,ll> > vpll;
typedef priority_queue<ll> pqll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
//typedef unordered_multiset<int> umsi;
//typedef unordered_set<int> usi;
typedef pair<int,int> pi;
typedef vector<pair<int,int> > vpi;
typedef vector<pair<double,double> > vpd;
typedef pair<double,double> pd;
typedef priority_queue<int> pqi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ind_set;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ind_setll;
#define in insert
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define be begin
#define en end
#define itr iterator
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mo 1000000007
#define inf 1000000000000000001
#define ninf -1000000000000000001
#define ima INT_MAX
#define imi INT_MIN
#define oncnt __builtin_popcount
#define zerobegin __builtin_clz
#define zeroend __builtin_ctz
#define parity __builtin_parity
#define all(x) x.be(),x.en()
#define eps 1e-9
const ld pii=3.14159265359;
inline ll modpow(ll x,ll n){if(n==0)return 1;if(n==1)return(x%mo);ll u=(modpow(x,n/2));u=(u*u)%mo;if(n%2!=0)u=(u*x%mo)%mo;return u;}
inline ll modinv(ll x){return modpow(x,mo-2);}
inline ll mmul(ll a,ll b){    if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll madd(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a+b>=mo)return(a+b)%mo;return(a+b);}
inline ll msub(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;return((a-b+mo)%mo);}
inline ll mdiv(ll a,ll bb){if(a>=mo)a=a%mo;ll b=modinv(bb);if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll gcd(ll a,ll b){return __gcd(a,b);}

const int NM=200001;
ll factmod[NM];
ll factmodinv[NM];
void ncrprecal()
{
    factmodinv[0]=1;
    factmod[0]=1;
    for(ll i=1;i<NM;i++)
    {
        factmod[i]=(i*factmod[i-1])%mo;
        factmodinv[i]=modinv(factmod[i]);
    }
}

ll ncrmodp(ll n,ll r){if(r==0||n==r)return 1;if(n<r)return 0;return mmul(mmul(factmod[n],factmodinv[r]),factmodinv[n-r]);}

int main()
{
io
ncrprecal();
int testcases=1;//cin>>testcases;
while(testcases--)
{	
ll n,m,l,r;
cin>>n>>m>>l>>r;
ll ans=0;

for(ll i=m;i>=m-(m-r)+1;i--)
{//cout<<n-l<<" "<<i<<"\n";
//cout<<l<<" "<<n-l-i+1<<"\n\n";
	ans=madd(mmul(ncrmodp(n-l+i-2,n-l-1),ncrmodp(l+(m-i+1)-2,l-1)),ans);
}
cout<<ans;


}return 0;}

Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const double PI = acos(-1);

ll gcm(ll x, ll y) {
	int r = 0;
	if (x<y) swap(x, y);

	while (y > 0) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}
/* 3つ以上の最大公約数を求めるには再帰的に処理する必要があります。
ll ans = gcm(gcm(x,y),z);
*/


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, X;
	cin >> N >> X;
	int f;
	cin >> f;
	int igcm = abs(f-X);
	REP(i, N-1) {
		int x;
		cin >> x;
		igcm = gcm(igcm, abs(x-X));
	}
	cout << igcm << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> mpair;
int main(){
  ll n,k;cin>>n>>k;
  ll a[n],ans=0,co=0;
  ll b[n];fill(b,b+n,0);
  for(int i=0;i<n;i++){
    cin >>a[i];
  }
  sort(a,a+n);
  for(int i=0;i<n;i++){
    b[a[i]-1]++;
  }
  sort(b,b+n);
  for(int i=n-1;i>=0;i--){
    if(co>=k){
      ans+=b[i];
    }
    co++;
  }
  cout<< ans<<endl;
}

Measured memory_bytes: 6776
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 4000 + 5 ; 
int n, a[N], b[N], nxt[N], pre[N], sum[N], R[N], Ans, top ; 
char A[N], B[N] ;
struct node {
	int l, r ; 
} st[N] ;
bool cmp( node x, node y ) {
	return x.l < y.l ; 
}
void solve() {
	int m = 2 * n ; nxt[m + 1] = m + 1 ; 
	drep( i, 1, m ) nxt[i] = ( b[i] ) ? i : nxt[i + 1] ;
	rep( i, 1, m ) pre[i] = (b[i]) ? i : pre[i - 1] ;
	rep( i, 1, m ) sum[i] = sum[i - 1] + b[i] ; 
	rep( de, 0, n ) { 
		int num = n, ans = de, u ; top = 0 ;
		rep( i, 1, n ) { 
			if( a[i] == b[i - de + n] ) continue ; 
			++ ans, u = sum[i + n] - sum[i + n - de - 1] ; 
			if( !u ) {
				++ top, st[top].r = nxt[i] - i, st[top].l = ( i + n - de ) - pre[i + n - de] ;
			}
		}
		sort( st + 1, st + top + 1, cmp ) ;
		
		drep( i, 1, top ) R[i] = max( R[i + 1], st[i].r ) ;
		rep( i, 0, top ) num = min( num, st[i].l + R[i + 1] ) ;
		rep( i, 0, top ) R[i] = 0 ;
		Ans = min( Ans, num * 2 + ans ) ;
	}
}
signed main()
{
	scanf("%s", A + 1 ), scanf("%s", B + 1 ), n = strlen(A + 1) ;
	int fl = 0, fA = 0 ;
	rep( i, 1, n ) a[i] = A[i] - '0', b[i] = B[i] - '0', b[i + n] = b[i], fl += b[i], fA += a[i] ; 
	if( !fl ) {
		if( !fA ) cout << "0" << endl ; 
		else cout << "-1" << endl ; exit(0) ; 
	}
	Ans = 4 * n, solve() ; 
	rep( i, 1, n ) if( (n - i) > i ) swap( a[i], a[n - i] ), swap( b[i], b[n - i] ) ;
	rep( i, 1, n ) b[i + n] = b[i] ; 
	solve() ;
	printf("%d\n", Ans ) ;
	return 0 ;
}

Measured memory_bytes: 512
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

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

//マクロ
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007    //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

// debug
#define DEBUG(x) cout << #x << ": " << x << endl
#define DEBUG2(x, y) cout << #x << ": " << x << " " << #y << ": " << y << endl
#define DEBUG_VEC(v)   \
  cout << #v << ":";   \
  REP(i, v.size())     \
  cout << " " << v[i]; \
  cout << endl
#define DEBUG_ARR(v, n) \
  cout << #v << ":";    \
  REP(i, n)             \
  cout << " " << v[i];  \
  cout << endl

signed main()
{
  string s;
  ll k;
  cin >> k;
  cin >> s;

  if (s.length() <= k)
  {
    cout << s << endl;
    return 0;
  }
  string sub = s.substr(0, k);
  cout << sub << "..." << endl;

  return 0;
}

Measured memory_bytes: 3632
H,W=map(int,input().split(' '))
a = [list(input()) for i in range(H)]
tmp = []
ans = []
for i in a:
    if i != ['.']*W:
        tmp.append(i)
for i in range(W):
    l = [tmp[j][i] for j in range(len(tmp))]
    if l != ['.']*len(tmp):
        ans.append(l)
for i in range(len(ans[0])):
    print(''.join([ans[j][i] for j in range(len(ans))]))

Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main()
{
    int n , k;
    cin >> n >> k;
    int r = n - 2;
    if(k > r * (r + 1) / 2)
    {
        cout << -1;
        return 0;
    }
    int m = n - 1;
    int p = r * (r + 1) / 2 - k;
    cout << m + p << endl;
    for(int i = 2; i <= n; i ++)
        cout << i << ' ' << 1 << endl;
    if(p == 0)
        return 0;
    for(int i = 2; i < n; i ++)
        for(int j = i + 1; j <= n; j ++)
        {
            cout << i << ' ' << j << endl;
            p --;
            if(p == 0)
                return 0;
        }
    return 0;
}


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

using namespace std;

int arr[100001];
int parent[100001];

int find(int a)
{
	if (a == parent[a])
		return a;
	return parent[a] = find(parent[a]);

}

void Union(int a, int b)
{
	int num1 = arr[a];
	int num2 = arr[b];

	num1 = find(num1);
	num2 = find(num2);

	parent[num1] = num2;

	arr[a] = num2;
}
int main()
{

	ios_base::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		parent[i] = i;
	}
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}
	for (int i = 1; i <= n; i++)
	{
		parent[i] = find(i);
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (find(arr[i]) == parent[i])
			ans++;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define INF 987654321

int a[10050];

int main() {
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            for (int k = 1; k <= 100; k++) {
                if (i * i + j * j + k * k + i * j + j * k + k * i <= 10050) {
                    a[i * i + j * j + k * k + i * j + j * k + k * i]++;
                } 
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3600
def c_sum_of_product_of_pairs(MOD=10**9 + 7):
    N = int(input())
    A = [int(i) for i in input().split()]

    total = sum(A)
    cumsum = [0]
    for i in range(N):
        cumsum.append(cumsum[-1] + A[i])

    return sum([(total - cumsum[i]) * A[i - 1] for i in range(1, N)]) % MOD

print(c_sum_of_product_of_pairs())

Measured memory_bytes: 39644
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define FOR(idx, begin, end) for(int idx = (int)(begin); idx < (int)(end); ++idx)
#define DMP(x) cerr << #x << ": " << x << "\n"

using namespace std;
typedef long long lint;
const int MOD = 1000000007;


int main() {

	cin.tie(0);
	
	string str;
	cin >> str;

	int A;

	FOR(i, 0, str.length()) {
		if (str[i] == 'A') {
			A = i;
			break;
		}
	}

	FOR(i, 0, str.length()) {
		if (str[str.length() - 1 - i] == 'Z') {
			
			cout << str.length() - i -A;
			return 0;
		}
	}
	return -1;
}

Measured memory_bytes: 640
local mma = math.max
local msq = math.sqrt
local n = io.read("*n")
local x, y = {}, {}
for i = 1, n do
  x[i], y[i] = io.read("*n", "*n")
end
local rep = 1000

local tx, ty = 0, 0
local function solvex(px)
  tx = px
  local sq = 0
  for i = 1, n do
    local tmp = (tx - x[i]) * (tx - x[i]) + (ty - y[i]) * (ty - y[i])
    sq = mma(sq, tmp)
  end
  return sq
end

local function triplediv(xmin, xmax, rep, func)
  local left_v, right_v = func(xmin), func(xmax)
  for i = 1, rep do
    local xmid1, xmid2 = (xmin * 2 + xmax) / 3, (xmin + xmax * 2) / 3
    local mid_v1, mid_v2 = func(xmid1), func(xmid2)
    if left_v > mid_v1 then
      if mid_v2 > right_v then
        xmin = xmid2
        left_v = mid_v2
      elseif mid_v1 > mid_v2 then
        xmin = xmid1
        left_v = mid_v1
      else
        xmax = xmid2
        right_v = mid_v2
      end
    else
      if mid_v2 < right_v then
        xmax = xmid1
        right_v = mid_v1
      elseif mid_v1 < mid_v2 then
        xmin = xmid1
        left_v = mid_v1
      else
        xmax = xmid2
        right_v = mid_v2
      end
    end
  end
  return (left_v + right_v) / 2
end

local function solvey(py)
  ty = py
  return triplediv(0, 1000, rep, solvex)
end

local ret = triplediv(0, 1000, rep, solvey)
print(string.format("%.10f", msq(ret)))


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

#define foreach(i,v) for(auto&& i: v)
#define all(x) (x).begin(), (x).end()

typedef std::vector< std::string > VS;
typedef std::vector<int> VI;
typedef long long ll;

template <class C> C& mini(C& a, C b) { if (b < a) a = b; return a; }
template <class C> C& maxi(C& a, C b) { if (a < b) a = b; return a; }

using namespace std;

template <typename T> void read(T& x) { x.read(); }
template <typename T> void read(vector<T>& v) { for (T& x: v) read(x); }
template <typename X, typename Y> void read(pair<X, Y>& p) { read(p.first); read(p.second); }
template <> void read(int& x) { scanf("%d", &x); }
template <> void read(unsigned int& x) { scanf("%u", &x); }
template <> void read(long long& x) { scanf("%lld", &x); }
template <> void read(unsigned long long& x) { scanf("%llu", &x); }
template <typename T> void readv(vector<T>& v) { int N; read(N); v.resize(N); read(v); }
template <typename T, typename ...Ts> void read(T& x, Ts&... args) { read(x); read(args...); }

#define MOD 1000000007

template <typename T>
void imfix(T& r) {
    if (r >= MOD)
        r -= MOD;
}

template <typename T>
T mfix(T r) {
    return r >= MOD ? r - MOD : r;
}

static int fact[100002];

int mpow(int a, int b) {
    ll r = 1;
    ll c = a;
    if (b == 0)
        return 1;
    while (b > 1) {
        if (b & 1)
            r = r * c % MOD;
        c = c * c % MOD;
        b >>= 1;
    }
    return r * c % MOD;
}

static int inv(int a) {
    return mpow(a, MOD-2);
}

static void initfact() {
    fact[0] = 1;
    for (int i = 1; i < sizeof(fact)/sizeof(fact[0]); i++)
        fact[i] = (ll)i * fact[i-1] % MOD;
}

//static VI calcD(const VI& A) {
//    VI ret;
//    ret.reserve(A.size());
//    for (int l = 1; l < A.size(); l++) {
//        ll r = 0;
//        for (int i = l; i < A.size(); i++) {
//            r += A[i] + MOD - A[i-l];
//        }
//        ret.push_back(r % MOD);
//    }
//    return ret;
//}

static VI calcD(const VI& A) {
    int N = A.size();
    VI ret(N-1);
    ret[0] = A[N-1] - A[0];

    for (int l = 2; l < N; l++) {
        int r = ret[l-2];
        imfix(r += A[N-1] - A[l-1]);
        imfix(r += MOD - (A[N-1] - A[N-l]));
        ret[l-1] = r;
    }

    return ret;
}

static VI calcP(int N) {
    VI ret;
    ret.reserve(N);
    for (int i = 1; i <= N; i++)
        ret.push_back((ll)fact[N] * inv(i) % MOD * inv(i+1) % MOD);
    return ret;
}

int main(int argc, const char* argv[]) {
    initfact();
    VI A;
    readv(A);
    int N = A.size() - 1;
    auto D = calcD(A);
    auto P = calcP(N);

    ll ret = 0;
    assert(D.size() == P.size());
    for (int i = 0; i < D.size(); i++)
        ret = (ret + (ll)D[i] * P[i]) % MOD;

    for (int i = 0; i < N; i++) {
        int m = N - i;
        ll dist = A[N] - A[i];
        ret = (ret + dist * ((ll)fact[N] * inv(m) % MOD + MOD - P[m-1])) % MOD;
    }

    printf("%lld\n", ret);

    return 0;
}


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

#define ll long long
#define mtv(kit) cout<<#kit<<" - "<<kit<<"\n";
#define ff first
#define ss second
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define pii pair<ll , ll>
#define all(x) x.begin(),x.end()
#define nl "\n"
#define ump unordered_map

void doit(){
	ll n,i,ans = 0;
	cin >> n;
	string s;
	cin >> s;
	rep(i,0,n-2){
		if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C')ans++;
	}
	cout << ans << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for(ll i = 1; i <= t; i++){
        doit();
    }
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <queue>
#include <iomanip>
#include <iterator>

#define MOD 1000000007
#define INF 1000000001

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


template <class T>
ostream &operator<<(ostream &o, const vector<T>&obj) {
    o << "["; for (int i = 0; i < (int)obj.size(); ++i) o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const pair<T, U>&obj) {
    o << "(" << obj.first << ", " << obj.second << ")"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const map<T, U>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const queue<T>&obj) {
    queue<T> obj_cp = obj;
    bool first = true;
    o << "{";
    while (!obj_cp.empty()) { o << (!first ? ", " : "") << obj_cp.front(); obj_cp.pop(); first = false; }
    o << "}"; return o;
}

void print() {
    cout << "\n";
}
template<class Head, class... Body>
void print(Head head, Body... body) {
    cout << head << " ";
    print(body...);
}


int main(int argc, char const *argv[]) {
    string S;
    cin >> S;
    if (S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }

    return 0;
}


Measured memory_bytes: 3628
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb emplace_back
#define koto_memory(a) cout<<(sizeof(a)/1048576.0)<<" MB";
#define res(v) sort(all(v)),v.erase(unique(all(v)), v.end());
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec "<<endl;
#define deb(x) cout<<endl<<"["<<#x<<" = "<<x<<"]"<<endl;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
void solve(){
  cout<<"ACL";
}
int32_t main()
{
  ibs;cti;
  // solve();return 0;
  int xx=0;
  int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<": "*/;solve();}
  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	string S, T;
	cin >> S >> T;
	string ans = "No";
	for(int i=0; i<S.length(); ++i){
		S = S[S.length()-1] + S;
		S.erase(S.length()-1);
		if(S==T) ans = "Yes";
	}
	cout << ans << endl;
}

Measured memory_bytes: 3628
import std.stdio;
//import std.string;
import std.array;
import std.algorithm;
import std.regex;
import std.container : SList;

void main() {
    char[] str;
    while((str = readln().dup).length != 0) {
        char[] ans = resolve(str);
        write(ans);
    }
}

char[] resolve(char[] str) {
    for (int c = 0; c < 'z'-'a' + 1; ++c) {
        for (int i = 0; i < str.length; ++i) {
            if ('a' <= str[i] && str[i] <= 'z') {
                if (str[i] == 'z') {
                    str[i] = 'a';
                } else {
                    str[i] += 1;
                }
            }
        }
        char[][] sxx = split(str);
        //if (contains_any(sxx, "the".dup, "this".dup, "that".dup)) {
        if (my_match(cast(immutable)str)) {
            break;
        }
    }
    return str;
}

bool my_match(string str) {
    if (match(str, r"the|this|that")) {
        return true;
    }
    return false;
}

bool contains_any(T, U...)(T[] arr, U elms) {
    foreach(elm ; elms) {
        if (!find(arr, elm).empty) {
            return true;
        }
    }
    return false;
}

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

int main() {
	string S;
	cin >> S;
	vector<int> alphabet(26);
	for (int i = 0; i < (int)S.size(); i++) {
		alphabet.at(S.at(i) - 'a')++;
	}

	for (int i = 0; i < 26; i++) {
		if (alphabet.at(i) == 0) {
			cout << (char)('a' + i) << endl;
			return 0;
		}
	}

	cout << "None" << endl;
}


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

 bool is_prime(int x){
   bool a = false;
   for (int i = 2; i * i <= x; i++){
     if (x % i == 0){
       a = true;
       break;
     }
     else{
       a=false;
     }
   }
 return a;
 }

 signed main(){
 int x;
 cin>>x;
 int p=x;
 while(is_prime(p)) p++;

 cout<<p<<endl;
 return 0;
 }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define push push_back
#define ii pair <int, int>
const int N = 2e5 + 7;
int dp[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    int t = 0;
    int i = n - 1;
    while (i >= 0) {
        if (s[i] == 'A') {
            ans += t;
            --i;
        }   
        else if (i && s[i - 1] == 'B' && s[i] == 'C') {
            ++t;
            i -= 2;
        }   
        else {
            t = 0;
            --i;
        }   
    }   
    cout << ans << '\n';
}   

Measured memory_bytes: 720
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll MOD = 1e9+7;
//LLONG_MIN



int main(void){
	int N,ans=1,type=0;
	ll A,B=-1;
	cin>>N;
	rep(i,N){
		cin>>A;
		if(B!=-1){
			if(B>A){
				if(type==2){
					ans++;
					B=-1;
					type=0;
				}else{
					type=1;
				}
			}else if(B<A){
				if(type==1){
					ans++;
					B=-1;
					type=0;
				}else{
					type=2;
				}
			}
		}
		B=A;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
	int a, b;
	cin >> a >> b;
	if (a < b){
		cout << "a < b" << endl;
	}else if (a > b){
		cout << "a > b" << endl;
	}else if (a == b){
		cout << "a == b" << endl;
	}
}

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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

const int MAX_N = 100;
int n;
string s;
bool use[MAX_N] = {};

int main()
{
  cin >> n >> s;
  deque<char> q(s.begin(),s.end());

  int c = 0;
  for (int i = 0; i < (int)s.length(); i++) {
    if (use[i]) continue;
    use[i] = true;
    if (s[i] == '(') {
      c++;
    } else {
      if (c > 0) c--;
      else q.push_front('(');
    }
  }
  while (c--) {
    q.push_back(')');
  }

  cout << string(q.begin(),q.end()) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	long double pi = 3.14159265358979;
	long double n, m;
	long double a, b;
	cin >> a >> b;
	cin >> n >> m;
	if (n >= 12) {
		n -= 12;
	}
	long double ans = abs(n * 30 - m * 5.5);
	if (ans > 180) {
		ans = 360 - ans;
	}
	long double r = ans * pi / 180;
	long double c = cos(r);
	long double ans1 = a * a + b * b - 2 * a * b * c;
	ans1 = sqrt(ans1);
	cout << fixed << setprecision(12) << ans1 << endl;
	return 0;
}

Measured memory_bytes: 4120
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, N) for(int i = 0; i < N; ++i)

typedef long long ll;
using namespace std;

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

    ll ans = 0;
    auto rem =  n % k;
    ans = min(rem, abs(k-rem));
    cout << ans << endl;
    
    return 0;
}


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

int main(){
  string T, S ;
  cin >> S >> T;
  ll ans = (1 << 30), check = S.size() - T.size() + 1, tsize = T.size();
  for(ll i = 0; i < check; i++){
    ll wrong = 0;
    string ST = S.substr(i,tsize);
    for(ll j = 0; j < tsize; j++)
      if(ST[j] != T[j]) wrong++;
    ans = min(ans, wrong);
  }
  cout << ans << endl;
}


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

using namespace std;

int main() {

	int n, x;
	cin >> n >> x;

	int d[n+1];
	d[0] = 0;

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

	for (int i = 0; i <= n; i++) {
		if (d[i] <= x) { ans++; }
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    private int N,K;
    private int[]A,B;
    private void Scan()
    {
        var l=Console.ReadLine().Split(' ');
        N=int.Parse(l[0]);
        K=int.Parse(l[1]);
        A=new int[N];
        B=new int[N];
        for(int i=0;i<N;i++)
        {
            l=Console.ReadLine().Split(' ');
            A[i]=int.Parse(l[0]);
            B[i]=int.Parse(l[1]);
        }
    }
    
    private long C(int n)
    {
        long res=0;
        for(int i=0;i<N;i++)
        {
            if((A[i]&n)==A[i])
            {
                res+=B[i];
            }
        }
        return res;
    }
    
    private void Calc()
    {
        long ans=C(K);
        for(int i=0;i<30;i++)
        {
            int b=1<<i;
            if((K&b)>0)
            {
                int n=(K-b)|(b-1);
                ans=Math.Max(ans,C(n));
            }
        }
        
        Console.WriteLine(ans);
    }
    
    public void Solve()
    {
        Scan();
        Calc();
    }
    
    static void Main()
    {
        new Program().Solve();
    }
}

static class MyMath
{
    static public long GCD(long a,long b)
    {
        if(a<b)
        {
            var t=a;
            a=b;
            b=t;
        }
        while(b>0)
        {
            long r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
}

Measured memory_bytes: 17856
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main() {
	string c = "CODEFESTIVAL2016";
	string s;
	cin >> s;
	int cc = 0;
	for (int i = 0; i < s.size(); i++) {
		if (c[i] != s[i]) {
			cc++;
		}
	}
	cout << cc << endl;
	return 0;
}

Measured memory_bytes: 892
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int A, B;
  cin>>A>>B;
  cout<<max(A+B, max(A-B, A*B))<<endl;
}



Measured memory_bytes: 3580
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){
    int n; cin >> n;
    vector<ll> A(n); rep(i, n) cin >> A[i];
    sort(all(A));
    ll res = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            //left < c < right
            int a = A[i], b = A[j];
            int len = lower_bound(all(A), a+b) - A.begin();
            res += len - j - 1;
        }
    }
    cout << res << ln;
}
    


Measured memory_bytes: 3560