akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
  int x;
  cin >> x;
  
  int ret = 1;
  for(int i = 2; i < x; ++i){
    int y = i * i;
    if(x < y){
      continue;
    }
    
    while(y <= x){
      y *= i;
    }
    ret = max(ret, y / i);
  }
  cout << ret << endl;
  return 0;
}


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

/*10^100回移動とか子供が人生をかけても達成できないと思うが...*/
/*移動回数は偶数回であるということ*/
/*連長圧縮を行ったほうがよい？*/

int main(){
  string S;
  cin >> S;                                 //マスの取得
  int N = S.size();                  //マス数
  queue<pair<char, int>> masu;    //移動方向と連続回数 RRLR ... <R,2> <L,1> <R,1>
  vector<int> masuu(N);                    //各マスにたどり着く子供の人数データを格納

  for(int i = 0; i < N;){
    char dir = S.at(i);               //方向を取得
    int num = 0;                      //その方向の連続回数
    
    while(S.at(i) == dir){
      if(i == N-1){
        ++i;
        ++num;
        break;
      }
      ++i;
      ++num;
    }

    masu.push(make_pair(dir, num));       //左の情報から順に格納されていく

  }

  int length = masu.size();                         //masuのサイズはpopで変わるので

  /*for(int i = 0; i < length; i++){
    cout << masu.front().first << " " << masu.front().second << endl;
    masu.pop();
  }*/

  int bef = 0;                                              //開始位置   bef = 2なら masuu[2]から操作
  while(!masu.empty()){
    auto tmp = masu.front();             //進行方向にいくつ進むかを示すデータ

    char dire = tmp.first;                      //進行方向を格納
    int cont = tmp.second;                  //方向連続回数

    for(int i = 0; i < cont; i++){    
      if(dire == 'L'){               //文字変わってLなら、左はRのはず
        if(i % 2 == 0)              //R[L]LL...として[]0番目 2*k番目のLは[L]に、2*k+1はR着
          masuu[bef] += 1;                   //[L]に最終的に到着
        else
          masuu[bef -1] += 1;             //Rに最終的に到着
      }else if(dire == 'R'){                   //R...R[R]Lとして同様
        if(i % 2 == (cont - 1) % 2){
          masuu[bef+cont-1] += 1;
        }else
          masuu[bef+cont] += 1;
      }
      
    
   
    }
    
    bef += cont;       //進行分だけ加算
    masu.pop();       //今回処理したデータを消去
  }

  for(int i = 0; i < masuu.size()-1; i++)
    cout << masuu[i] << " ";
  cout << masuu[masuu.size()-1] << endl;

}




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

using namespace std;

priority_queue <int> pr;
long long n, m, x, d, s;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> x;
        pr.push(x);
    }
    for(int i = 0; i < m; i++){
        d=pr.top();
        d = d/2;
        pr.pop();
        pr.push(d);
    }
    while(!pr.empty()){
        s+=pr.top();
        pr.pop();
    }
    cout << s;
    return 0;
}


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

int main(int argc, char const *argv[])
{
    int n;
    vector<int> v;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    int minv = v[0];
    int ans = -1000000000;
    for(int i = 1; i < n; i++)
    {
        ans = max(ans, v[i] - minv);
        minv = min(minv, v[i]);
    }

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



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

int main()
{
    int n;
    cin>>n;
    vector<vector<int> > dp(n,vector<int>(3));
    vector<vector<int> > a(n, vector<int> (3));

    for(int i=0; i<n; i++)
        for(int j=0; j<3; j++)
        cin>>a[i][j];
    dp[0][0] = a[0][0];
    dp[0][1] = a[0][1];
    dp[0][2] = a[0][2];
    for(int i=1; i<n; i++)
    {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i][0];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1];
        dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + a[i][2];
    }
    int maxi = max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
    cout<<maxi;

    return 0;


}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define int ll

using namespace std;

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

const int M = 1e9 + 7;

vi G[100005];
int k;

int dfs(int u, int m, int p = -1) {
	int ret = m, n = k - 2;
	if(p == -1) n = k - 1;
	for(int v:G[u]) {
		if(v == p) continue;
		ret *= dfs(v, n--, u);
		ret %= M;
	}
	return ret;
}

int32_t main()
{
	IO_OP;
	
	int n;
	cin >> n >> k;
	for(int i=0;i<n-1;i++) {
		int u, v;
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
	
	cout << dfs(1, k) << endl;
}



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

int main(){
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    vector<vector<int>> s(h, vector<int>(w, 0));


    for(int i = 0; i < b; i++){
        for(int j = a; j < w; j++){
            s.at(i).at(j) = 1;
        }
    }

    for(int i = b; i < h; i++){
        for(int j = 0; j < a; j++){
            s.at(i).at(j) = 1;
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cout << s.at(i).at(j);
        }
        cout << "" << endl;
    }

}

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

using namespace std;

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  int n, m;
  cin >> n >> m;

  vector<int> cnt(n+1);
  for(int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    cnt[u]++;
    cnt[v]++;
  }

  cout << (all_of(cnt.begin(), cnt.end(), [](int x) {return not (x&1);}) ? "YES" : "NO") << endl;
}

Measured memory_bytes: 640
H,W,K = map(int, input().split())
C = [input() for _ in range(H)]

ans = 0
for i in range(2**H):
    I = []
    for k in range(H):
        if i & (1<<k) > 0:
            I.append(k)
    for j in range(2**W):
        J = []
        for k in range(W):
            if j & (1<<k) > 0:
                J.append(k)
        cnt = 0
        for a in range(H):
            if a in I:
                continue
            for b in range(W):
                if b in J:
                    continue
                if C[a][b] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Measured memory_bytes: 9160
N = int(input())
a = list(map(int, input().split()))

ans = 0
num = [0] * int(2e5)
for i in a:
    if i < 2e5:
        num[i] += 1
    else:
        ans += 1


for i in range(len(num)):
    if num[i] == 0:
        continue
    else:
        if num[i] < i:
            ans += num[i]
        elif num[i] > i:
            ans += num[i] - i

print(ans)

Measured memory_bytes: 14692
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    vector<vector<char>> c(3, vector<char>(3));
    REP(i, 3) {
        REP(j, 3) { cin >> c[i][j]; }
    }
    REP(i, 3) { cout << c[i][i]; }
    return 0;
}

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

using namespace std;

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


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

  int q, orn =0;
  cin>>q;
  deque<char> frnt, bk;
  while(q--){
    int t;
    cin>>t;
    if(t==1) orn = (orn+1)%2;
    if(t==2){
      int f;
      char c;
      cin>>f>>c;
      f%=2;

      if(orn==0 && f==1) frnt.push_front(c);
      if(orn==0 && f==0) bk.push_back(c);
      if(orn==1 && f==1) bk.push_back(c);
      if(orn==1 && f==0) frnt.push_front(c);
    }

  }
  vector<char> s;
  
  for(int i=0;i<frnt.size();i++){
    s.push_back(frnt[i]);
  }
  for(int i=0;i<inp.size();i++){
    s.push_back(inp[i]);
  }
  for(int i=0;i <bk.size();i++){
    s.push_back(bk[i]);
  }

  if(orn==0){
    for(int i=0;i<s.size();i++){
      cout<<s[i];
    }
    cout<<endl;
  }else {
    for(int i=s.size()-1;i>=0;i--){
      cout<<s[i];
    }
    cout<<endl;
  }

  

  
  

  return 0;
}


Measured memory_bytes: 1276
#include <bits/stdc++.h>
#define re return
#define ll long long
#define oo 1e9
#define mm(o,k) memset(o,k,sizeof o)
using namespace std;
ll m,n,k,a[500000],ans,x,z,o,zz,h;
string s;
int main()
{
     cin>>n>>m;
     ans=n-m;
     if (ans>0)cout<<ans;
     else cout<<0;

    return 0;
}


Measured memory_bytes: 256
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));
  list($s) = explode(" ", trim(fgets(STDIN)));

  $w=[0];
  for($i=0;$i<$n;$i++){
    if($s[$i]=='W') $w[$i+1]=$w[$i]+1;
    else $w[$i+1]=$w[$i];
  }
  $e=[0];
  for($i=0;$i<$n;$i++){
    if($s[$n-1-$i]=='E') $e[$i+1]=$e[$i]+1;
    else $e[$i+1]=$e[$i];
  }

  $ans=PHP_INT_MAX;

  for($i=1;$i<=$n;$i++){
    $cnt=$w[$i-1]+$e[$n-$i];
//    echo $w[$i-1]." ".$e[$n-$i].PHP_EOL;
    $ans=min($ans,$cnt);
  }

  echo $ans;

