stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

using namespace std;

#define LL long long



int n;

LL W, w[105], v[105];

LL judge;



//int dfs(int now, LL rest, LL value)

//{

//    if(value >= judge) return 1;

//    if(now > n) return 0;

//    int flag1 = 0, flag2 = 0;

//    flag1 = dfs(now + 1, rest, value);

//    if(rest - w[now] >= 0) flag2 = dfs(now + 1, rest - w[now], value + v[now]);

//    if(flag1 + flag2 > 0) return 1;

//    return 0;

//}

//

//int C(LL x)

//{

//    judge = x;

//    if(dfs(1, W, 0)) return 1;

//    else return 0;

//}

//

//int main()

//{

//    while(~scanf("%d %lld", &n, &W))

//    {

//        LL sum = 0;

//        for(int i = 1; i <= n; ++i)

//        {

//            scanf("%lld %lld", &w[i], &v[i]);

//            sum += v[i];

//        }

//        LL l = 0, r = sum, mid;

//        while(l < r)

//        {

//            mid = (l + r) / 2;

//            if(C(mid)) l = mid + 1;

//            else r = mid;

//        }

//        mid = (l + r) / 2;

//        if(!C(mid)) l--;

//        printf("%lld\n", l);

//    }

//}



map<LL, LL> dp[105];



LL dfs(int i, LL cost)

{

    if(cost > W) return -10000000;

    if(i > n) return 0;

    if(dp[i].count(cost)) return dp[i][cost];

    return dp[i][cost] = max(dfs(i + 1, cost + w[i]) + v[i], dfs(i + 1, cost));

}



int main()

{

    while(~scanf("%d %lld", &n, &W))

    {

        for(int i = 1; i <= n; ++i) dp[i].clear();

        for(int i = 1; i <= n; ++i)

            scanf("%lld %lld", &w[i], &v[i]);

        LL ans = dfs(1, 0);

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

    }

}


// Optimized solution to the same problem (faster):
#include       <set>

#include       <map>

#include     <queue>

#include     <cmath>

#include    <cstdio>

#include    <cctype>

#include    <vector>

#include   <cstring>

#include <algorithm>

using namespace std;



typedef long long ll;

const ll mod = 1e9+7;

const double eps = 1e-7;

const int maxn = 105;



ll fast_pow(ll a,ll b,ll mod){

    ll ans = 1;

    while(b){

        if(b&1)

            ans = ans*a%mod;

        a = a*a%mod;

        b>>=1;

    }

    return ans;

}



int w[maxn], v[maxn];

int dp[maxn*4][maxn];



