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

using namespace std;

typedef long long ll;

typedef pair<ll, ll> lpair;

const ll MOD = 1e9 + 7;

const ll INF = 1e18;

#define rep(i,m,n) for(ll i = (m); i < (n); i++)

#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)

#define print(x) cout << (x) << endl;

#define print2(x,y) cout << (x) << " " << (y) << endl;

#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;

int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N;

    ll A[200010];

    cin >> N;

    rep(i,0,N) cin >> A[i];

    ll sum[200010] = {};

    rep(i,0,N) sum[i+1] = sum[i] + A[i];

    ll ans = 0;

    map<ll,ll> mp;

    rep(i,0,N+1) mp[sum[i]]++;

    for(auto &e: mp){

        ans += e.second * (e.second-1) / 2;

    }

    print(ans);

    

}

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

using namespace std;

typedef long long ll;

typedef pair<ll, ll> lpair;

const ll MOD = 1e9 + 7;

const ll INF = 1e18;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)

#define print(x) cout << (x) << endl;

#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;

int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    

    int n;cin>>n;

    ll ary[n];

    rep(i,n) cin >> ary[i];

    ll ruisekiwa[n+1];

    ruisekiwa[0] = 0;

    map<ll, ll> mp;

    mp[0] = 1;

    rep(i,n)

    {

        ruisekiwa[i+1] = ruisekiwa[i]+ary[i];

        if (mp.find(ruisekiwa[i+1])==mp.end())

        {

            mp[ruisekiwa[i+1]] = 1;

        }

        else

        {

            mp[ruisekiwa[i+1]]++;

        }

    }

    ll ans = 0;

    for (auto itr = mp.begin(); itr != mp.end(); ++itr)

    {

        ans += itr->second * (itr->second-1) / 2;

        // std::cout << "key = " << itr->first           // キーを表示

        //                 << ", val = " << itr->second << "\n";    // 値を表示

    }

    cout << ans << endl;



}


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

using namespace std;

typedef long long ll;

const int maxn=2e5+7;

int a[maxn],cnt[maxn]={0};

ll pre[maxn]={0},jie[maxn];

void init()

{

    jie[0]=0;

    jie[1]=1;

    for(int i=2;i<maxn;++i)

        jie[i]=i+jie[i-1];

}

int main()

{

    ios::sync_with_stdio(false);

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

    init();

    int n;

    cin>>n;

    ll ans=0;

    set<int> st;

    map<ll,int> mp;

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

        cin>>a[i];

        pre[i]=a[i]+pre[i-1];

        mp[pre[i]]++;

    }

    map<ll,int>::iterator it=mp.begin();

    for(;it!=mp.end();++it){

        if(it->first==0)

            ans+=jie[it->second];

        else

            ans+=jie[it->second-1];

    }

    cout<<ans<<endl;

    return 0;

}




// Optimized solution to the same problem (faster):
/*

 * Author : Andrew J

*/

#include <bits/stdc++.h>

using namespace std;

#define rall(x) x.rbegin() , x.rend()

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

#define fi first

#define se second

#define pb push_back

using ll = long long;

using ii = pair <ll , ll>;

void in(ll &x);

const ll N = 2e5 + 10;

#define singleCase

// #define multipleCase

ll n,a[N],ps[N];

map <ll , ll> freq;



void work() {

   in(n);

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

      in(a[i]);

      ps[i] = ps[i - 1] + a[i];

   }

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

      freq[ps[i]]++;

   }

   ll sol = 0;

   for (ii x : freq) {

      sol += (x.se * (x.se - 1)) / 2;

   }

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

   return;

}



int main() {

   #ifdef multipleCase

      ll nQ; in(nQ);

      while (nQ--)

         work();

   #endif

   #ifdef singleCase

      work();

   #endif

   return 0;

}



void in(ll &x) {

	bool neg = false;

	register ll c;

	x = 0;

	c = getchar();

	if(c == '-') {

		neg = true;

		c = getchar();

	}

	for (; c > 47 && c < 58; c = getchar())

	  x = (x << 1) + (x << 3) + c - 48;

	if (neg) x *= -1;

}


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

#include <vector>

#include <map>

typedef long long ll;



std::map<ll, ll> mp;



int main()

{

	ll n;

	std::vector<ll> arr(200005);



	ll ans = 0;



	std::cin >> n;

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

		std::cin >> arr[i];

	}



	mp[0] = 1;

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

		arr[i] = arr[i] + arr[i - 1];



		ans = ans + mp[arr[i]];

		mp[arr[i]]++;

	}



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



	return 0;

}


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