Measured memory_bytes: 42928
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
bool comp(int a,int b)
{
	return a>b;
}
int main()
{
	int a[300];
	int n;
	cin>>n;
	for(int i=0;i<2*n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+2*n,comp);//从大到小排序
	int ans=0;
	for(int i=1;i<2*n;i=i+2)
	{
		ans+=a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3168
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
  int N;
  cin>>N;
  int a[100000],b[100000];
  for(int i=1;i<=N;i++){
    cin>>a[i];
    b[a[i]]=i;
  }
  for(int i=1;i<=N;i++){
    if(i!=N){
    cout<<b[i]<<' ';
    }
    else{
      cout<<b[i]<<endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1536
N, K = map(int, input().split())
L = [0 for i in range(26)]
for i in range(N):
    p = input()
    L[ord(p[0]) - ord("A")] += 1
ans = 0
while True:
    maxv = [0 for k in range(K)]
    argmax = [-1 for k in range(K)]
    cnt = 0
    for n in range(26):
        minimum = min(maxv)
        if L[n] > minimum:
            for k in range(K):
                if maxv[k] == minimum:
                    argmax[k] = n
                    maxv[k] = L[n]
                    break
    # print(argmax)
    if 0 in maxv:
        print(ans)
        break
    else:
        for k in range(K):
            L[argmax[k]] -= 1
        ans += 1


Measured memory_bytes: 3064
/*  -*- coding: utf-8 -*-
 *
 * f.cc: F - Select Half
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 200000;
const long long LINF = 1LL << 62;

/* typedef */

typedef long long ll;

/* global variables */

int as[MAX_N];
ll dp00[MAX_N + 1], dp01[MAX_N + 1], dp10[MAX_N + 1], dp11[MAX_N + 1];

/* subroutines */

inline void setmax(ll &a, ll b) { if (a < b) a = b; }

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i);

  fill(dp00, dp00 + n + 1, -LINF);
  fill(dp01, dp01 + n + 1, -LINF);
  fill(dp10, dp10 + n + 1, -LINF);
  fill(dp11, dp11 + n + 1, -LINF);
  dp01[0] = 0;

  for (int i = 0; i < n; i++) {
    bool ev = ((i & 1) == 0);
    if (dp00[i] > -LINF) {
      if (ev)
	setmax(dp10[i + 1], dp00[i] + as[i]);
      else {
	setmax(dp00[i + 1], dp00[i]);
	setmax(dp11[i + 1], dp00[i] + as[i]);
      }
    }
    if (dp01[i] > -LINF) {
      if (ev) {
	setmax(dp00[i + 1], dp01[i]);
	setmax(dp11[i + 1], dp01[i] + as[i]);
      }
      else
	setmax(dp01[i + 1], dp00[i]);
    }
    if (dp10[i] > -LINF) {
      if (! ev)
	setmax(dp00[i + 1], dp10[i]);
    }
    if (dp11[i] > -LINF) {
      if (ev)
	setmax(dp00[i + 1], dp11[i]);
      else
	setmax(dp01[i + 1], dp11[i]);
    }
  }

  printf("%lld\n", (n & 1) ? max(dp00[n], dp10[n]) : max(dp01[n], dp11[n]));

  return 0;
}


Measured memory_bytes: 10212
N, M = gets.split.map &:to_i

W, B, R = (0..2).to_a
color = []
N.times do
  s = gets
  color << [s.count(?W), s.count(?B), s.count(?R)]
end

ans = N * M

(1...(N-1)).each do |t|
  ((t+1)...N).each do |b|
    res = 0
    N.times do |i|
      case i
        when 0...t
          res += M - color[i][W]
        when t...b
          res += M - color[i][B]
        when b...N
          res += M - color[i][R]
      end
    end
    ans = [ans, res].min
  end
end

p ans

Measured memory_bytes: 8668
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#ifndef U_L_LONG
typedef unsigned long long U_L_LONG;
#endif
#ifndef L_LONG
typedef long long L_LONG;
#endif


static void ABC114C_task();

#if 1
int main()
{
	ABC114C_task();

	fflush(stdout);
	return 0;
}
#endif

static int ABC114C_dfs(L_LONG targNum, int digit, int nowDigit, char* sz753)
{
	int ans = 0;
	L_LONG tmp = 0;

	if (digit == nowDigit) {
		bool findNum = false;
		bool find7 = false, find3 = false, find5 = false, findOther = false;
		for (int i = 0; i < digit; i++) {
			if (sz753[i] != '0') {
				findNum = true;
			}

			if (findNum) {
				switch (sz753[i]) {
				case '7':
					find7 = true;
					break;
				case '5':
					find5 = true;
					break;
				case '3':
					find3 = true;
					break;
				default:
					findOther = true;
					break;
				}
			}
		}

		if(!find7 || !find5 || !find3 || findOther) {
			return 0;
		}
		else if ((tmp = strtoll(sz753, NULL, 10)) > targNum) {
			return 0;
		}
		else {
			return 1;
		}
	}

	char setNum[] = { '7', '5', '3', '0' };

	for (int i = 0; i < 4; i++) {
		sz753[nowDigit] = setNum[i];
		ans += ABC114C_dfs(targNum, digit, nowDigit + 1, sz753);
	}
	return ans;
}

static void ABC114C_task()
{
	char sz753[16] = { 0 };
	L_LONG N;
	scanf(" %lld", &N);
	
	int digit = 0;
	L_LONG N2 = N;
	L_LONG div = 1;
	while (N2 / div) {
		digit++;
		div *= 10;
	}

	printf("%d\n", ABC114C_dfs(N, digit, 0, sz753));
}


Measured memory_bytes: 256
from collections import deque

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))
q, k = map(int, input().split())

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)
visited = set({})
while d:
    point = d.popleft()
    for index, value in graph[point]:
        distance[index] = min(distance[point] + value, distance[index])
        if index not in visited:
            d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

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

using ll = long long;

constexpr int MAX_N = 1e5 + 9;

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

const ll INF = 1LL << 60;

int N;
ll h[MAX_N];

ll dp[MAX_N];

int main() {
  fill_n(dp, MAX_N, INF);
  cin >> N;
  for (int i{}; i < N; ++i) cin >> h[i];

  dp[0] = 0;
  for (int i{1}; i < N; ++i) {
    chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
    if (i > 1)
      chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
  }

  cout << dp[N - 1] << endl;
  return 0;
}


Measured memory_bytes: 5164
#include<bits/stdc++.h>
using namespace std;
    static const double pi = 3.141592653589793;
 typedef pair<int64_t,int64_t> P;




int main(){
int a;
  cin>>a;
vector<int>B(a-1);
  for(int i=0;i<a-1;i++)
  {
  int b;
    cin>>b;
    B.at(i)=b;
  }
  vector<int>A(a);
  A.at(0)=B.at(0);
  A.at(a-1)=B.at(a-2);
  for(int i=1;i<a-1;i++)
  {
  A.at(i)=min(B.at(i-1),B.at(i));
  }
  int sum=0;
  for(int i=0;i<a;i++)
  {
  sum=sum+A.at(i);
  
  }
cout<<sum;
}
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int n;
void solve(){
    cout<<(1000-n%1000)%1000<<endl;
}

int main(){
    cin>>n;

    solve();
    return 0;
}


Measured memory_bytes: 3564
import sys
import numpy as np

def parse(inp):
    N=int(next(inp))
    
    wordlist=np.array([list(next(inp))])
    for i in range(2):
        wordlist=np.append(wordlist,np.array([list(next(inp))]),axis=0)

#     print(wordlist)

    return N,wordlist

def main(inp):
    N,wordlist=parse(inp)
    sousa=0
    total=np.array([],dtype=int)
    
    tf01=(wordlist[0]==wordlist[1])
    tf02=(wordlist[0]==wordlist[2])
    tf12=(wordlist[1]==wordlist[2])
#    print(tf01,tf02,tf12)
    for i in range(N):
        total=np.append(total,sum([tf01[i],tf02[i],tf12[i]]))
#    print(total)
    
    for i in range(N):
        if(total[i]==0):
            sousa+=2
        elif(total[i]==1):
            sousa+=1
        else:
            continue
    
    return sousa
  
print(main(sys.stdin))
  

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

sp = [False for _ in range(N + 1)]
pg = [False for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    if a == N:
        pg[b] = True
    if b == N:
        pg[a] = True
    if a == 1:
        sp[b] = True
    if b == 1:
        sp[a] = True

for i in range(1, N + 1):
    if pg[i] and sp[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')


Measured memory_bytes: 6320
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <queue>
#include <stdarg.h>
#include <map>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <numeric>
#include <set>

#define ll long long

using namespace std;

void
solve() {
  int k;
  cin>>k;

  string s;
  cin>>s;

  if (s.length() <= k)
    cout<<s<<endl;
  else 
    cout<<s.substr(0, k)<<"..."<<endl;
}

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

  int t = 1;
  //cin>>t;

  while (t > 0) {
    t--;
    solve();
  }

  return 0;
}



Measured memory_bytes: 3652
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) {
		while (true) {
			int N = nextInt();
			if (N == 0) {
				break;
			}
			int M = nextInt();
			ArrayList<Edge> list = new ArrayList<Edge>();

			for (int i = 0; i < M; i++) {
				int a = nextInt() - 1;
				int b = nextInt() - 1;
				int w = nextInt();
				list.add(new Edge(w, a, b));
			}
			Collections.sort(list);

			int ans = Integer.MAX_VALUE;
			for (int i = 0; i < list.size(); i++) {
				// 道iのコストより大きい物だけを使って最小全域木を作ってみる

				PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
				for (int j = i; j < list.size(); j++) {
					priorityQueue.add(new Edge(list.get(j).weight, list.get(j).from, list.get(j).to));
				}

				UnionFind uf = new UnionFind(N);
				int max = 0;// 最大コストを調べておく
				while (!priorityQueue.isEmpty()) {
					Edge e = priorityQueue.poll();
					if (!uf.isSame(e.from, e.to)) {
						max = Math.max(max, e.weight);
						uf.unite(e.from, e.to);
					}
				}

				// 全域木になっているかチェック
				boolean allSame = true;
				for (int j = 1; j < N; j++) {
					if (!uf.isSame(0, j)) {
						allSame = false;
						break;
					}
				}

				// 全域木なら解答を更新
				if (allSame) {
					ans = Math.min(ans, max - list.get(i).weight);
				} else {
					break;
				}
			}

			if (ans == Integer.MAX_VALUE) {
				System.out.println(-1);
			} else {
				System.out.println(ans);
			}
		}
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}

class UnionFind {
	int[] parts;

	UnionFind(int n) {
		parts = new int[n];
		for (int i = 0; i < n; i++)
			parts[i] = i;
	}

	public int find(int x) {
		if (parts[x] == x)
			return x;
		return parts[x] = find(parts[x]);
	}

	public Boolean isSame(int x, int y) {
		return find(x) == find(y);
	}

	public void unite(int x, int y) {
		if (find(x) == find(y))
			return;
		parts[find(x)] = find(y);
	}
}

class Edge implements Comparable<Edge> {
	int weight;
	int from, to;

	Edge(int w, int f, int t) {
		this.weight = w;
		this.from = f;
		this.to = t;
	}

	@Override
	public int compareTo(Edge edge) {
		// 昇順
		return this.weight - edge.weight;
	}
}

Measured memory_bytes: 167016
#include<bits/stdc++.h>
#define ll long long
#define maxn 1008
using namespace std;
int n;
char s[maxn];
int main(){
scanf("%s",s);
scanf("%d",&n);

for(int i=0;i<strlen(s);i+=n){
    printf("%c",s[i]);
}
printf("\n");



return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
pair<int,int>c[200020];
int ans[200020];
int main()
{
	int n,tot=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>c[i].first,
		c[i].second=i;
	sort(c,c+n);
	for(int i=0;i<n;i++)//2 3 4 4
		if(i<n/2)
			ans[c[i].second]=c[n/2].first;
		else
			ans[c[i].second]=c[n/2-1].first;
	for(int i=0;i<n;i++)//2 3 4 4
		cout<<ans[i]<<endl;
}

Measured memory_bytes: 4480
#include <stdio.h>

int main(){
	int a, b;
	int vl[31];
	int w, n, i, t;

	scanf("%d", &w );

	//init vl( vl[1]=1, vl[2]=2, ... )
	for( i=1; i<=w; i++ )
		vl[i] = i;

	scanf("%d", &n );

	for( i=0; i<n; i++ ){
		scanf("%d,%d", &a, &b);
		t=vl[a]; vl[a]=vl[b]; vl[b]=t;//swap
	}

	for( i=1; i<=w; i++ ){
		printf("%d\n", vl[i] );
	}
	
	return 0;
}

Measured memory_bytes: 592
n = int(input())
p = tuple(map(int, input().split()))

c = 0
for i in range(1, n-1):
  if (p[i+1] > p[i] and p[i] > p[i-1]) or (p[i+1] < p[i] and p[i] < p[i-1]):
    c += 1
print(c)

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

int main(){
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k%2 == 0)  cout << a-b << endl;
    else cout << b-a << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define R register
int n,st[100005],top,vis;
int main()
{
	scanf("%d",&n);int sum=n;
	for(int i=1;;i++)
	{
		if(i>sum)
		{
			st[++top]=i;
			vis=i-sum;
			break;
		}
		else if(i==sum)
		{
			st[++top]=i;
			break;
		}
		sum-=i;
		st[++top]=i;
	}
	for(int i=1;i<=top;i++)
		if(st[i]!=vis)
			printf("%d\n",st[i]);
	return 0;
}

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

public class Program
{
    static void Main()
    {
        var nm = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
        var abArray = new List<long[]>();
        for (int i = 0; i < nm[0]; i++)
        {
            abArray.Add(Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray());
        }

        abArray.Sort((a,b) => (int)(a[0] - b[0]));

        long price = 0;
        var need = nm[1];
        for (int i = 0; i < nm[0]; i++)
        {
            if (abArray[i][1] > need)
            {
                price += need * abArray[i][0];
                need = 0;
            }
            else
            {
                price += abArray[i][1] * abArray[i][0];
                need -= abArray[i][1];
            }

            if (need == 0)
            {
                Console.WriteLine(price);
                break;
            }
        }
    }
}


Measured memory_bytes: 23864
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Atcoder
{
    class aaaa
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);int A = int.Parse(input[1]);int B = int.Parse(input[2]);

            int planA = N * A;
            if (planA > B) {
                Console.WriteLine(B);
            }else{
                Console.WriteLine(planA);
            }

        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
using namespace std;
void doit(int n)
{
	if(n == 0)
	{
		return;
	}
	int x = n % 2;
	if(n > 0)
	{
		doit(-n / 2);
	}
	else
	{
		doit((-n + 1) / 2);
	}
	if(x == 0)
	{
		printf("0");
	}
	else
	{
		printf("1");
	}
}
int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	if(n == 0)
	{
		printf("0\n");
		return 0;
	}
	doit(n);
	cout<<endl;
	return 0;
}

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

using namespace std;

struct Edge {
    int v[2];
    double d, c;
    Edge() {}
    Edge(int v1, int v2, double d, double c) :
        v{v1, v2}, d(d), c(c) {}
};
bool operator<(const Edge &e1, const Edge &e2) {
    return e1.c >= e2.c;
}
using Edges = vector<Edge>;
using Graph = vector<Edges>;
const double INF = 1e8;

double MinimumTime(const int start, const int goal, const Graph &g) {
    const int n = g.size();
    vector<vector<vector<double>>> tm(n,
                                      vector<vector<double>>(n, vector<double>(31, INF))); // tm[前の頂点][現在の頂点][速度]

    for (int v = 0; v < n; ++v) tm[v][start][1] = 0.0;

    // 前の頂点，現在の頂点，速度，経過時間
    priority_queue<Edge> que;
    for (const auto &e : g[start]) {
        que.push(Edge(start, e.v[1], 1, e.d));
        tm[start][e.v[1]][1] = e.d;
    }

    while (!que.empty()) {
        int prev = que.top().v[0], cur = que.top().v[1];
        double velocity = que.top().d, elapsed = que.top().c;
        que.pop();

        if (tm[prev][cur][velocity] < elapsed) continue;

        for (const auto &e : g[cur]) {
            if (e.v[1] == prev) continue;

            for (int add = -1; add <= 1; ++add) {
                const double nxt_velocity = velocity + add;

                if (nxt_velocity <= 0.0 || e.c < nxt_velocity) continue;

                double tmp_tm = elapsed + e.d / nxt_velocity;
                if (tmp_tm < tm[e.v[0]][e.v[1]][nxt_velocity]) {
                    tm[e.v[0]][e.v[1]][nxt_velocity] = tmp_tm;
                    que.push(Edge(cur, e.v[1], nxt_velocity, tmp_tm));
                }
            }
        }
    }

    double res = INF;
    for (int v = 0; v < n; ++v) res = min(res, tm[v][goal][1]);
    return (INF <= res) ? -1.0 : res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    int n, m, s, g, x, y, d, c;

    while (cin >> n >> m, n) {
        cin >> s >> g;

        Graph graph(n);
        for (int i = 0; i < m; ++i) {
            cin >> x >> y >> d >> c;
            graph[x - 1].emplace_back(Edge(x - 1, y - 1, d, c));
            graph[y - 1].emplace_back(Edge(y - 1, x - 1, d, c));
        }

        double time = MinimumTime(s - 1, g - 1, graph);
        if (time < 0.0) cout << "unreachable\n";
        else cout << time << '\n';
    }

    return 0;
}



Measured memory_bytes: 3952
using System;
using System.Collections;
using System.Collections.Generic;

namespace A
{
    class Program
    {
        public class ab
        {
            public int a;
            public int b;
            public ab(int i, int j)
            {
                a = i;
                b = j;
            }
        }
        static void Main(string[] args)
        {
            int[,] result_arr = new int[100, 2];
            for (int z = 0; z < 100; z++)
            {
                string s = Console.ReadLine();
                if (s == "0 0") break;
                string[] s_arr = s.Split(' ');
                int a = int.Parse(s_arr[0]);
                int b = int.Parse(s_arr[1]);
                double min = 999999;
                double pow_sum = Math.Pow(a, 2) + Math.Pow(b, 2);
                for (int i = 1; i < 150; i++)
                {
                    for (int j = i + 1; j < 150; j++)
                    {
                        double i_j_pow_sum = Math.Pow(i, 2) + Math.Pow(j, 2);
                        if (i_j_pow_sum >= pow_sum && i_j_pow_sum < min)
                        {
                            if (i_j_pow_sum == pow_sum && i > a)
                            {
                                min = i_j_pow_sum;
                                result_arr[z, 0] = i;
                                result_arr[z, 1] = j;
                            }
                            else if (i_j_pow_sum > pow_sum)
                            {
                                min = i_j_pow_sum;
                                result_arr[z, 0] = i;
                                result_arr[z, 1] = j;
                            }
                        }
                    }
                }
            }

            for(int z = 0; z<100; z++)
            {
                if (result_arr[z, 0] != 0) Console.WriteLine(result_arr[z, 0] + " " + result_arr[z, 1]);
            }
        }
    }
}

Measured memory_bytes: 9320
n, k = map(int, input().split())
S = list(map(int, input()))
T = []    
if S[0] == 1:
    T.append(1)
else:
    T.append(0)
    T.append(-1)
for i in range(1, n):
    if S[i] == S[i-1] and S[i] == 1:
        T[-1] += 1
    elif S[i] == S[i-1]:
        T[-1] -= 1
    elif S[i] == 1:
        T.append(1)
    else:
        T.append(-1)
if T[-1] < 0:
    T.append(0)
m = len(T)

ans = []
ans.append(T[0])
for i in range(0, k):
    if 2*i+2 < m:
        ans[0] = ans[0] - T[2*i+1] + T[2*i+2]
    else:
        break

i = 0
j = k+1
ma = ans[0]
while True:
    if 2*j >= m:
        break
    re = ans[-1] - T[2*i] + T[2*i+1] - T[2*j-1] + T[2*j]
    ma = max(ma, re)
    i += 1
    j += 1
    ans.append(re)
    
    
print(ma)



Measured memory_bytes: 6264
#include <bits/stdc++.h>
using namespace std;
int main(void){
    vector<int> A(9);
    int N;
    for(int i=0; i<9; i++){
        cin >> A[i];
    }
    cin >> N;
    vector<int> b(N);
    for(int i=0; i<9; i++){
        for(int j=0; j<N; j++){
            cin >> b[j];
            if(A[i]==b[j]){
                A[i]=1;
            }
        }
    }
    if(A[0]==A[1] && A[1]==A[2]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[3]==A[4] && A[4]==A[5]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[6]==A[7] && A[7]==A[8]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[0]==A[3] && A[3]==A[6]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[1]==A[4] && A[4]==A[7]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[2]==A[5] && A[5]==A[8]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[0]==A[4] && A[4]==A[8]){
        cout << "Yes" ;
        return 0;
    }
    else if(A[2]==A[4] && A[4]==A[6]){
        cout << "Yes" ;
        return 0;
    }
    else cout << "No" ;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
  int a,b,ave;
  scanf("%d %d",&a,&b);
  ave = (a+b)/2;
  if ((a+b)%2!=0) {
    printf("%d",ave+1);
  } else {
    printf("%d",ave);
  }
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc164a
{
    class Program
    {
        static void Main(string[] args)
        {
            //==========================================================================================================================
            //1) input
            List<int> input = Console.ReadLine().Split(' ').Select(int.Parse).ToList();

            //==========================================================================================================================
            //2) output
            string output = "safe";
            if (input[0] <= input[1])
            {
                output = "unsafe";
            }

            Console.WriteLine(output);

        }
    }
}


Measured memory_bytes: 28324
<?php

fscanf(STDIN, "%d %d", $n, $k);
fscanf(STDIN, "%s", $s);
$n = strlen($s);

$nums = [];
$now = 1;
$cnt = 0;
for ($i = 0; $i < $n; ++$i) {
    if ($s[$i] == $now) {
        ++$cnt;
    } else {
        $nums[] = $cnt;
        $now ^= 1;
        $cnt = 1;
    }
}
if ($cnt != 0) $nums[] = $cnt;

if (count($nums) % 2 == 0) $nums[] = 0;

/* echo implode(', ', $nums), PHP_EOL; */

$K = 2 * $k + 1;

$r = 0;
$sum = 0;
$max = 0;
for ($l = 0; $l < count($nums); $l += 2) {
    while ($r < $n && $r - $l < $K) {
        $sum += $nums[$r];
        ++$r;
    }

/* echo "l: $l, r: $r", PHP_EOL; */
    /* if ($r - $l < $K) break; */

    $max = max($max, $sum);
    
    $sum -= $nums[$l];
    $sum -= $nums[$l + 1];
 }

echo $max;


Measured memory_bytes: 10744
#include <cstdio>
#include <queue>

using namespace std;

static const char * itoc
  = "ABCDEFGHIJKLMNOPQRSTUVWXYZ .,-\'?";

template<typename T>
static void
push (
  queue<T>    & lis,
  const char  * s
  )
{
  for ( ; *s != '\0'; ++s )
  {
    lis.push ( *s );
  }

  return ;
}

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  queue<int>  lis;
  int i;

  for ( ; ; )
  {
    const int ch = getchar ( );

    if ( ch == EOF )  break ;
    if ( ch == '\n' )
    {
      while ( !lis.empty ( ) )
      {
        int p = 0;

        for ( i = 0; i < 5; ++i )
        {
          p <<= 1;
          if ( !lis.empty ( ) )
          {
            p |= !!( lis.front ( ) == '1' );
            lis.pop ( );
          }
        }

        putchar ( itoc[ p ] );
      }
      puts ( "" );
      continue ;
    }

    switch ( ch )
    {
      case ' ':   push ( lis, "101" );      break ;
      case '\'':  push ( lis, "000000" );   break ;
      case ',':   push ( lis, "000011" );   break ;
      case '-':   push ( lis, "10010001" ); break ;
      case '.':   push ( lis, "010001" );   break ;
      case '?':   push ( lis, "000001" );   break ;
      case 'A':   push ( lis, "100101" );   break ;
      case 'B':   push ( lis, "10011010" ); break ;
      case 'C':   push ( lis, "0101" );     break ;
      case 'D':   push ( lis, "0001" );     break ;
      case 'E':   push ( lis, "110" );      break ;
      case 'F':   push ( lis, "01001" );    break ;
      case 'G':   push ( lis, "10011011" ); break ;
      case 'H':   push ( lis, "010000" );   break ;
      case 'I':   push ( lis, "0111" );     break ;
      case 'J':   push ( lis, "10011000" ); break ;
      case 'K':   push ( lis, "0110" );     break ;
      case 'L':   push ( lis, "00100" );    break ;
      case 'M':   push ( lis, "10011001" ); break ;
      case 'N':   push ( lis, "10011110" ); break ;
      case 'O':   push ( lis, "00101" );    break ;
      case 'P':   push ( lis, "111" );      break ;
      case 'Q':   push ( lis, "10011111" ); break ;
      case 'R':   push ( lis, "1000" );     break ;
      case 'S':   push ( lis, "00110" );    break ;
      case 'T':   push ( lis, "00111" );    break ;
      case 'U':   push ( lis, "10011100" ); break ;
      case 'V':   push ( lis, "10011101" ); break ;
      case 'W':   push ( lis, "000010" );   break ;
      case 'X':   push ( lis, "10010010" ); break ;
      case 'Y':   push ( lis, "10010011" ); break ;
      case 'Z':   push ( lis, "10010000" ); break ;
    }
  }

  return ( 0 );
}

Measured memory_bytes: 0
from math import floor, ceil

from numpy import argmax

t = []
for each in range(6):
    t.append(int(input()))
n = t[0]
arrivals = [0] * 6
arrivals[0] = t[0]
limits = t[1:]
step = 0

steps = [0] * 5

for i, (num, limit) in enumerate(zip(arrivals, limits)):
    if n > min(limit, min(limits[:i + 1])):
        steps[i] = ceil(n / limit)



# print(steps)
step += max(steps) + 4

print(max(5, step))


Measured memory_bytes: 12500
#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 a, b, c;
  cin >> a >> b >> c;

  int result = max(0, c - (a - b));

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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 (a>b) { a=b; return 1; } return 0; }

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

    string s; cin >> s;
    int cnt = 0;
    rep(i,s.size()-1) if(s[i] != s[i+1]) cnt++;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define eps 0.000001;
using namespace std;
typedef long long ll;
const int inf = 0xfff;
const int maxn = 200005;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
struct node{
    int x, y, d;
    node() { x = y = d = 0; };
};
int main()
{
    int n;
    cin >> n;
    string maze;
    cin >> maze;
    int i = 0, j = n-1;
    int cnt = 0;
    for(int l = 0, r = n - 1; l < r;){
		if(maze[l]=='W'){
			if(maze[r]=='R'){
				swap(maze[l], maze[r]);
				cnt++;
				l++;
			}
			r--;
		}
		else{
			l++;
		}
	}
    cout << cnt << endl;
}

Measured memory_bytes: 3720
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


const int MAX = 2000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a, ll n, ll p){
	if(n==0) return 1;
	if(n%2) return (a*modpow(a, n-1, p))%p;
	if(!(n%2)){
		ll t=modpow(a, n/2, p);
		return (t*t)%p;
	}
}


int main(){
  int k; string s; cin >> k >> s; int n = s.size();
  ll ans = 0;
  COMinit();
  for(int i=0; i<=k; i++){
    ans+=((COM(k-i+n-1, n-1)*modpow(25, k-i, mod))%mod*modpow(26, i, mod))%mod;
    ans%=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 51236
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n,s,l,r;
ll ans,x[100005],p[100005];
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&p[i]);
	l=1,r=n;
	while(s>=x[l]&&s<=x[r])
	{
		ans+=x[r]-x[l];
		if(p[l]<p[r])
		{
			while(p[l]<p[r]&&s>=x[l])
			  p[r]+=p[l],l++;
		}
		else
		{
			while(p[l]>=p[r]&&s<=x[r])
			  p[l]+=p[r],r--;
		}
	}
	if(s<x[l])ans+=x[r]-s;
	else if(s>x[r])ans+=s-x[l];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
using ll = long long;

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

int main() {
    int x;
    cin >> x;
    int i = gcd(x, 360);
    cout << 360 / i << endl;
    return 0;
}

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

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

	static class TaskA {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = in.nextInt();
			}
			int ans = 1;
			int state = 0;
			for (int i = 1; i < n; i++) {
				if (state == 0) {
					if (a[i] < a[i - 1]) {
						state = 1;
					}
					if (a[i] > a[i - 1]) {
						state = 2;
					}
				} else if (state == 1) {
					if (a[i] > a[i - 1]) {
						state = 0;
						++ans;
					}
				} else {
					if (a[i] < a[i - 1]) {
						state = 0;
						++ans;
					}
				}
			}
			out.println(ans);
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}



Measured memory_bytes: 36884
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	int n,m;
	while( cin >> n , n ){
		map<char,char> f;
		for(int i=0 ; i<n ; ++i ){
			char c , c_;
			cin >> c >> c_ ;
			f[c] = c_;
		}
		cin >> m;
		string s;
		for(int i=0 ; i<m ; ++i ){
			char c;
			cin >> c;
			if( f.count( c ) )
				s.push_back( f[c] );
			else
				s.push_back( c );
		}
		cout << s << endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)
 
int main(void) {
  int a, b;cin>>a>>b;
//  if(b==1) return 0;
  cout << (b-1)/(a-1) + ((b-1)%(a-1)==0? 0: 1) << endl;

  return 0;
}

Measured memory_bytes: 256
/*author @dhanush*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define se second
#define fi first
#define INF INT_MAX

int parent[200001];

int find(int a)
{
  if(parent[a]<0)
  {
    return a;
  }
  else
  {
    int x=find(parent[a]);
    parent[a]=x;
    return x;
  }

}

void Union(int a , int b)
{
  parent[a] += parent[b];   //adding size of set b to set a
  parent[b] = a;        //making a , parent of new set
}


int main()
{


  int n , m , a , b;
  cin >> n >> m;

  for (int i = 1; i <= n; i++)
    parent[i] = -1;   //initializing

  while (m--)
  {
    cin >> a >> b;
    a = find(a) , b = find(b);

    if (a != b) Union(a , b);
  }

  int res = -1;

  for (int i = 1; i <= n; i++)
    if (parent[i] < 0)
      res = min(res, parent[i]);

  cout << abs(res);



}







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


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k%2) cout << b - a;
    else cout << a - b;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int N, p[55], c, i;
    scanf("%d", &N);
    c=0;
    for (i=1; i<=N; i++) {
        scanf("%d", &p[i]);
        if (p[i]==i) c++;
    }
    if (c==N || c==N-2) printf("YES");
    else printf("NO");
    return 0;
}


Measured memory_bytes: 128
a, b =  list(map(int, input().split()))
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

print(lcm([a,b]))  # 実行結果: 12

Measured memory_bytes: 5044
using System;
using System.Linq;

namespace arc077_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Array.Reverse(x);
            Console.Write(x[0]);
            for (int i = 2; i < n; i += 2)
            {
                Console.Write(" " + x[i]);
            }
            Array.Reverse(x);
            for (int i = n % 2; i < n; i += 2)
            {
                Console.Write(" " + x[i]);
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 39468
import math
n = int(input())
d = {}
       
for i in range(2,n+1):
  for j in range(2,i+1):
    while i%j == 0:
      i /= j
      if j in d:
        d[j] += 1
      else:
        d[j] = 2
ans = 1
for i in list(d.values()):
  ans *= i
print(ans%(10**9+7))

Measured memory_bytes: 3064
import itertools
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(q):
  A,B,C,D=map(int,input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
L=list(range(1,m+1))
cnt=[]
l=list(itertools.combinations_with_replacement(L,n))
for i in range(len(l)):
  Cnt=0
  tup=l[i]
  for j in range(q): 
    if int(tup[b[j]-1])-int(tup[a[j]-1])==int(c[j]):
      Cnt+=int(d[j])
  cnt.append(Cnt)
print(max(cnt))

Measured memory_bytes: 86160
#include <stdio.h>

#define MAX 1000

void insertion(int *,int);

int main(){
  int A[MAX],key;
  int i=0,j,k;
  int num;

  scanf("%d",&num);
  for(i=0;i<num;i++) scanf("%d",&A[i]);

  insertion(A,num);
  
  /*for(i=1;i<=num;i++){
    key=A[i];
    j=i-1;
    while(j>=0&&A[j]>key){
      A[j+1]=A[j];
	j--;
    }
    A[j+1]=key;
    for(k=1;k<num;k++) printf("%d ",A[k]);
    printf("%d",A[k]);
    printf("\n");
  }
*/
  return 0;
}

//kannsuuka
void insertion(int *A,int len){
  int key;
  int i,j,k;
  
  for(k=0;k<len;k++){
      if(k!=0) printf(" ");
      printf("%d",A[k]);
    }
    printf("\n");
  for(i=1;i<len;i++){
    key=A[i];
    j=i-1;
    while(j>=0&&A[j]>key){
      A[j+1]=A[j];
	j--;
    }
    A[j+1]=key;
    for(k=0;k<len;k++){
      if(k!=0) printf(" ");
      printf("%d",A[k]);
    }
    printf("\n");
  }
}



Measured memory_bytes: 2112
#include<iostream>
 
using namespace std;
 
int main(void){
	int a,b,c,d,e,k;
  	cin>>a>>b>>c>>d>>e>>k;
  	if(e-a>k)cout<<":("<<endl;
  	else cout<<"Yay!"<<endl;
  	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<set> 
#define LL long long 
using namespace std;
int main()
{
	int n,y;
	cin>>n>>y;
	int a=(y/10000)+1;
	int b=(y/5000)+1;
	int c=(y/1000)+1;
	for(int i=0;i<=a;i++)
		for(int j=0;j<=b;j++)
		{
			int k;
			if((y-10000*i-5000*j)%1000==0)
				k=(y-10000*i-5000*j)/1000;
			else
				continue;
			if(k<0) continue;
			if((i+j+k)==n)
			{
				cout<<i<<" "<<j<<" "<<k;
				return 0;
			}
		}
	cout<<-1<<" "<<-1<<" "<<-1;
} 

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

int main(){
  
  int n;
  cin >> n;
  int b =0;
  
  for(int i = n; i > 0; i/=10)
    b += i%10;
  
  if(n%b==0)
    cout << "Yes" << endl;
  else
    cout << "No" <<endl;
}
    

    
 
    
    

Measured memory_bytes: 256