int main(){

    int n, W, c;

    scanf("%d%d",&n,&W);

    for(int i=0;i<n;i++)

        scanf("%d%d",&w[i],&v[i]);

    for(int i=1;i<n;i++)

        w[i] -= w[0]-1;

    c = w[0]-1;

    w[0] = 1;

    for(int i=0;i<n;i++)

        for(int j=n*4;j>=w[i];j--)

            for(int k=1;k<=i+1;k++){

                dp[j][k] = max(dp[j][k],dp[j-w[i]][k-1]+v[i]);

    }

    int ans = 0;

    for(int j=n*4;j>=0;j--)

        for(int k=1;k<=n;k++){

            if(1ll*k*c+j<=W){

                ans = max(ans,dp[j][k]);

            }

    }

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

    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

//#pragma GCC optimize("O3")

//#pragma GCC target ("sse4")

using namespace std;

#define PB push_back

#define all(x) (x).begin(),(x).end()

#define MEM(x,a) memset((x),a,sizeof((x)))

#define F first

#define S second

#define imx INT_MAX

#define inI(x) scanf("%d",&x)

#define inI2(x,y) scanf("%d %d",&x,&y)

#define inI3(x,y,z) scanf("%d %d %d",&x,&y,&z)

const long long MOD = (long long)(1e9+7);

const long long MMX = (long long)(1e18);

typedef long long LL;

long long n,w,val[105],ww[105],k=MMX,dp[105][1000],ans=0;

int main()

{

    for(int i=0;i<105;i++)for(int j=0;j<1000;j++)dp[i][j]=-1;

    dp[0][0]=0;

    scanf("%lld %lld",&n,&w);

    for(int i=1;i<=n;i++)

    {

        scanf("%lld %lld",&ww[i],&val[i]);

        k=min(k,ww[i]);

    }

    for(int i=1;i<=n;i++)ww[i]-=k;

    for(int t=1;t<=n;t++)

    {

        for(int i=100;i>=0;i--)

        {

            for(int j=1000;j>=0;j--)

            {

                if(dp[i][j]!=-1)

                {

                    dp[i+1][j+ww[t]]=max(dp[i+1][j+ww[t]],dp[i][j]+val[t]);

                }

            }

        }

    }

    for(int i=0;i<105;i++)for(int j=0;j<1000;j++)if(((i*k)+j)<=w)ans=max(ans,dp[i][j]);

    printf("%lld",ans);

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define PB(x) push_back(x)

#define MP(x,y) make_pair(x,y)



map<long long,long long> mp;

long long ty[5];

long long nty;

vector<long long> a[5];



main()

{

	long long n;

	long long w;

	scanf("%lld %lld",&n,&w);

	for(long long i=0;i<n;i++)

	{

		long long v;

		long long w;

		scanf("%lld %lld",&w,&v);

		if(mp[w]==0)

		{

			nty++;

			ty[nty]=w;

			mp[w]=nty;

			a[mp[w]].PB(v);

		}

		else

		{

			a[mp[w]].PB(v);

		}

	}

	for(long long i=1;i<=nty;i++)

		sort(a[i].begin(),a[i].end());

	long long ans=0;

	a[1].PB(0);

	a[2].PB(0);

	a[3].PB(0);

	a[4].PB(0);

	long long s1=0,s2=0,s3=0,s4=0;

	for(long long i=a[1].size()-1,ni=0;i>=0;i--,ni++)

	{

		long long all=0;

		long long wei=ni*ty[1];

		s1+=a[1][i];

		all=s1;

		if(wei>w)break;

		s2=0;

		ans=max(ans,all);

		for(long long j=a[2].size()-1,nj=0;j>=0;j--,nj++)

		{

			long long wei2=nj*ty[2];

			s2+=a[2][j];

			long long all2=s2;

			if(wei+wei2>w)break;

			s3=0;

			ans=max(ans,all+all2);

			for(long long k=a[3].size()-1,nk=0;k>=0;k--,nk++)

			{

				long long wei3=nk*ty[3];

				s3+=a[3][k];

				long long all3=s3;

				if(wei+wei2+wei3>w)break;

				s4=0;

				ans=max(ans,all+all2+all3);

				for(long long l=a[4].size()-1,nl=0;l>=0;l--,nl++)

				{

					long long wei4=nl*ty[4];

					s4+=a[4][l];

					long long all4=s4;

					if(wei+wei2+wei3+wei4>w)break;

					ans=max(ans,all+all2+all3+all4);

				}

			}

		}	

	}

	printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// glory be to the sky

#include<bits/stdc++.h> 

#define pb push_back

using namespace std;

	

typedef long long ll; 





ll W;

ll w[105], v[105];

int n;

map<pair<int, ll>, ll > mep;



ll f(int curr, ll rem) {

	if (curr == 0) return 0;

	pair<int, ll> param = make_pair(curr, rem);

	if (mep.count(param)) return mep[param];

	ll ans = 0, t1, t2;

	if (rem >= w[curr]) {

		t1 = f(curr - 1, rem - w[curr]) + v[curr];

		ans = max(ans, t1);

	}

	t2 = f(curr - 1, rem);

	ans = max(ans, t2);

	return mep[param] = ans;

}

int main(){



	ios::sync_with_stdio(false);

	cin.tie(0);



	cin >> n >> W;

	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

	ll ans = f(n, W);

	cout << ans;

	return 0;	

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

struct huowu

{

	int w,v;

}g[105];

huowu A[105], B[105], C[105], D[105];

bool cmp(huowu a,huowu b)

{

	return a.v > b.v;

}

int n,W;

int main()

{

	scanf("%d %d",&n,&W);

	int a, b, c, d, f;

	a = b = c = d = f = 0;

	for(int i = 1;i <= n;i++)

	{

		scanf("%d %d",&g[i].w,&g[i].v);

		if(g[i].w == g[1].w)

		{

			A[++a] = g[i];

		}

		else if(g[i].w == g[1].w + 1)

		{

			B[++b] = g[i];

		}

		else if(g[i].w == g[1].w + 2)

		{

			C[++c] = g[i];

		}

		else if(g[i].w == g[1].w + 3)

		{

			D[++d] = g[i];

		}

	}

	sort(A + 1,A + 1 + a,cmp);

	sort(B + 1,B + 1 + b,cmp);

	sort(C + 1,C + 1 + c,cmp);

	sort(D + 1,D + 1 + d,cmp);

	LL swa[110],swb[110],swc[110],swd[110];

	LL sva[110],svb[110],svc[110],svd[110];

	swa[0] = swb[0] = swc[0] = swd[0] = 0;  

    sva[0] = svb[0] = svc[0] = svd[0] = 0;  

    for(int i = 1;i <= a;i++)  

    {  

        swa[i] = swa[i - 1] + A[i].w;  

        sva[i] = sva[i - 1] + A[i].v;  

    }  

    for(int i = 1;i <= b;i++)  

    {  

        swb[i] = swb[i - 1] + B[i].w;  

        svb[i] = svb[i - 1] + B[i].v;  

     }  

     for(int i = 1;i <= c;i++)  

     {  

         swc[i] = swc[i - 1] + C[i].w;  

         svc[i] = svc[i - 1] + C[i].v;  

     }  

     for(int i = 1;i <= d;i++)  

     {  

        swd[i] = swd[i - 1] + D[i].w;  

        svd[i] = svd[i - 1] + D[i].v;  

      }  

    int sumv = 0;  

    int ans = 0;  

	for(int i = 0;i <= a;i++)  

    {  

         for(int j = 0;j <= b;j++)  

         {  

            for(int k = 0;k <= c;k++)  

            {  

             for(int l = 0;l <= d;l++)  

              {  

			      LL sum = swa[i] + swb[j] + swc[k] + swd[l];  

					if(sum <= (LL)W)  

					{  

                      f = max((LL)f,sva[i] + svb[j] + svc[k] + svd[l]);  

					}  

			 }  

            }  

        }  

    }  

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

    return 0;  

}  

	

	

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <map>



using namespace std;



typedef long long ll;

const int Maxn = 1e9 + 10;

const int N = 1e5 + 10;

const int INF=(0x7fffffff)/2;

int dp[105][305];

int n, W;

int w[105], v[105];

int d, ans=0;

int main(){

	int i, j, k;

	while(~scanf("%d%d",&n,&W)){

		for(i = 1; i <= n; i++)

			scanf("%d %d", &w[i], &v[i]);

		for(i = 0; i <= n; i++)

			for(j = 0; j <= 300; j++)

				dp[i][j]=0;

		for(i = 1; i <= n; i++)

			for(j = n; j > 0; j--)

				for(k = 300; k >= 0; k--){

				d = w[i] - w[1];

				if(k < d)

					break;

				dp[j][k] = max(dp[j][k], dp[j-1][k-d] + v[i]);

				}

		for(i = 0; i <= n; i++)

			for(j = 0; j <= 300; j++)

				if(1ll * i * w[1] + 1ll * j <= 1ll * W)

					ans = max(ans, dp[i][j]);

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

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

struct huowu

{

	int w,v;

}g[105];

huowu A[105], B[105], C[105], D[105];

bool cmp(huowu a,huowu b)

{

	return a.v > b.v;

}

int n,W;

int main()

{

	scanf("%d %d",&n,&W);

	int a, b, c, d, f;

	a = b = c = d = f = 0;

	for(int i = 1;i <= n;i++)

	{

		scanf("%d %d",&g[i].w,&g[i].v);

		if(g[i].w == g[1].w)

		{

			A[++a] = g[i];

		}

		else if(g[i].w == g[1].w + 1)

		{

			B[++b] = g[i];

		}

		else if(g[i].w == g[1].w + 2)

		{

			C[++c] = g[i];

		}

		else if(g[i].w == g[1].w + 3)

		{

			D[++d] = g[i];

		}

	}

	sort(A + 1,A + 1 + a,cmp);

	sort(B + 1,B + 1 + b,cmp);

	sort(C + 1,C + 1 + c,cmp);

	sort(D + 1,D + 1 + d,cmp);

	LL swa[110],swb[110],swc[110],swd[110];

	LL sva[110],svb[110],svc[110],svd[110];

	swa[0] = swb[0] = swc[0] = swd[0] = 0;  

    sva[0] = svb[0] = svc[0] = svd[0] = 0;  

    for(int i = 1;i <= a;i++)  

    {  

        swa[i] = swa[i - 1] + A[i].w;  

        sva[i] = sva[i - 1] + A[i].v;  

    }  

    for(int i = 1;i <= b;i++)  

    {  

        swb[i] = swb[i - 1] + B[i].w;  

        svb[i] = svb[i - 1] + B[i].v;  

     }  

     for(int i = 1;i <= c;i++)  

     {  

         swc[i] = swc[i - 1] + C[i].w;  

         svc[i] = svc[i - 1] + C[i].v;  

     }  

     for(int i = 1;i <= d;i++)  

     {  

        swd[i] = swd[i - 1] + D[i].w;  

        svd[i] = svd[i - 1] + D[i].v;  

      }  

    int sumv = 0;  

    int ans = 0;  

	for(int i = 0;i <= a;i++)  

    {  

         for(int j = 0;j <= b;j++)  

         {  

            for(int k = 0;k <= c;k++)  

            {  

             for(int l = 0;l <= d;l++)  

              {  

			      LL sum = swa[i] + swb[j] + swc[k] + swd[l];  

					if(sum <= (LL)W)  

					{  

                      f = max((LL)f,sva[i] + svb[j] + svc[k] + svd[l]);  

					}  

			 }  

            }  

        }  

    }  

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

    return 0;  

}  

	

	

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 100000 + 10;



const int Up = 0;

const int Down = 1;



int n;

int aa[N];

int dp[N][2];



int main() {

	scanf( "%d", &n );

	for( int i = 1; i <= n; i++ ) {

		scanf( "%d", aa + i );

	}

	memset( dp, 0x3f, sizeof(dp) );

	dp[1][Up] = dp[1][Down] = 1;

	for( int i = 2; i <= n; i++ ) {

		dp[i][Up] = dp[i-1][Up] + (aa[i] < aa[i-1]);

		dp[i][Down] = dp[i-1][Down] + (aa[i] > aa[i-1]);

		dp[i][Up] = min( dp[i][Up], dp[i-1][Down] + 1 );

		dp[i][Down] = min( dp[i][Down], dp[i-1][Up] + 1 );

	}

	printf( "%d\n", min(dp[n][Up],dp[n][Down]) );

}




// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

const int N = 1e5 + 10;



int n, a[N];



int main()

{

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

	int ans = 0;

	for (int i = 1; i <= n; )

	{

		bool ii = 0, d = 0;

		int j;

		for (j = i + 1 ; j <= n; j++)

		{

			if(a[j] > a[j - 1])

			{

				ii = 1;

			}

			else if(a[j] < a[j - 1])

			{

				d = 1;

			}

			if (ii && d)

			{

				break;

			}

		}

		i = j;

		ans++;

	}

	cout << ans << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <fstream>

#include <map>

#include <set>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#define mod 1000000007

using namespace std;



int main()

{

    //freopen("1.txt", "r", stdin);

    int n; cin >> n;

    vector<int> v(n, 0);

    int flag = 0;

    int ret = 1;

    for (int i = 0; i < n; ++i) {

        cin >> v[i];

        if (i == 0) continue;

        if (flag == 1) {

            if (v[i] < v[i - 1]) {

                flag = 0;

                ++ret;

            }

        } else if (flag == -1) {

            if (v[i] > v[i - 1]) {

                flag = 0;

                ++ret;

            }

        } else {

            if (v[i] > v[i - 1]) flag = 1;

            else if (v[i] < v[i - 1]) flag = -1;

        }

    }

    cout << ret << '\n';

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#define N 200010

using namespace std;

int n, a[N];

int sgn(int x) {

	return x < 0 ? -1 : x > 0;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

	if (n == 1) {

		puts("1");

		return 0;

	}

	

	int flag;

	if (a[1] == a[2]) flag = 0;

	else flag = (a[1] < a[2] ? -1 : 1);

	int ans = 1;

	for (int i = 3; i <= n; ++i) {

		if (!flag || sgn(a[i - 1] - a[i]) == 0 || sgn(a[i - 1] - a[i]) == flag) {

			if (sgn(a[i - 1] - a[i])) flag = sgn(a[i - 1] - a[i]);

		}

		else {

			flag = 0;

			++ans;

		}

	}

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

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



int sign(int x) {

	return (x > 0) - (x < 0);

}



int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);



	int n; std::cin >> n;

	int ans = 0, t = 0, last = -1;

	for (int i = 0; i < n; ++ i) {

		int x; std::cin >> x;

		if (!i || (sign(x - last) * t == -1)) {

			++ ans; t = 0;

		}

		else if (!t && sign(x - last)) {

			t = sign(x - last);

		}

		last = x;

	}



	std::cout << ans << std::endl;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include<vector>

using namespace std;

 

int main()

{

	int N;

	cin >> N;

	vector<int> A(N);

	for (int i = 0; i < N; i++) {

		cin >> A[i];

	}

	int f = 0, res = 1;

	for (int i = 1; i < N; i++) {

		if (A[i] > A[i - 1]) {

			if (f > 0) {

				;

			}

			else if (f < 0) {

				f = 0;

				res++;

			}

			else {

				f = 1;

			}

		}

		else if (A[i] == A[i - 1]) {

			;

		}

		else {

			if (f > 0) {

				f = 0;

				res++;

			}

			else if (f < 0) {

				;

			}

			else {

				f = -1;

			}

		}

	}

	cout << res << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

#define max_n 100005



int a[max_n];



int main()

{

	int n,k=1,ans,i;

	bool flag,res=false;

	scanf("%d",&n);

	scanf("%d",&a[0]);

	if(n==1)

	{

		printf("1\n");

		return 0;

	}

	ans=a[0];

	for(i=1;i<n;i++)

	{

		scanf("%d",&a[i]);

//		for(;i<n;i++)

//		{

//			scanf("%d",&a[i]);

//			

//		}

		if(!res)

		{

			if(a[i]>ans)

			{

				flag=true;

				res=true;

				ans=a[i];

			}

			else if(a[i]<ans)

			{

				flag=false;

				res=true;

				ans=a[i];

			}

		}

		else

		{

			if(flag)

			{

				if(a[i]>=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

			else

			{

				if(a[i]<=ans)

					ans=a[i];

				else

				{

					k++;

					ans=a[i];

					res=false;

				}

			}

		}

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N];

int main()

{

	int n;

	cin>>n;

	//vector<int> a(n);

	for(int i=1;i<=n;i++) cin>>a[i];

	int ans=0;

	for(int i=1,j;i<=n;i=j+1){

		j=i;

		ans++;

		while(j+1<=n&&a[i]==a[j+1]) j++;

		if(j+1<=n){

			if(a[i]<a[j+1]) 

				while(j+1<=n&&a[j]<=a[j+1]) j++;

			else

				while(j+1<=n&&a[j]>=a[j+1]) j++;

		}

	}

	cout<<ans<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h> 

main()

{

	long long z[100005],i,j,k=0,l=0,t=0,n;

	scanf("%lld",&n);

	for(i=0;i<n;i++)

	scanf("%lld",&z[i]);

	for(i=0;i<n-1;i++)

	{

		if(k==0)

		{

			for(j=i+1;j<n;j++)

			{

				if(z[i]!=z[j])

				{

					if(z[j]>z[i])

						k=1;

					else

						k=-1;

					i=j-1;

					break;

				}

			}

		}

		else

		{

			if(k==1&&z[i+1]<z[i])

				{l++;k=0;t=1;}

			if(k==-1&&z[i+1]>z[i])

			{	l++;k=0;t=1;}

		}

	}

	

	printf("%lld\n",l+1);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int main()

{

	int n;

	cin>>n;

	long long a[100000+5]={0};

	for(int i=0;i<n;i++)

		cin>>a[i];

	int num=0;

	int i=0;

	while(i<n)

	{

		if(i==n-1)

		{num++;break;}

		if(a[i]<a[i+1])

		{

			int j;

			for(j=i;j<n;j++)

			{

				if(a[j]<=a[j+1])

					continue;

				else

					break;

			}

			num++;

			i=j+1;

		}

		else if(a[i]>a[i+1])

		{

			int j;

			for(j=i;j<n;j++)

			{

				if(a[j]>=a[j+1])

					continue;

				else

					break;

			}

			num++;

			i=j+1;

		}

		else if(a[i]==a[i+1])

		{

			i++;

		}

		else

		{

			num++;

			i++;

		}

	}

	cout<<num<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



const int N = 1e5 + 10;



int a[N];



int main(){

	int n, cnt, p, flag;

	scanf("%d",&n);

	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);

	if (n <= 2){

		printf("1\n");

		return 0;

	}

	cnt = 1; p = 2; flag = 0;

	if (a[p] > a[p - 1]) flag = 1;

	else if (a[p] < a[p - 1]) flag = -1;

	p++;

	while (p <= n){

		if ((a[p] > a[p - 1] && flag == -1) || (a[p] < a[p - 1] && flag == 1)){

			cnt++;

			if (n - p <= 1) break;

			p++;

			flag = 0;

			if (a[p] > a[p - 1]) flag = 1;

			else if (a[p] < a[p - 1]) flag = -1;

			p++;

		}

		else{

			if (a[p] > a[p - 1]) flag = 1;

			else if (a[p] < a[p - 1]) flag = -1;

			p++;

		}

	}

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

	return 0;

}

// Fastest known solution for this problem: