stablegradients/pie-gem5-bysrc huggingface dataset:
// 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;



ll N;

string S;

ll T[100005];

bool check(ll k)

{

    REP(n, 2)

    {

        memset(T, 0, sizeof(T));

        ll m = 0;

        string s = "";

        REP(i, N)

        {

            m += T[i];

            ll t = (S[i] - '0' + m) % 2;



            if (i + k <= N && t != n)

            {

                m++;

                T[i + k] = -1;

                t = (t + 1) % 2;

            }

            s.push_back(t + '0');

        }



        ll max = 0;

        ll sum = 0;

        REP(i, N)

        {

            sum++;

            if (i == N - 1 || s[i] != s[i + 1])

            {

                max = std::max(max, sum);

                sum = 0;

            }

        }



        if (max >= k)

            return true;

    }

    return false;

}



int main()

{

    cin >> S;

    N = S.length();

    ll ok = 1, ng = N + 1;

    while (abs(ok - ng) > 1)

    {

        ll mid = (ok + ng) / 2;

        if (check(mid))

            ok = mid;

        else

            ng = mid;

    }

    cout << ok << 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);

    string S;

    cin >> S;

    ll N = S.length();

    bool e = true;

    REP(i, N - 1) {

        if (S[i] != S[i + 1])

            e = false;

    }

    ll ans = INF;

    REP(i, N - 1) {

        if (S[i] == S[i + 1])

            continue;

        ans = std::min(ans, std::max(i + 1, N - 1 - i));

    }

    if (e)

        ans = N;

    cout << ans << endl;

    return 0;

}

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

#include<algorithm>

#define maxn 100005

#define inf 0x3f3f3f3f

using namespace std;

typedef long int ll;

int main()

{

    string s;

    cin >> s;

    int ls = s.size(), ans = ls;

    for (int i = 1; i < ls; ++i) if (s[i - 1] != s[i]) ans = min(ans, max(i, ls - i));

    cout << ans << endl;

    return 0;

}


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

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int inf=1<<29;

const int maxn=1e5+100;

char s[maxn];



int main()

{

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

    while (scanf("%s",s+1)!=EOF)

    {

        int len=strlen(s+1);

        int ans=inf;

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

        {

            if (s[i]!=s[i+1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

}


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

using namespace std;



const int maxn = 1e5+100;

char s[maxn];



int main()

{

    while (scanf("%s",s)!=EOF)

    {

        int l = strlen(s);

        int k = 0, ans = l;

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

            if (abs(s[i-1] - s[i]) == 1)

            {

                k = max(i,l-i);

                ans = min(ans,k);

            }

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

    }

    return 0;

}


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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

}


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

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<iostream>

#include<algorithm>

#include<map>

#include<set>

#include<stack>

#include<time.h>

#include<queue>

#include<bitset>

#include<vector>

using namespace std;

const int maxn=1e5+100;

char a[maxn];

int main()

{

    scanf("%s",a);

    int len=strlen(a),ans=len;

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

        if(a[i-1]!=a[i])

            ans=min(ans,max(i,len-i));

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

    return 0;

}

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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

}


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

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <cstdlib>

#include <vector>

#include <map>

#include <cstring>

using namespace std;

const int maxn=2e6+100;

const long long mod=1e12+7;

long long ans,l1,l2,len1,len2,ty,z,n,m,k,t,x,y;

set<long long>s;char c[maxn];bool le;char tt;

long long h[maxn];

int main()

{

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

  //  freopen("x.out","w",stdout);

  scanf("%s",c);

  k=strlen(c);

  ans=k;

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

  {

      if(c[i]!=c[i-1])

      ans=min(ans,max(i,k-i));

  }

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

  //  fclose(stdin);

   // fclose(stdout);

    return 0;

}


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

#include<string.h>

int max(int x,int y)

{

    return x>y ? x:y;

}

int min(int x,int y)

{

    return x<y ? x:y;

}

int main()

{

    char ch[100010];

    while(scanf("%s",ch)!=EOF)

    {

        int len=strlen(ch);

        int ans=len;

        for(int i=1;i<=len-1;i++)

        {

            if(ch[i]!=ch[i-1])

                ans=min(ans,max(i,len-i));

        }

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

    }

    return 0;

}


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

using namespace std;

typedef pair<int,int> par;

int read(){

	int x=0,f=1; char ch=getchar();

	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}

	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}

	return x*f;

}

int fa[1000005];

map <par,int>m,a;

multiset<int>s[100005];

queue<par>q;

par makep(int x,int y){

	if (x>y) return par(y,x);

	else return par(x,y);

}

int find(int x){

	return fa[x]==x?x:find(fa[x]);

}

int main(){

	int n=read();

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

		int u=read(),v=read();

		par w=makep(u,v);

		m[w]++; 

		if (m[w]>1&&a[w]==0){

			a[w]=1; q.push(w);

		}

		if (i<=n) fa[i]=i; 

		s[v].insert(u); s[u].insert(v);

	}

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

		int x,y;

		while (1){

			if (q.empty()){printf("NO\n"); return 0;}

			par w=q.front(); q.pop();

			x=find(w.first); y=find(w.second);

			if (x!=y) break;

		}

		if (s[x].size()>s[y].size()) swap(x,y);

		fa[x]=y;

		for (set<int>::iterator i=s[x].begin();i!=s[x].end();i++){

			int v=find(*i);

			if (v==y) continue;

			par z=makep(v,y);

			m[z]++; 

			if (m[z]>1&&a[z]==0){

				q.push(z); a[z]=1;

			}

			s[v].erase(s[v].find(x)); s[y].insert(v); s[v].insert(y);

		}

		s[y].erase(x);

		s[x].clear();

	}

	printf("YES\n");

	return 0;

}

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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

		for(rg int j=head[x];j;j=a[j].nxt){

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

}

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

#include<cstring>

#include<cstdlib>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=100005;



int N;

set<int> E[MAXN];

map<int,int> cnt[MAXN];

queue<pair<int,int>> Q;



int fa[MAXN];

int Root(int x)

{return fa[x]==0?x:(fa[x]=Root(fa[x]));}



void Link(int u,int v)

{

    E[u].insert(v);

    E[v].insert(u);

    if(u>v)

        swap(u,v);

    cnt[u][v]++;

    if(cnt[u][v]>2)

    {

        puts("NO");

        exit(0);

    }

    if(cnt[u][v]==2)

        Q.emplace(u,v);

}

void Cut(int u,int v)

{

    E[u].erase(v);

    if(u>v)

        swap(u,v);

    cnt[u].erase(v);

}



int main()

{

    scanf("%d",&N);

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

    {

        int u,v;

        scanf("%d%d",&u,&v);

        Link(u,v);

    }

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

    {

        int u,v;

        do

        {

            if(Q.empty())

            {

                puts("NO");

                return 0;

            }

            u=Root(Q.front().first),v=Root(Q.front().second);

            Q.pop();

        }while(u==v);

        if(E[u].size()<E[v].size())

            swap(u,v);

        fa[v]=u;

        Cut(u,v);

        for(auto e:E[v])

        {

            int t=Root(e);

            if(t==u)

                continue;

            Link(t,u);

            Cut(t,v);

        }

    }

    puts("YES");



    return 0;

}


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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

		for(rg int j=head[x];j;j=a[j].nxt){

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

}

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

#include<map>

#include<set>

#include<queue>

#include<algorithm>

#define MAXN 100006

using namespace std;

int n,fa[MAXN],u,v,top,p[MAXN];

map<int,int> h[MAXN];

set<int> e[MAXN];

queue<pair<int,int> > q;

void link(int u,int v)

{

	e[u].insert(v);

	e[v].insert(u);

	if(u>v) swap(u,v);

	++h[u][v];

	if(h[u][v]==2) q.push(make_pair(u,v));

	if(h[u][v]>2)

	{

		printf("NO");

		exit(0);

	}

}

void cut(int u,int v)

{

	e[u].erase(v);

	if(u>v) swap(u,v);

	h[u].erase(v);

}

int find(int x)

{

	if(x!=fa[x]) fa[x]=find(fa[x]);

	return fa[x];

}

int main()

{

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

	//freopen("bluered.out","w",stdout);

	scanf("%d",&n);

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

		fa[i]=i;

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

	{

		scanf("%d%d",&u,&v);

		link(u,v);

	}

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

	{

		scanf("%d%d",&u,&v);

		link(u,v);

	}

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

	{

		do

		{

			if(q.empty())

			{

				printf("NO");

				return 0;

			}

			u=q.front().first;

			v=q.front().second;

			u=find(u);

			v=find(v);

			q.pop();

		}while(u==v);

		if(e[u].size()>e[v].size()) swap(u,v);

		fa[u]=v;

		cut(v,u);

		top=0;		

		for(set<int>::iterator it=e[u].begin();it!=e[u].end();it++)

			p[++top]=*it;

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

		{

			int x=p[i];

			x=find(x);

			if(x==v) continue;

			link(x,v);

			cut(x,u);

		}

		e[u].clear();

	}

	printf("YES");

}

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

using namespace std;

typedef long long ll;

#define rg register



template <typename _Tp> inline _Tp read(_Tp&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;

}



const int N=101000,ae=20;

struct Edge{int v,nxt;}a[N*ae*2];

int qx[N*ae],qy[N*ae],dad[N];

int head[N],_,sz[N];

int n,he=1,ta=0;



inline int find(int x){return dad[x]?dad[x]=find(dad[x]):x;}



inline void ins(int u,int v){++sz[u],a[++_].v=v,a[_].nxt=head[u],head[u]=_;}



map <ll,int> cnt;



#define h(x,y) (x+1ll*n*y)

inline void add(int x,int y){

	if(x>y)swap(x,y);

	ins(x,y),ins(y,x);

	if((++cnt[h(x,y)])==2)

		++ta,qx[ta]=x,qy[ta]=y;

}



int main(){

	read(n);int x,y,p;

	for(rg int i=n-2+n;i;--i)read(x),read(y),add(x,y);

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

		do	x=qx[he],y=qy[he],++he;

		while(find(x)==find(y)&&he<=ta);

		x=find(x),y=find(y);

		if(x==y){puts("NO");return 0;}

		if(sz[x]>sz[y])swap(x,y);

		--sz[y];cnt.erase(x<y?h(x,y):h(y,x));

		for(rg int j=head[x];j;j=a[j].nxt){

			p=find(a[j].v);

			if(p^y)if(p!=find(x))add(p,y);

		}

		dad[x]=y;

	}puts("YES");

}

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

using namespace std;

#define pii pair<int,int>

#define mk make_pair

pii q[200001];

int h,t;

int n;

set<int> s[200001];

map<pii,int> mp;

int fa[200001];

int findfa(int x){

	return x==fa[x]?fa[x]:fa[x]=findfa(fa[x]);

}

int main(){

	scanf("%d",&n);

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

		int u,v;

		scanf("%d%d",&u,&v);

		mp[mk(u,v)]++;mp[mk(v,u)]++;

		s[u].insert(v),s[v].insert(u);

		if(mp[mk(u,v)]==2)q[++t]=mk(u,v);

	}

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

	set<int>::iterator id;

	while(h<t){

		int u=q[++h].first,v=q[h].second;

		u=findfa(u),v=findfa(v);

		s[u].erase(v),s[v].erase(u);

		if(s[u].size()<s[v].size())swap(u,v);

		for(id=s[v].begin();id!=s[v].end();++id){

			int to=(*id);

			mp[mk(v,to)]=mp[mk(to,v)]=0;

			s[to].erase(v);s[to].insert(u);

			mp[mk(u,to)]++,mp[mk(to,u)]++;

			if(mp[mk(u,to)]==2){

				q[++t]=mk(u,to);

			}

			s[u].insert(to);

		}

		fa[v]=u;

		s[v].clear();

	}

	int ans=0;

	for(int i=1;i<=n;++i)ans+=fa[i]==i;

	if(ans==1)puts("YES");

	else puts("NO");

}

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