#include <set>

#include <map>

using namespace std; // 575;



map<long long, long long> ms; // ms... Windowsっぽくね？

long long n;

long long a[200005];

long long ans;



int main()

{

    cin >> n;

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

        cin >> a[i];

    }



    ms[0] = 1;

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

        a[i] += a[i - 1];



        ans += ms[a[i]];

        ms[a[i]] += 1;

    }



    cout << ans << endl;

    

    return 0;

}


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

#include <vector>

#include <map>

using namespace std;



map<long long, long long> mp;



int main()

{

	long long n;

	vector<long long> vec(2 * 100005);

	long long ans = 0;



	cin >> n;

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

		cin >> vec[i];

	}



	mp[0] = 1;

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

		vec[i] += vec[i - 1];



		ans = ans + mp[vec[i]];

		mp[vec[i]]++;

	}



	cout << ans << endl;



	return 0;

}


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

#include <set>

#include <map>

using namespace std; // 575;



map<long long, long long> ms; // ms... Windowsっぽくね？

long long n;

long long a[200005];

long long ans;



int main()

{

    cin >> n;

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

        cin >> a[i];

    }



    ms[0] = 1;

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

        a[i] += a[i - 1];



        ans += ms[a[i]];

        ms[a[i]] += 1;

    }



    cout << ans << endl;

    

    return 0;

}


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

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000

#define int long long



signed main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N; cin >> N;

    int a[200010];

    rep(i, N) cin >> a[i];

    int sum[200010] = {};

    rep(i, N) sum[i + 1] = sum[i] + a[i];

    map<int, int> mp;

    rep(i, N + 1) mp[sum[i]]++;

    int ans = 0;

    int num = 0;

    rep(i, N) {

        ans += mp[num] - 1;

        mp[sum[i]]--;

        num += a[i];

    }

    cout << ans << endl;



    return 0;

}


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

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000

#define int long long

int a[200010];

int sum[200010];

map<int, int> mp;

signed main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n; cin >> n;

    

    rep(i, n) cin >> a[i];

    rep(i, n) sum[i + 1] = sum[i] + a[i];

    rep(i, n + 1) {

        mp[sum[i]]++;

    }

    int ans = 0;

    rep(i, n) {

        mp[sum[i]]--;

        ans += mp[sum[i]];

    }

    cout << ans << endl;



    return 0;

}


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

using namespace std;

int main ()

{

int k,x;

cin>>k>>x;

if (k*500 >= x) cout << "Yes";

else cout << "No";

return 0;

}

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



int main(){

int a,b;

scanf("%d%d", &a,&b);

if(a*500>=b)puts("Yes");

else puts("No");

	return 0;

}

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

using namespace std;

main()

{

int K,X,N;

cin>>K>>X;

K<=500;

K=500*K;

if(K>=X)

    cout<<"Yes";

else

    cout<<"No";

}




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

int main()

{

    int a ;

    scanf("%d",&a);

    

    int b;

    scanf("%d",&b);

    

    int c = a*500;

    

    if( c>=b){

        printf("Yes");



    }

    

    else{

        printf("No");

    }



    return 0;

}

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

using namespace std;



int main() 

{

	int k,x;

	cin>>k>>x;

	k=k*500;

	if(k>=x)

	printf("Yes\n");

	else

	printf("No\n");

}

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

int main()

{

    int a ;

    scanf("%d",&a);

    

    int b;

    scanf("%d",&b);

    

    int c = a*500;

    

    if( c>=b){

        printf("Yes");



    }

    

    else{

        printf("No");

    }



    return 0;

}

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

using namespace std;

int main()

{

    int K , X , Y, into;

    cin >> Y >> X;

    K = 500;

    into = K*Y;

    if (into >= X) cout << "Yes" << endl ;

    else cout << "No" << endl;

    return 0;

}

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



int main(){

 	int K,X;

 	scanf("%d %d", &K, &X );

 	int sum = K*500;

 	if(sum >= X){

 		puts("Yes");

	 }

	 else{

	 	puts("No");

	}

	return 0;

 }

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

using namespace std;

int main()

{

    int a,b;

    cin>>a>>b;

    int c=a*500;



    if(c>=b)

        cout<< "Yes"<<endl;

    if(c<b)

        cout<< "No"<<endl;

    return 0;

}




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



int main(){

 	int K,X;

 	scanf("%d %d", &K, &X );

 	int sum = K*500;

 	if(sum >= X){

 		puts("Yes");

	 }

	 else{

	 	puts("No");

	}

	return 0;

 }

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

using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))

#define REP(i, n) FOR(i, n, 0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll)1e15;



bool L[200005];



int main()

{

    ll N;

    string S;

    cin >> N >> S;

    memset(L, 0, sizeof(L));

    ll l = 0;

    REP(i, 2 * N)

    {

        if (l % 2 == 0 && S[i] == 'B')

        {

            L[i] = true;

            l++;

        }

        else if (l % 2 == 1 && S[i] == 'W')

        {

            L[i] = true;

            l++;

        }

        else

            l--;

    }

    if (l != 0)

    {

        cout << 0 << endl;

        return 0;

    }



    ll ans = 1;

    ll r = 0;

    REP(i, 2 * N)

    {

        if (!L[2 * N - 1 - i])

            r++;

        else

            ans = (ans * r--) % MOD;

    }

    REP(i, N)

    {

        ans = (ans * (i + 1)) % MOD;

    }

    cout << ans << endl;

    return 0;

}

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



using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))

#define REP(i, n) FOR(i,n,0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll) 1e15;



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N;

    cin >> N;

    string S;

    cin >> S;

    ll L = 0;

    ll ans = 1;

    REP(i, 2 * N) {

        if (S[i] == 'W') {

            if (L % 2 == 0) {

                ans = (ans * L) % MOD;

                L--;

            }

            else

                L++;

        }

        else {

            if (L % 2 == 0)

                L++;

            else {

                ans = (ans * L) % MOD;

                L--;

            }

        }

    }

    if (L != 0)

        ans = 0;



    REP(i, N) {

        ans = (ans * (i + 1)) % MOD;

    }

    cout << ans << endl;

    return 0;

}

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

using namespace std;

#define finish(x) return cout << x << endl, 0

#define ll long long



const int N = 100001;



int n, dp[2 * N], mod = 1e9 + 7;

vector <int> a;



int solve(int idx, int open){

    if(idx == 2 * n) return open == 0;

    if(open < 0) return 0;

    if(dp[idx] != -1) return dp[idx];

    if(((open & 1) ^ a[idx]) == 0) return 1LL * open * solve(idx + 1, open - 1) % mod;

    return solve(idx + 1, open + 1);

}

int main(){

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    memset(dp, -1, sizeof dp);

    cin >> n;

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

        char c;

        cin >> c;

        a.push_back(c == 'W' ? 0 : 1);

    }

    int ans = solve(0, 0);

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

        ans = 1LL * ans * i % mod;

    }

    cout << ans << endl;

}


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

using namespace std;

#define finish(x) return cout << x << endl, 0

#define ll long long



const int N = 100001;



int n, mod = 1e9 + 7;

vector <int> a;



int main(){

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

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

        char c;

        cin >> c;

        a.push_back(c == 'W' ? 0 : 1);

    }

    int open = 0;

    int ans = 1;

    for(auto &i : a){

        if(open < 0) finish(0);

        if(((open & 1) ^ i) == 0){

            ans = 1LL * ans * open % mod;

            open--;

        }

        else open++;

    }

    if(open) finish(0);

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

        ans = 1LL * ans * i % mod;

    }

    cout << ans << endl;

}


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

using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef tuple<int, int, int> T;

const int INF = 1 << 27;

const ll LLINF = (ll)1 << 60;

const ll MOD = 1e9+7;



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

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



int main() {

  int n;

  scanf("%d", &n);

  vector<T> blocks;

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

    int w, s, v;

    scanf("%d %d %d", &w, &s, &v);

    blocks.emplace_back(s, w, v);

  }



  sort(blocks.begin(), blocks.end(), [](T& t1, T& t2) {return get<0>(t1) + get<1>(t1) < get<0>(t2) + get<1>(t2);});



  const int MAXS = 2e4+10;

  vector<vector<ll>> dp(n, vector<ll>(MAXS, 0));

  for (int s = get<1>(blocks[0]); s < MAXS; s++) {

    dp[0][s] = get<2>(blocks[0]);

  }

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

    auto& block = blocks[i];

    int slimit = get<0>(block);

    int w = get<1>(block), v = get<2>(block);

    for (int s = 0; s < w; s++) {

      dp[i][s] = dp[i-1][s];

    }

    for (int s = w; s < MAXS; s++) {

      dp[i][s] = max(dp[i-1][s], v + dp[i-1][min(s - w, slimit)]);

    }

  }

  

  printf("%lld\n", dp[n-1][MAXS - 1]);

}


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

using namespace std;



typedef long long ll;

typedef pair<int, int> P;

typedef tuple<int, int, int> T;

const int INF = 1 << 27;

const ll LLINF = (ll)1 << 60;

const ll MOD = 1e9+7;



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

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



int main() {

  int n;

  scanf("%d", &n);

  vector<T> blocks;

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

    int w, s, v;

    scanf("%d %d %d", &w, &s, &v);

    blocks.emplace_back(s, w, v);

  }



  sort(blocks.begin(), blocks.end(), [](T& t1, T& t2) {return get<0>(t1) + get<1>(t1) < get<0>(t2) + get<1>(t2);});



  const int MAXS = 2e4+10;

  vector<ll> dp(MAXS, 0);

  for (int s = get<1>(blocks[0]); s < MAXS; s++) {

    dp[s] = get<2>(blocks[0]);

  }

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

    auto& block = blocks[i];

    int slimit = get<0>(block);

    int w = get<1>(block), v = get<2>(block);

    for (int s = MAXS - 1; s >= w; s--) {

      dp[s] = max(dp[s], v + dp[min(s - w, slimit)]);

    }

  }



  printf("%lld\n", dp[MAXS - 1]);

}


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

using namespace std;

typedef long long ll;

#define i_7 (ll)(1E9+7)

#define i_5 (ll)(1E9+5)

ll mod(ll a){

    ll c=a%i_7;

    if(c>=0)return c;

    else return c+i_7;

}

typedef pair<int,int> i_i;

typedef pair<ll,ll> l_l;

ll inf=(ll)1E12;

#define rep(i,l,r) for(ll i=l;i<=r;i++)

#define pb push_back

ll max(ll a,ll b){if(a<b)return b;else return a;}

ll min(ll a,ll b){if(a>b)return b;else return a;}

void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);

void Min(ll * pos,ll val){*pos=min(*pos,val);}

void Add(ll * pos,ll val){*pos=mod(*pos+val);}

const long double EPS=1E-8;

////////////////////////////////////////





struct tower{

    ll w,s,v;

};

bool comp(tower t1,tower t2){

    if(t1.w+t1.s<t2.w+t2.s)return true;

    else return false;

}



int main(){

    ll n;cin>>n;

    tower t[n];

    rep(i,0,n-1){

        cin>>t[i].w>>t[i].s>>t[i].v;

    }

    sort(t,t+n,comp);

    ll N=30005;

    ll dp[n+1][N];

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

    rep(i,0,n-1){

        rep(j,0,N-1){

            dp[i+1][j]=dp[i][j];

            if(0<=j-t[i].w&&j-t[i].w<=t[i].s)Max(&dp[i+1][j],dp[i][j-t[i].w]+t[i].v);

        }

    }

    /*rep(i,0,n){

        rep(j,0,20){

            cout<<dp[i][j]<<" ";

        }cout<<endl;

    }*/

    ll ans=0;rep(i,0,N-1)Max(&ans,dp[n][i]);

    cout<<ans<<endl;

    return 0;

}










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

using namespace std;

typedef long long ll;

#define i_7 (ll)(1E9+7)

#define i_5 (ll)(1E9+5)

ll mod(ll a){

    ll c=a%i_7;

    if(c>=0)return c;

    else return c+i_7;

}

typedef pair<int,int> i_i;

typedef pair<ll,ll> l_l;

ll inf=(ll)1E12;

#define rep(i,l,r) for(ll i=l;i<=r;i++)

#define pb push_back

ll max(ll a,ll b){if(a<b)return b;else return a;}

ll min(ll a,ll b){if(a>b)return b;else return a;}

void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);

void Min(ll * pos,ll val){*pos=min(*pos,val);}

void Add(ll * pos,ll val){*pos=mod(*pos+val);}

const long double EPS=1E-8;

////////////////////////////////////////





struct tower{

    ll w,s,v;

};

bool comp(tower t1,tower t2){

    if(t1.w+t1.s<t2.w+t2.s)return true;

    else return false;

}



int main(){

    

    ll N=20001;

    ll n;cin>>n;

    tower t[n];

    rep(i,0,n-1){

        cin>>t[i].w>>t[i].s>>t[i].v;

    }

    sort(t,t+n,comp);

    ll dp[n+1][N];

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

    rep(i,0,n-1){

        rep(j,0,N-1){

            dp[i+1][j]=dp[i][j];

            if(0<=j-t[i].w&&j-t[i].w<=t[i].s)Max(&dp[i+1][j],dp[i][j-t[i].w]+t[i].v);

        }

    }

    /*rep(i,0,n){

        rep(j,0,20){

            cout<<dp[i][j]<<" ";

        }cout<<endl;

    }*/

    ll ans=0;rep(i,0,N-1)Max(&ans,dp[n][i]);

    cout<<ans<<endl;

    return 0;

}




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

#include <iostream>



int c[301000];

int a[301000], st[301000], top, n;



void add(int x) {for(int i = x; i <= n; i += i & -i) c[i]++;}

int query(int x) {int ans = 0;for(int i = x; i; i -= i & -i) ans += c[i]; return ans;}



bool check1()

{

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

	{

		if((a[i] - i) & 1) return false;

	}

	return true;

}



bool check2()

{

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

	{

		if(a[i] != i && a[i + 1] != i + 1 && a[i + 2] != i + 2) return false;

	}

	return true;

}



bool check3()

{

	long long sum = 0;

	for(int i = n; i >= 1; i--)

	{

		sum += query(a[i]);

		add(a[i]);

	}

	if(sum % 3 != 0) return false;

	return true;

}



bool check4()

{

	top = 0;

	st[++top] = a[1];

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

	{

		if(st[top] > a[i]) st[++top] = a[i];

		else

		{

			int l = 1, r = top + 1;

			while(l < r)

			{

				int mid = l + r >> 1;

				if(st[mid] < a[i]) r = mid;

				else l = mid + 1;

			}

			st[r] = a[i];

		}

	}

	if(top > 2) return false;

	top = 0;

	st[++top] = a[2];

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

	{

		if(st[top] > a[i]) st[++top] = a[i];

		else

		{

			int l = 1, r = top + 1;

			while(l < r)

			{

				int mid = l + r >> 1;

				if(st[mid] < a[i]) r = mid;

				else l = mid + 1;

			}

			st[r] = a[i];

		}

	}

	if(top > 2) return false;

	return true;

}



int main()

{

	scanf("%d", &n);

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

	if(check1() && check2() && check3() && check4()) puts("Yes");

	else puts("No");

	return 0;

}

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

#include<cstring>

#include<algorithm>

#define MN 300005

using namespace std;

inline int in(){

    int x=0;bool f=0;char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

int a[MN],q[MN],tp,hd,tl,n;

int main()

{

	n=in();hd=tp=1;

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

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

		tp=min(tp,i); 

		if((a[i]-tp)&1){if(a[i]!=i){printf("No");return 0;}}

		else if (hd>tl||q[tl]<a[i]) q[++tl]=a[i];

		else if (a[i]==tp) tp+=2;

		else {printf("No");return 0;}

		while (hd<=tl&&q[hd]==tp) tp+=2,++hd;

	}printf("Yes");return 0;

}

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

#define fr(i,x,y) for(int i=x;i<=y;++i)

#define rf(i,x,y) for(int i=x;i>=y;--i)

#define LL long long

using namespace std;

const int N=3e5+10;

int a[N],b[N];



void fail(){

	printf("No\n");

	exit(0);

}



bool check(int l,int r){

	int L=0,R=0;

	fr(i,l,r){

		if(b[i]<l||b[i]>r) return false;

		if(b[i]<i)

			if(L>b[i]) return false;

			 else L=b[i];

		else if(b[i]>i)

			if(R>b[i]) return false;

			 else R=b[i];

	}

	return true;

}



int main(){

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

	fr(i,1,n) scanf("%d",&b[i]),a[i]=(b[i]==i);

	fr(i,2,n-1) if(!a[i-1]&&!a[i]&&!a[i+1]) fail();

	fr(i,1,n){

		if(!a[i]){

			int l=i,r=i,nw=0;

			while((a[r+1]^nw)&&r+1<=n) r++,nw^=1;

			//printf("%d %d\n",l,r);

			if(!check(l,r)) fail();

			i=r;

		}

	}

	printf("Yes\n");

	return 0;

}

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

using namespace std;

int n,a,b,c,l1,l2;

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a);

		if((a^i)&1){printf("No\n");return 0;}

		if(a>i||(l1&&!((l1^a)&1))){if(!l1)l1=a;else if(a<l2){printf("No\n");return 0;}else if(a<l1)l2=a;else l1=a;}

		if(i&1){if(b<a)b=a;}else if(c<a)c=a;

		if(b>i&&c>i){printf("No\n");return 0;}

		if(b<=i&&c<=i)l1=l2=0;

	}

	printf("Yes\n");

}//

// Fastest known solution for this problem: