akhauriyash/Code-Regression huggingface dataset:
def coloring_colorfully(S: str)->int:
    # 黒から始まるように変更した場合の操作と
    # 白から始まるように変更した場合の操作数。
    black, white = 0, 0

    for i, c in enumerate(S):
        if i % 2 == 0:
            if c == '0':
                white += 1
            else:
                black += 1
        else:
            if c == '0':
                black += 1
            else:
                white += 1

    return min(black, white)


if __name__ == "__main__":
    S = input()
    ans = coloring_colorfully(S)
    print(ans)


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

using namespace std;

typedef long long ll;

template<int MOD, int RT = 1> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; }
	int v; explicit operator int() const { return v; }
	mint() { v = 0; }
	mint(ll _v) { v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD; }
	friend bool operator==(const mint& a, const mint& b) {
		return a.v == b.v; }
	friend bool operator!=(const mint& a, const mint& b) {
		return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) {
		return a.v < b.v; }
	friend void re(mint& a) { ll x; cin >> x; a = mint(x); }
	friend string ts(mint a) { return to_string(a.v); }

	mint& operator+=(const mint& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this; }
	mint& operator-=(const mint& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this; }
	mint& operator*=(const mint& m) {
		v = (ll) v * m.v % MOD; return *this; }
	mint& operator/=(const mint& m) { return (*this) *= inv(m); }
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }
	friend mint inv(const mint& a) { assert(a.v != 0);
		return pow(a, MOD-2); }

	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

constexpr int md = (int) 1e9 + 7;
using Mint = mint<md>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  for (int i = 0; i < h; i++) {
    cin >> s[i];
  }
  vector<vector<Mint>> dp(h + 1, vector<Mint>(w + 1));
  dp[0][0] = 1;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i == 0 && j == 0)
        continue;
      if (s[i][j] == '.') {
        if (i > 0) {
          dp[i][j] = dp[i - 1][j];
        } if (j > 0) {
          dp[i][j] += dp[i][j - 1];
        }
      }
    }
  }
  cout << dp[h - 1][w - 1].v << '\n';
  return 0;
}


Measured memory_bytes: 8208
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define f(i,a,b,c) for(ll i=a;i<b;i+=c)
#define r(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define mod 1000000007

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll a,b,c,d; cin >> a >> b >> c >> d;
	ll ar[4];
	ar[0] = a*c;
	ar[1] = a*d;
	ar[2] = b*c;
	ar[3] = b*d;
	sort(ar,ar+4);
	cout << ar[3];
    return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>

int main()
{
    int n;
    long long int res;
    scanf("%d",&n);
    int f[n][10];
    int p[n][11];
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            scanf("%d",&f[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<11;j++){
            scanf("%d",&p[i][j]);
        }
    }
    long long int resx=0,kaisu=0;
    int min=-1000000000;
    res=min;
    for(int k=1;k<1024;k++){
        resx=0;
        for(int j=0;j<n;j++){
            kaisu=0;
            for(int i = 0; i<10;i++){
                kaisu+=(k>>i)&f[j][i];
            }
            resx+=p[j][kaisu];
        }
        if(res<resx){
            res=resx;
        }
    }
    printf("%lld\n",res);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> p(m);
  for(Int i=0;i<m;i++) cin>>p[i];
  vector<Int> a(n),b(n),c(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];

  vector<Int> s(n);
  for(Int i=0;i<m;i++) p[i]--;
  for(Int i=1;i<m;i++){
    s[min(p[i-1],p[i])]++;
    s[max(p[i-1],p[i])]--;
  }
  for(Int i=1;i<n;i++) s[i]+=s[i-1];
  
  Int ans=0;
  for(Int i=0;i<n;i++) ans+=min(s[i]*a[i],c[i]+s[i]*b[i]);
  
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 6788
#include <stdio.h>
int main()
{
  int W,H,x,y,r;
  scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
  if(x<W && y<H && x+r<=W && y+r<=H && W>0 && H>0 && -100<=x&y<=100 && x+r>0 && y+r>0)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

signed main()
{
    int A, B, C;
    cin >> A >> B >> C;
    printf("%lld\n", min(B/A, C));
    return 0;
}


Measured memory_bytes: 256
s = input()
t = input()
sWords = {}
tWords = {}
for si, ti in zip(s,t):
    sWords[si] = sWords.get(si, 0) + 1
    tWords[ti] = tWords.get(ti, 0) + 1
print(["No", "Yes"][sorted(list(sWords.values())) == sorted(list(tWords.values()))])

Measured memory_bytes: 3632
import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

void main() {
  auto size = readln.chomp.to!int;
  auto lucky = cast(byte[])readln.chomp;
  lucky[] -= '0';

  void solve() {
    int count;
    bool[byte] ava;
    foreach(a; lucky) ava[a] = true;

    foreach(x; ava.keys) foreach(y; ava.keys) foreach(z; ava.keys) {
      if (auto after_x = lucky.findSplit([x])) {
        if (auto after_y = after_x[2].findSplit([y])) {
          if (after_y[2].canFind(z)) {
            count++;
          }
        }
      }
    }
    writeln(count);
  }

  solve();
}


Measured memory_bytes: 2428
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

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

	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			if(i * (m - j) + j * (n - i) == k){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3620
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n = I()
    p = LI()
    cnt = 0
    for i in range(n-2):
        if p[i] < p[i+1] < p[i+2]:
            cnt += 1
        if p[i+2] < p[i+1] < p[i]:
            cnt += 1
    print(cnt)
main()



Measured memory_bytes: 83712
N = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(N):
    if a[i] % 2 == 0:
       ans *= 2
if N != 1:
    print(3**N-ans)
else:
    if a[0] % 2 == 0:
        print(1)
    else:
        print(2)


Measured memory_bytes: 9100
#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i){
        int n, d;
        cin >> n >> d;
        int ans = 127 * (n - 1) + (n % 2 ? d : (127 ^ d));
        cout << ans << endl;
    }


    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    int c[10][10];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            cin>>c[i][j];
    }
    int c1,c2,c3;
    c1=c[1][2]-c[1][1];
    c2=c[2][2]-c[2][1];
    c3=c[3][2]-c[3][1];
    int d1,d2,d3;
    d1=c[1][3]-c[1][2];
    d2=c[2][3]-c[2][2];
    d3=c[3][3]-c[3][2];
    bool b=true;
    if(!(c1==c2&&c1==c3))b=false;
    if(!(d1==d2&&d1==d3))b=false;

    if(b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
import math

def main():

    N = int(input())
    ps = []
    for i in range(2, 55555+1):
        if isPrime(i) and i % 5 == 1:
            ps.append(i)
        if len(ps) == N:
            return ps


def isPrime(n):
    if n == 1: return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

if __name__ == '__main__':
    output = main()
    print(" ".join(map(str, output)))

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std;
 
typedef signed long long ll;
const int MX = 1e6 + 5;

int main() {
	int n;
	string A, B, C = "";
	cin >> n >> A >> B;
	for(int i = 0; i < n; C.push_back(A[i]), C.push_back(B[i]), i++);
	cout << C << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(ll a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    int n; cin >> n;
    ll a[n]; inarray(a, n);
    ll sum = 0;
    sort(a, a+n);
    sum += a[n-1];
    for(int i = n-2, c = 0; c < n-2 ; c++){
        sum += a[i];
        if(c % 2 == 1) i--;
    }
    cout << sum << endl;
    return 0;
}

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

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

int main(){
    
    long int N,M;
    string S,T;
    cin>>N>>M>>S>>T;
    long int k=gcd(N,M);
    long int a=N/gcd(N,M),b=M/gcd(N,M);
    bool flag=true;
    for(int i=0;i<k;i++){
        if(S[i*a]!=T[i*b]) flag=false;
    }
    if(flag) cout<<a*M<<endl;
    else cout<<-1<<endl;
    
}


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

#define ll long long int

int mx = 1e5+7;
int main(){
  ll n,m;
  cin >> n >> m;
  priority_queue<ll> q;
  for(int i=0;i<n;i++){
    ll a;
    cin >> a;
    q.push(a);
  }
  ll ans=0;
  for(int i=0;i<m;i++){
    ll x = q.top();
    q.pop();
    q.push(x/2);
  }
  for(int i=0;i<n;i++){
    ans+=q.top();
    q.pop();
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1400
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    S = input()
    a = [0] * (len(S) + 1)
    for i in range(len(S)):
        if S[i] == '<':
            a[i + 1] = max(a[i + 1],a[i] + 1)
    for i in range(len(S) - 1,-1,-1):
        if S[i] == '>':
            a[i] = max(a[i],a[i + 1] + 1)
    print(sum(a))    
if __name__ == '__main__':
    main()


Measured memory_bytes: 23336
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c) { return b / c - (a - 1) / c; }

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

int main() {
    long long n, m;
    cin >> n >> m;
    vector<int> as(n);
    vector<int> bs(n);
    vector<int> cs(m);
    vector<int> ds(m);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        cin >> bs[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> cs[i];
        cin >> ds[i];
    }
    for (int i = 0; i < n; i++) {
        vector<int> xs;
        long md = 1e10;
        for (int j = 0; j < m; j++) {
            if (md > abs(as[i] - cs[j]) + abs(bs[i] - ds[j])) {
                md = abs(as[i] - cs[j]) + abs(bs[i] - ds[j]);
            }
        }
        for (int j = 0; j < m; j++) {
            if (md == abs(as[i] - cs[j]) + abs(bs[i] - ds[j])) {
                xs.push_back(j);
            }
        }
        sort(xs.begin(), xs.end());
        cout << xs[0] + 1 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e9
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ll long long
using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll s, sum = 0;
    vector<ll> a;
    rep(i, n){
        cin>>s;
        a.pb(s);
        sum += s;
    }
    int ans = 0;
    ll mi = 9999999999;
    
    ll tmp1 = sum, tmp2 = 0, tmp = 0; 
    
    rep(i, n){
        tmp1 -= a[i];
        tmp2 += a[i];
        tmp = abs(tmp1-tmp2);
        if(tmp < mi){
            mi = tmp;
        }
    }
    
    cout<<mi<<endl;
    return 0;
}

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

using namespace std;

typedef long long llint;
const long long MOD = 1e9 + 7;

/* べき乗(mのn乗)を計算する関数. O(logn) */
template <typename T>
T modpow(T m, T n, const T &p) {
  if (n == 0) return 1;
  T ret = modpow(m * m % p, n / 2, p);
  if (n % 2) ret *= m;
  return ret % p;
}

llint fact[101010];
void makecomb(int n) {
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i, fact[i] %= MOD;
}
llint retcomb(int n, int r) {
  if (r < 0 || r > n) return 0;
  return fact[n] * modpow(fact[r], MOD - 2, MOD) % MOD *
         modpow(fact[n - r], MOD - 2, MOD) % MOD;
}

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

  makecomb(n + 5);

  llint ans = 0;
  for (int ri = 0; ri < 2; ri++) {
    for (int i = 0; i < n; i++) {
      llint now = retcomb(i, k - 1);
      if (ri == 1) now = -now;
      ans += now * a[i] % MOD, ans %= MOD;
    }
    reverse(a.begin(), a.end());
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1408
#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>;
 
int main() {
  int n;
  string s;
  cin >> n >> s;
  int a = 0, b = 0;
  rep(i,n) if (s[i] == 'R') ++a;
  int ans = max(a,b);
  rep(i,n) {
    if (s[i] == 'R') --a;
    else ++b;
    int now = max(a,b);
    ans = min(ans, now);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3748
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

const int MaxN = 10000;
const int MaxNL = MaxN * 2;
const int M = 998244353;

inline int modpow(int a, const int &n)
{
	int res = 1;
	for (int i = n; i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

int n;
char a[MaxN + 2];
char b[MaxN + 2];

int fact[MaxNL + 1];
int rfact[MaxNL + 1];

inline void init_fact(int n = MaxNL)
{
	fact[0] = 1;
	for (int i = 1; i <= n; ++i)
		fact[i] = (s64)fact[i - 1] * i % M;

	rfact[n] = modpow(fact[n], M - 2);
	for (int i = n; i; --i)
		rfact[i - 1] = (s64)rfact[i] * i % M;
}

int f[MaxN + 1];

int main()
{
	init_fact();

	scanf("%s", a + 1);
	scanf("%s", b + 1);
	n = strlen(a + 1);

	int x = 0, y = 0;
	for (int i = 1; i <= n; ++i)
		if (a[i] == '1')
			b[i] == '0' ? ++x : ++y;

	f[0] = 1;
	for (int i = 1; i <= x; ++i)
		for (int j = 1; j <= y; ++j)
			f[j] = (f[j] + (s64)i * f[j - 1]) % M;

	int res = 0;
	for (int i = 0; i <= y; ++i)
		res = (res + (s64)f[i] * rfact[i + x]) % M;

	res = (s64)res * fact[x] % M * fact[x] % M;
	res = (s64)res * fact[y] % M;
	res = (s64)res * fact[x + y] % M;

	cout << res << endl;

	return 0;
}

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

using ll=long long;

int main(){
    int n;
    cin>>n;
    vector<ll> cost(n+3,0);
    vector<ll> a(n+2,0);
    a[n+1]=0;
    for(int i=0;i<n;i++)cin>>a[i+1];
    for(int i=1;i<=n+1;i++){
        cost[i+1]=cost[i]+abs(a[i]-a[i-1]);
    }
    for(int i=1;i<=n;i++){
        cout<<cost[i]+abs(a[i-1]-a[i+1])+cost[n+2]-cost[i+2]<<endl;;
    }
    return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#define lli long long int
using namespace std;

int main()
{
    lli n, count = 0, max = 0;
    cin >> n;
    lli c[n];
    for(lli i = 0; i < n ; i++)
    {
        cin >> c[i];
    }
    for(lli i = 0; i < n - 1 ; i++)
    {
        if(c[i] >= c[i + 1])
        {
            count++;
            if(count >= max)
                max = count;
        }
        else
            count = 0;
    }
    cout << max << endl;

    return 0;
}


Measured memory_bytes: 1024
w, h, x, y = map(int, input().split())

rect = w * h

cx = w / 2
cy = h / 2

if x == cx:
    s = x * h
elif y == cy:
    s = y * w
else:
    a = (x - cx) / (y - cy)
    if -1 < a < 1:
        s = w * cy
    else:
        s = h * cx

if cx == x and cy == y:
    print(s, 1)
else:
    print(s, 0)


Measured memory_bytes: 3064
from collections import defaultdict
roads = [list(map(int, input().split())) for _ in range(3)]

degree = defaultdict(int)

for r in roads:
    degree[r[0]] += 1
    degree[r[1]] += 1

odd_num = 0
for val in degree.values():
    if val % 2 != 0:
        odd_num += 1

if odd_num == 0 or odd_num == 2:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3316
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int MOD=1000000007;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b && a!=c){
        cout<<"Yes";
    }else if(a==c && a!=b){
        cout<<"Yes";
    }else if(c==b && a!=c){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}

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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'

VI n, x;
int cnt = 0;
signed main()
{
    REP(i, 10000){
        int a, b;
        cin >> a >> b;
        if (a == 0 && b == 0) break;
        n.push_back(a);
        x.push_back(b);
    }

    REP(times, n.size()){
        FOR(i, 1, x[times]){
            FOR(j, i+1, x[times] - i){
                if (x[times] - i - j > j && x[times] - i - j <= n[times]) {
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
        cnt = 0;
    }
    return 0;
}


Measured memory_bytes: 3148
import java.util.*;

public class Main {
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] arr = sc.next().toCharArray();
        char prev = 'A';
        int count = 0;
        for (char c : arr) {
            if (prev >= c) {
                count++;
            }
            prev = c;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 26260
tbl = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
n = int(input())
for i in range(n):
    b,f,r,v = map(int,input().split())
    if tbl[b-1][f-1][r-1] == 0:
        tbl[b-1][f-1][r-1] = v
    else:
        tbl[b-1][f-1][r-1] += v
for k in range(4):
    for j in range(3):
        for i in range(10):
            print(' ', end='')
            print(tbl[k][j][i], end='')
        print()
    if k != 3:
        print('####################')


Measured memory_bytes: 5632
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): #整数のときはその値について更新する
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

Measured memory_bytes: 66268
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<char>> vec(3,vector<char>(3));
for (int i = 0;i < 3;i++) {
  for (int j = 0;j < 3;j++) {
    cin >> vec.at(i).at(j);
  }
}
cout << vec.at(0).at(0) << vec.at(1).at(1) << vec.at(2).at(2) << endl;

  return 0;
}

Measured memory_bytes: 256
import sys
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
start = 0
end = k
count = 0
for i in range(n):
    if a[n-1]==1:
        print(count)
        sys.exit()
    a[start:end] = [1]*k
    start += (k-1)
    end += (k-1)
    count += 1

Measured memory_bytes: 13880
'use strict';
(function(stdin) {
  //declare function

  //declare variable
  var inputs = stdin.toString().trim().split(' ');
  //main
  inputs = inputs.sort(function(a, b) {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    })
    //display
  console.log(inputs.join(' '));
})(require('fs').readFileSync('/dev/stdin', 'utf8'))

Measured memory_bytes: 15580
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long int n;
	cin >> n;
	long long int q =n/15;
	long long int r =n%15;
	long long int a=0;
	for (long long int i = 0; i < q; ++i)
	{
		a=a+60+120*i;
	}
	
	vector<long long int> vec={ 15*q+1,15*q+2,0,15*q+4,0,0,15*q+7,15*q+8,0,0,15*q+11,0,15*q+13,15*q+14 };
	if(r!=0){
	for (int i = 0; i < r; ++i)
	{
        a=a+vec.at(i);
		
	}
	cout << a << endl;
}
else{
	cout << a << endl;
}


}

Measured memory_bytes: 3632
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  while (sc.hasNext) {
    val n = sc.nextInt()
    if (n == 0) sys.exit()
    val scores = List.fill(n)(sc.nextInt())
    println(f"${calc(n, scores).toDouble}%.8f")
  }

  def calc(n: Int, scores: List[Int]): BigDecimal = {
    val m = (scores.sum.toDouble / n).toBigDecimal
    val dispersion = ((scores.map(e => (e - m).squared).sum) / n)
    dispersion.sqRoot.abs
  }

  implicit class DoubleExtends(val d: Double) extends AnyVal {
    def toBigDecimal = BigDecimal(d)
  }

  implicit class BigDecimalExtends(val b: BigDecimal) extends AnyVal {

    import scala.math.sqrt

    def squared = b * b

    def sqRoot = sqrt(b.toDouble).toBigDecimal
  }

}

Measured memory_bytes: 50036
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 1; i < n; i++) {
            int x = sc.nextInt()-1;
            a[x]++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(a[i]).append("\n");
        }
        System.out.print(sb.toString());
        sc.close();

    }

}


Measured memory_bytes: 60112
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
int main() {
  string S;
  cin>>S;
  int a=S.size();
  if(S[a-1]=='s'){
      cout<<S<<"es"<<endl;
  }
  else{
      cout<<S<<"s"<<endl;
  }
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string str,res;
  cin >> N >> str;
  
  res = "Yes";
  
  if(N%2 !=0){
    res = "No";
  }
  
  for (int i = 0;i<N/2;++i){
   if (N%2 == 0){
   if(str.at(i) != str.at(i+N/2)){
     res = "No";
   break;
   }
   }
      else{
        break;
      }
  }
  cout << res << endl;
}

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

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

    vector<int> dp(n, 0), child[n], indeg(n, 0);
    int x, y;

    for(int i = 0; i < m; i++){
        cin >> x >> y;
        x--, y--;
        child[x].push_back(y);
        indeg[y]++;
    }

    queue<pair<int,int>> q;
    vector<double> used(n, 0);

    for(int i = 0; i < n; i++)  if(indeg[i] == 0)   q.push({i, 0});

    while(!q.empty()){
        pair<int,int> p = q.front();    q.pop();
        dp[p.first] = p.second;
        used[p.first] = true;
        for(int c : child[p.first]){
            indeg[c]--;
            if(indeg[c] == 0)   q.push({c, dp[p.first]+1});
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;

    return 0;
}

Measured memory_bytes: 7296
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 1)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int moder) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%moder;
		x = x * x%moder;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	if (x == y)return 1;
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

string s;
int ans[100010];
int cnt1, cnt2;
int a, b;

signed main(){
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R'&&s[i + 1] == 'R')cnt1++;
		if (s[i] == 'L'&&s[i + 1] == 'L')cnt2++;
		if (s[i] == 'R'&&s[i + 1] == 'L') {
			a = i;
			b = i + 1;

		}
		if (s[i] == 'L'&&s[i + 1] == 'R'||i==s.size()-1) {
			if ((cnt1 + cnt2) % 2 == 0) {
				ans[a] = (cnt1 + cnt2 + 2) / 2;
				ans[b] = ans[a];
			}
			else {
				if (cnt1 < cnt2) {
					if (cnt2 % 2 == 1) {
						ans[a] = (cnt1 + cnt2 + 3) / 2;
						ans[b] = ans[a] - 1;
					}
					else {
						ans[a] = (cnt1 + cnt2 + 1) / 2;
						ans[b] = ans[a] + 1;
					}
				}
				else {
					if (cnt1 % 2 == 0) {
						ans[a] = (cnt1 + cnt2 + 3) / 2;
						ans[b] = ans[a] - 1;
					}
					else {
						ans[a] = (cnt1 + cnt2 + 1) / 2;
						ans[b] = ans[a] + 1;
					}
				}
			}
			cnt1 = 0;
			cnt2 = 0;
		}
	}
	for (int i = 0; i < s.size(); i++) {
		if (i == s.size() - 1)cout << ans[i] << endl;
		else cout << ans[i] << " ";
	}
}

Measured memory_bytes: 1408
#include<iostream>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	if (a <= 5) {
		cout << "0" << endl;
	}
	else if (a <= 12) {
		cout << b / 2 << endl;
	}
	else {
		cout << b << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)

# change limit for deep tree (recursion)
sys.setrecursionlimit(N)

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)

Measured memory_bytes: 91936
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import math
    # import random
    input = stdin.readline


    s = input()[:-1]
    t = input()[:-1]
    if t[:-1] == s:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 8972
#include <bits/stdc++.h>
#define INF 1e7

using namespace std;
typedef long long int ll;
typedef tuple<int,int,int> tii;
typedef tuple<long long int,long long int,long long int> tll;
typedef tuple<double,double,double> tdd;

int main()
{
    ll n,m,q; cin >> n >> m >> q;
    vector<vector<ll>>G(n+1,vector<ll>(n+1,0));
    for(int i = 0; i < m; i++)
    {
        ll l,r; cin >> l >> r;
        G[l][r] += 1;
    }
    vector<vector<ll>>dp(n+1,vector<ll>(n+1,0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + G[i][j];
        }
    }
    for(int i = 0; i < q; i++)
    {
        int p,q; cin >> p >> q;
        cout << dp[q][q] - dp[q][p-1] - dp[p-1][q] + dp[p-1][p-1] << endl;
    }
}

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

A.sort()

A.append(0)
B = []
length = 1
for i in range(N):
    if A[i] == A[i+1]:
        length += 1
    else:
        B.append(length)
        length = 1

for i in range(len(B)):
    B[i] = 2 - B[i] % 2

if B.count(2) % 2 == 0:
    print(len(B))
else:
    print(len(B)-1)

Measured memory_bytes: 14092
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a) memset(a, 0, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back
#define inf (1<<29)

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

vector<ll>vec;
bool isPrime[1000101];
void sieve(){
    int MAX = 1000101, sq = sqrt(MAX);
    memset(isPrime,true, sizeof isPrime);
    for(int i = 4; i<=MAX; i+=2){
        isPrime[i] = 0;
    }
    for(int i = 3; i<=sq; i+=2){
        if(isPrime[i]){
            for(int j = i*i; j<=MAX; j+=i){
                isPrime[j] = 0;
            }
        }
    }
    isPrime[1]=0;
    isPrime[0]=0;
    for(int p = 2; p<MAX; p++){
        if(isPrime[p])vec.pb(p);
    }
}

ll factorialDivisors(ll n){
    ll ans = 1;
    for(ll x : vec){
        ll p = x;
        ll exp = 0;
        while(p<=n){
            exp  = exp+(n/p);
            p = p*x;
        }
        ans = (ans*(exp+1))%mod;
    }

    return ans;
}

int main(){
        _ios;

        sieve();
        ll n; cin >> n;
        cout<< factorialDivisors(n)<<endl;



return 0;
}


Measured memory_bytes: 2424
n = int(input())

dp = [float("INF")] * 1000010
dp[0] = 0


for i in range(1, 100001):
    power = 1
    while power <= n:
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 6


for i in range(1, 100001):
    power = 1
    while power <= n:
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 9


ans = dp[n]
print(ans)

Measured memory_bytes: 78940
n, m = map(int, input().split())
h = list(map(int, input().split()))
count = [0] * n

for i in range(m):
  a, b = map(int, input().split())
  if h[a - 1] < h[b -1]:
    count[a - 1] = 1
  elif h[a - 1] > h[b - 1]:
    count[b - 1] = 1
  else:
    count[a - 1] = 1
    count[b - 1] = 1
    
print(count.count(0))

Measured memory_bytes: 19940
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

	      	  cin.tie(0);  ios_base::sync_with_stdio(false);
	      	  
	      	  string x;
	      	  cin >> x;
	      	  int n=x.size();
	      	  
	      	  for(i=0;i<=n-9;i++){
	      		  cout << x[i];
	      	  }
	      	  
	      	  cout << endl;

	          return 0;
}


Measured memory_bytes: 256
N = int(input())
C = [0]*6
S = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
L = [1, 2, 2, 3, 3, 2]
P = []
init = [0, 1, 2]
for i in range(N):
    w, *A = map(int, input().split())
    state = init[:]
    for a in A:
        if a:
            state[1], state[2] = state[2], state[1]
        else:
            state[0], state[1] = state[1], state[0]
    j = S.index(state)
    C[j] += 1
    if C[j] >= L[j]:
        print('yes')
        exit(0)
    P.append(state)

# case: "L <= [0, 1, 1, 2, 2, 1]"
from itertools import permutations
for p in permutations(P):
    s = init[:]
    for q in p:
        s[0], s[1], s[2] = s[q[0]], s[q[1]], s[q[2]]
    if s == init:
        print('yes')
        exit(0)
print('no')



Measured memory_bytes: 5652
n, m, k = map(int, input().split())
a = list(map(int, input().split())) 
b = list(map(int, input().split()))

from bisect import bisect_right
"""
if n>m:
    a, b = b, a
    n, m = m, n
"""
c = [b[0]]
for i in range(1, m):
    c.append(c[-1]+b[i])
a.insert(0,0)
x = 0
result = [0]
for i in range(n+1):
    x += a[i]
    if x > k:
        break
    y = k - x
    z = bisect_right(c, y)
    result.append(z+i)
print(max(result))


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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

void compress(vector<pii>& vec) {
	vi xs, ys;
	for (auto &p : vec) {
		xs.pb(p.fi);
		ys.pb(p.se);
	}
	sort(ALL(xs));
	sort(ALL(ys));
	xs.erase(unique(ALL(xs)), xs.end());
	ys.erase(unique(ALL(ys)), ys.end());	
	rep(i, vec.size()) {
		int a = lower_bound(ALL(xs), vec[i].fi) - xs.begin();
		int b = lower_bound(ALL(ys), vec[i].se) - ys.begin();
		vec[i] = mp(a, b); 
	}
}

void rot(vector<pii>& vec) {
	rep(i, vec.size()) {
		int x = vec[i].fi, y = vec[i].se;
		vec[i] = mp(-y, x);
	}
}

vector<pii> gen(vi a) {
	int n = a.size();
	if (n == 4) {
		vector<pii> res = {mp(0, 0), mp(1, 0), mp(1, 1), mp(0, 1)};
		return res;
	} else {
		rep(i, n) {
			int j = (i + 1) % n;
			if (a[i] == 90 && a[j] == 270) {
				vi nx;

				rep(k, n) {
					if (k != i && k != j) {
						nx.pb(a[k]);
					}
				}

				auto _pl = gen(nx);
				for (auto &p : _pl) {
					p.fi *= 2;
					p.se *= 2;
				}

				int l = (i - 1 + n) % n;
				int r = (j + 1) % n;

				vector<pii> pl(n);
				{
					int now = 0;
					rep(k, n) {
						if (k != i && k != j) {
							pl[k] = _pl[now++];
						}
					}
					pl[i] = pl[j] = pl[l];
				}

				rep(t, 4) {
					if (pl[l].fi < pl[r].fi && pl[l].se == pl[r].se) {
						break;
					}
					rot(pl);
				}
				pl[i].fi++; 
				pl[j].fi++; pl[j].se++;
				pl[r].se++;

				compress(pl);
				return pl;
			}
		}
	}
}

int main() {
	int N; cin >> N;
	vi a(N);
	int s = 0;

	rep(i, N) {
		cin >> a[i];
		s += a[i];
	}

	if (s != 180 * (N-2)) {
		puts("-1");
		return 0;
	}

	auto pts = gen(a);
	for (auto p : pts) {
		cout << p.fi << " " << p.se << endl;
	}
	return 0;
}

Measured memory_bytes: 2688
#include<iostream>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	int kind[m]={};
	for(int i=0;i<n;i++){
		int k;
		cin >> k;
		for(int j=0;j<k;j++){
			int a;
			cin >> a;
			kind[a-1]++;
		}
	}
	int ans=0;
	for(int i=0;i<m;i++) if(kind[i]==n) ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
#define Pll pair<ll,ll>

template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const int INF =2e+9;
const ll INFL =9e+18;
const long MOD =1e+9+7;
#define PI 3.14159265258979

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

int main(void){
	int N,tem,cn=1;
	vector<int> ve,ve2;

	cin>>N;
	cin>>tem;
	ve.pb(tem);

	FOR(i,1,N){
		cin>>tem;
		if(*ve.rbegin()!=tem){		
			if(*ve.rbegin()-tem>0) ve2.pb(true);
			else ve2.pb(false);
			ve.pb(tem);
		}
	}

	FOR(i,1,(int)ve2.size()){
		if(ve2[i-1]!=ve2[i]){
			cn++;i++;
		}
	}

	print(cn);

	return 0;
}




Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n; cin>>n;
    int p; cin>>p;
    int arr[p+1];
    memset(arr, 0, sizeof(arr));
    arr[0]=1;
    string s; cin>>s;
    int mult = 1;
    int cur = 0;
    int ans = 0;
    if (p == 2 or p == 5){
        for (int i = n-1; i >= 0; --i){
            if ((s[i]-'0') % p == 0){
                ans += i + 1;
            }
        }
        cout<<ans;
        return 0;
    }
    for(int i=n-1; i>=0; i--){
        int a = s[i]-'0';
        a *= mult;
        a %= p;
        cur += a;
        cur %= p;
        ans += arr[cur];
        // trace(ans);
        arr[cur]++;
        mult *= 10;
        mult %= p;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 848
#include<bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (int)(1e9+7)
#define MOD (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define ios cin.tie(0); ios::sync_with_stdio(false)
#define FIX(a) cout << fixed << setprecision(a)
#define mp make_pair
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//manip
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power_mod(T a, T b) {return b ? power_mod(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
template<class T> T power(T a, T b) {return b ? power(a * a, b / 2) * (b % 2 ? a : 1) : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}
template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outaa(a, m, n) rep(i, m) {rep(j, n) cout << a[i][j] << " "; cout << endl;} cout << endl
#define out(a) cout << a << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl

//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//minimal required terms
//cast caution
//look constraints always
//product of minimum 9 prime numbers is above 1e9

struct mint {int n; mint(int n): n(n){}}; //n = n;
mint operator+(mint a, mint b) {a.n += b.n; return a.n >= mod ? a.n - mod : a.n;}
mint &operator+=(mint &a, mint b) {return a = a + b;}
ostream &operator<<(ostream &s, mint a) {return s << a.n;}

int main() {
    int h, w; cin >> h >> w;
    char c[h][w]; rep(i, h) rep(j, w) cin >> c[i][j];
    
    int dp[h][w]; fill_n(*dp, h * w, 0);
    dp[0][0] = 1;
    rep(i, h) rep(j, w) {
        if (i == 0 && j == 0) continue;
        if (c[i][j] == '#') continue;
        if (j) dp[i][j] += dp[i][j - 1];
        if (i) dp[i][j] += dp[i - 1][j];
        dp[i][j] %= mod;
    }
    out(dp[h - 1][w - 1]);
}

/*
 あるマスに関して下、右がすでに訪問済みだったらいい
 
 
 
 */



Measured memory_bytes: 5120
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;

void main()
{
	int sum, avr, cnt;
	foreach (line; stdin.byLine) {
		auto nm = line.split(",").map!(to!int);
		sum += nm[0] * nm[1];
		avr += nm[1];
		cnt++;
	}
	writeln(sum);
	writeln((1.0*avr/cnt).round);
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <ios>
#include <sstream>
using namespace std;

int triple_max(int x, int y, int z){
    int ans = x;
    if (y > x && y > z) ans = y;
    else if (z > x && z > y) ans = z;

    return ans;
}

int vv(int x, unsigned int y){
    ostringstream str_x;
    str_x << x;
    size_t len = str_x.str().length();
    for (int i = 0; i < (y - len > 0 ? y - len : 0); ++i) {
        cout << 0;
    }
    cout << x << endl;
    return 0;
}

int main(){
    int n, a, expensive = 0, x = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        if (a > expensive) {
            expensive = a;
        }
        x += a;
    }
    cout << x - expensive/2 << endl;

    return 0;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
S = readline().rstrip()

unhappy = 0
for i in range(len(S)):
  if i == 0:
    if S[i] == "L":
      unhappy += 1
    if S[i] == "R" and S[i + 1] == "L":
      unhappy += 1
  elif i == len(S) - 1:
    if S[i] == "R":
      unhappy += 1
    if S[i] == "L" and S[i - 1] == "R":
      unhappy += 1
  else:
    if S[i] == "L" and S[i - 1] != "L":
      unhappy += 1
    if S[i] == "R" and S[i + 1] != "R":
      unhappy += 1
      
print(min(N - 1,N - max(unhappy - K * 2,0)))

Measured memory_bytes: 9272
while 1:
    try:
        S=input()
        JOI,IOI=0,0
        for i in range(len(S)-2):
            r=S[i]+S[i+1]+S[i+2]
            if r=="JOI":
                JOI+=1
            elif r=="IOI":
                IOI+=1
        print(JOI)
        print(IOI)
    except:
        break


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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

struct team
{
	string id;
	int win;
	int lose;

	team(string s,int w,int l) : id(s),win(w),lose(l) {}

	bool operator < (const team& t) const{
		return win == t.win ? lose < t.lose : win > t.win;
	}
};

int main()
{
	int n;
	while(cin >> n && n)
	{
		vector<team> v;

		rep(i,n)
		{
			string s;
			cin >> s;
			
			int w = 0;
			int l = 0;
			
			rep(j,n-1)
			{
				int temp;
				cin >> temp;

				if(temp == 0) w++;
				else if(temp == 1) l++;
			}

			v.push_back(team(s,w,l));
		}

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


		rep(i,v.size())
		{
			cout << v[i].id <<  endl;
		}
	}
	return 0;
}

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

vector<int> nei[100000];
bool used[100000];
int dist[100000];
int par[100000];

struct edge {
  int d, u, v;
  edge(int i, int j, int k) {
    d = i; u = j; v = k;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int u, v;
    cin >> u >> v; u--; v--;
    nei[u].push_back(v);
    nei[v].push_back(u);
  }
  rep(i, n) used[i] = true;

  queue<edge> que;
  que.push(edge(0, 0, -1));
  while (!que.empty()) {
    int u = que.front().u, v = que.front().v, d = que.front().d;
    que.pop();
    if (used[u]) {
      dist[u] = d; par[u] = v; used[u] = false;
      rep(i, nei[u].size()) {
        if (used[nei[u][i]]) {
          que.push(edge(d+1, nei[u][i], u));
        }
      }
    }
  }

  cout << "Yes" << endl;
  rep(i, n-1) cout << par[i+1] + 1 << endl;
  
  return 0;
}


Measured memory_bytes: 11592