using namespace std;

namespace IO {

  const int IN_LEN = 1 << 18 | 1;

  static char buf[IN_LEN] , *s , *t;

  inline int Getchar( void ) { return s == t && ( t = ( s = buf ) + fread( buf , 1 , IN_LEN , stdin ) ) , s == t ? -1 : *s++; }

  template <class T> inline void read( T & x ) {

    static int c , f;

    for( c = Getchar() , f = 0 ; c < '0' || c > '9' ; c = Getchar() ) if( c == '-' ) f = 1;

    for( x = 0 ; c <= '9' && c >= '0' ; c = Getchar() ) x = x * 10 + c - 48;

    x = f ? -x : x;

  }

}using IO::read;

const int MAXN = 1e5 + 1;

typedef pair<int,int> pii;

set<int> E[MAXN];

map<pii,int> rem;

int n , f[MAXN];

queue<pii> Q;

pii get( int x , int y ) { if( x > y ) swap( x , y ); return make_pair( x , y ); }

int find( const int & x ) { return x == f[x] ? x : f[x] = find( f[x] ); }

int main( void ) {

  read( n );

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

    read( u ) , read( v );

    ++rem[get( u , v )];

    E[u].insert( v ) , E[v].insert( u );

  }

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

    read( u ) , read( v );

    ++rem[get( u , v )];

    E[u].insert( v ) , E[v].insert( u );

    if( rem[get( u , v )] == 2 ) Q.push( pii( u , v ) );

  }

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

  while( !Q.empty() ) {

    int u = Q.front().first , v = Q.front().second;Q.pop();

    if( ( u = find( u ) ) == ( v = find( v ) ) ) continue;

    if( E[u].size() < E[v].size() ) swap( u , v );

    for( int k : E[v] ) {

      rem[get( u , v )] = 0;

      E[u].insert( k ) , E[k].insert( u );

      ++rem[get( u , k )];

      if( rem[get( u , k )] == 2 ) Q.push( pii( u , k ) );

    }

    f[v] = u;

    E[v].clear();

  }

  int cnt = 0;

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

    find( i );

    cnt += ( i == f[i] );

  }

  puts( cnt == 1 ? "YES" : "NO" );

  return 0;

}

 

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

using namespace std;

#define N 100005

set<int>s[N];

map<int,int>mat[N];

queue<pair<int,int> >q;

int n,x,y,ans,f[N];

int find(int k){

	if (k==f[k])return k;

	return f[k]=find(f[k]);

}

void add(int x,int y){

	s[x].insert(y);

	s[y].insert(x);

	if (x>y)swap(x,y);

	if (++mat[x][y]==2){

		q.push(make_pair(x,y));

		mat[x][y]=0;

	}

}

void merge(int x,int y){

	if (s[x].size()>s[y].size())swap(x,y);

	f[x]=y;

	for(set<int>::iterator it=s[x].begin();it!=s[x].end();it++){

		int z=find(*it);

		if (y==z)continue;

		add(y,z);

		s[z].erase(x);

	}

	s[x].clear();

}

int main(){

	scanf("%d",&n);

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

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

		scanf("%d%d",&x,&y);

		add(x,y);

	}

	while (!q.empty()){

		ans++;

		merge(find(q.front().first),find(q.front().second));

		q.pop();

	}

	if (ans==n-1)printf("YES");

	else printf("NO");

}

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

#include<cstdio>

#include<map>

#include<set>

#include<queue>

using namespace std;

const int N=100001;

int n;

map<pair<int,int>,int> book;

set<int> e[N];

queue<pair<int,int> >q;

int f[N];

int find(int v)

{

	if(v==f[v]) return v;

	f[v]=find(f[v]);

	return f[v];

}

pair<int,int> make(int x,int y)

{

    if(x>y) swap(x,y);

    return make_pair(x,y);

}

int main()

{

    scanf("%d",&n);

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

    	f[i]=i;

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

	{

        int x,y;

        scanf("%d%d",&x,&y);

        e[x].insert(y);

		e[y].insert(x);

        pair<int,int> t=make(x,y);

        book[t]++;

        if(book[t]==2) q.push(t);

        if(book[t]>2)

        {

        	printf("NO");

        	return 0;

		}

    }

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

	{

        if(q.empty())

        {

        	printf("NO");

        	return 0;

		}

        int x=0,y=0;

        while(x==y)

        {

        	x=find(q.front().first),y=find(q.front().second);

        	q.pop();

		}

        if(e[x].size()>e[y].size()) swap(x,y);

        f[x]=y;

        for(set<int>::iterator it=e[x].begin();it!=e[x].end();it++)

		{

            int v=find(*it);

            e[v].erase(e[v].find(x));

            if(v==y) continue;

            e[v].insert(y),e[y].insert(v);

            pair<int,int> t=make(v,y);

            book[t]++;

            if(book[t]==2) q.push(t);

        }

        e[x].clear();

    }

    printf("YES");

    return 0;

}

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

using namespace std;

int n;

int a[100005];

int x[100005];

int y[100005];



int main(){

  scanf("%d",&n);

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

    cin>>a[i];

  }



  memset(x,-1,sizeof(x));

  memset(y,-1,sizeof(y));

  

  int ans=0;

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

    int p=i,c=0;

    while(x[p]==-1){

      x[p]=c++;

      y[p]=i;

      p=(p+a[p])%n;

    }

    if(y[p]==i)ans+=(c-x[p]);

  }



  cout<<ans<<endl;

  return 0;

}

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

int n,i,p,c,ans=0;

int a[100000];

int x[100000];

int y[100000];



int main(){

  scanf("%d",&n);

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

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

    x[i]=-1;

    y[i]=-1;

  }

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

    p=i;

    c=0;

    while(x[p]==-1){

      x[p]=c++;

      y[p]=i;

      p=(p+a[p])%n;

    }

    if(y[p]==i)ans+=(c-x[p]);

  }

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

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<unordered_set>

#include<complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 2000 + 47;



int A[MAX];

int B[MAX];

int B1[MAX];



int main()

{

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

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	int n; 

	LL x;

	cin >> n >> x;

	FOR(i, 0, n)

	{

		cin >> A[i];

		B[i] = A[i];

	}



	LL ans = LINF;

	FOR(k, 0, n)

	{

		LL summ = 0;

		FOR(i, 0, n) summ += B[i];

		ans = min(ans, k * x + summ);

		FOR(i, 0, n)

		{

			B1[i] = min(A[i], B[(i - 1 + n) % n]);

		}



		FOR(i, 0, n)

		{

			B[i] = B1[i];

		}

	}



	cout << ans << endl;

}


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



typedef long long LL;



const int MAXN = 4005;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}



int q[MAXN];

int a[MAXN];

int N, x;



LL calc( const int l )

{

	LL ret = 1ll * l * x;

	int h = 1, t = 0, r = 1;

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

	{

		while( h <= t && q[h] < i ) h ++;

		for( ; r <= i + l ; r ++ )

		{

			while( h <= t && a[q[t]] >= a[r] )

				t --;

			q[++ t] = r;

		}

		ret += a[q[h]];

	}

	return ret;

}



int main()

{

	read( N ), read( x );

	for( int i = 1 ; i <= N ; i ++ ) read( a[i] ), a[i + N] = a[i];

	LL ans = 1e18;

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

		ans = MIN( ans, calc( i ) );

	write( ans ), putchar( '\n' );

	return 0;

}

// Fastest known solution for this problem: