#727809 (C++17) No.1470 Mex Sum

提出ソース
結果

問題	No.1470 Mex Sum
ユーザー	tonakai
提出日時	2022-01-02 17:35:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	16 ms / 2,000 ms
コード長	42,920 bytes
コンパイル時間	5,257 ms
コンパイル使用メモリ	298,444 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-20 02:28:31
合計ジャッジ時間	7,882 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	15 ms 5,376 KB
testcase_13	AC	15 ms 5,376 KB
testcase_14	AC	15 ms 5,376 KB
testcase_15	AC	15 ms 5,376 KB
testcase_16	AC	15 ms 5,376 KB
testcase_17	AC	15 ms 5,376 KB
testcase_18	AC	15 ms 5,376 KB
testcase_19	AC	14 ms 5,376 KB
testcase_20	AC	15 ms 5,376 KB
testcase_21	AC	15 ms 5,376 KB
testcase_22	AC	15 ms 5,376 KB
testcase_23	AC	15 ms 5,376 KB
testcase_24	AC	15 ms 5,376 KB
testcase_25	AC	15 ms 5,376 KB
testcase_26	AC	15 ms 5,376 KB
testcase_27	AC	15 ms 5,376 KB
testcase_28	AC	16 ms 5,376 KB
testcase_29	AC	15 ms 5,376 KB
testcase_30	AC	16 ms 5,376 KB
testcase_31	AC	15 ms 5,376 KB
testcase_32	AC	15 ms 5,376 KB
testcase_33	AC	16 ms 5,376 KB
testcase_34	AC	15 ms 5,376 KB
testcase_35	AC	15 ms 5,376 KB
testcase_36	AC	15 ms 5,376 KB
testcase_37	AC	11 ms 5,376 KB
testcase_38	AC	12 ms 5,376 KB
testcase_39	AC	12 ms 5,376 KB
testcase_40	AC	13 ms 5,376 KB
testcase_41	AC	12 ms 5,376 KB
testcase_42	AC	13 ms 5,376 KB
testcase_43	AC	13 ms 5,376 KB
testcase_44	AC	13 ms 5,376 KB
testcase_45	AC	13 ms 5,376 KB
testcase_46	AC	13 ms 5,376 KB
testcase_47	AC	14 ms 5,376 KB
testcase_48	AC	13 ms 5,376 KB
testcase_49	AC	13 ms 5,376 KB
testcase_50	AC	12 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ll> pdl;
typedef pair<ll,ld> pld;
typedef pair<ld,ld> pdd;
#ifdef _MSC_VER
#endif
namespace atcoder{namespace internal{int ceil_pow2(int n){int x=0;while((1U<<x)<(ui)(n))x++;return x;}constexpr int bsf_constexpr(ui n){int x=0;while(!(n&(1<<x)))x++;return x;}int bsf(ui n){
#ifdef _MSC_VER
unsigned long index;_BitScanForward(&index,n);return index;
#else
return __builtin_ctz(n);
#endif
}}}
#ifdef _MSC_VER
#endif
#ifdef _MSC_VER
#endif
namespace atcoder{namespace internal{constexpr ll safe_mod(ll x,ll m){x%=m;if(x<0)x+=m;return x;}struct barrett{ui _m;ull im;explicit barrett(ui m):_m(m),im((ull)(-1)/m+1){}ui umod()const{return _m;}ui mul(ui a,ui b)const{ull z=a;z*=b;
#ifdef _MSC_VER
ull x;_umul128(z,im,&x);
#else
ull x=(ull)(((unsigned __int128)(z)*im)>>64);
#endif
ui v=(ui)(z-x*_m);if(_m<=v)v+=_m;return v;}};constexpr ll pow_mod_constexpr(ll x,ll n,int m){if(m==1)return 0;ui _m=(ui)(m);ull r=1,y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;ll d=n-1;while(d%2==0)d/=2;constexpr ll bases[3]={2,7,61};for(ll a:bases){ll t=d,y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}
template<int n>constexpr bool is_prime=is_prime_constexpr(n);constexpr pll inv_gcd(ll a,ll b){a=safe_mod(a, b);if(a==0)return{b,0};ll s=b,t=a,m0=0,m1=1;while(t){ll u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr int primitive_root_constexpr(int m){if(m==2)return 1;if(m==167772161)return 3;if(m==469762049)return 3;if(m==754974721)return 11;if(m==998244353)return 3;int divs[20]={};divs[0]=2;int cnt=1,x=(m-1)/2;while(x%2==0){x/=2;}for(int i=3;(ll)(i)*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}for(int g=2;;g++){bool ok=true;for(int i=0;i<cnt;i++){if(pow_mod_constexpr(g,(m-1)/divs[i],m)==1){ok=false;break;}}if(ok)return g;}}
template<int m>constexpr int primitive_root=primitive_root_constexpr(m);ull floor_sum_unsigned(ull n,ull m,ull a,ull b){ull ans=0;while(1){if(a>=m){ans+=n*(n-1)/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ull y_max=a*n+b;if(y_max<m)break;n=(ull)(y_max/m);b=(ull)(y_max%m);swap(m,a);}return ans;}}}namespace atcoder{namespace internal{
#ifndef _MSC_VER
template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T, __int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;
template<class T>using make_unsigned_int128=typename std::conditional<is_same<T,__int128_t>::value,__uint128_t,unsigned __int128>;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template <class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using to_unsigned=typename conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename conditional<is_signed<T>::value,make_unsigned<T>,common_type<T>>::type>::type;
#else
template<class T>using is_integral=typename is_integral<T>;template<class T>using is_signed_int=typename conditional<is_integral<T>::value&&is_signed<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<is_integral<T>::value&&is_unsigned<T>::value,true_type,false_type>::type;template<class T>using to_unsigned=typename conditional<is_signed_int<T>::value,make_unsigned<T>,common_type<T>>::type;
#endif
template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;template<class T>using to_unsigned_t=typename to_unsigned<T>::type;}}namespace atcoder{namespace internal{struct modint_base {};struct static_modint_base:modint_base{};template<class T>using is_modint=is_base_of<modint_base,T>;template<class T>using is_modint_t=enable_if_t<is_modint<T>::value>;}
template<int m,std::enable_if_t<(1<=m)>* =nullptr>struct static_modint:internal::static_modint_base{using mint=static_modint;public:static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){ll x=(ll)(v%(ll)(umod()));if(x<0)x+=umod();_v=(ui)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(ui)(v%umod());}ui val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint& rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint& rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}mint&operator*=(const mint& rhs){ull z=_v;z*=rhs._v;_v=(ui)(z%umod());return*this;}
mint&operator/=(const mint& rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(ll n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}private:ui _v;static constexpr ui umod(){return m;}static constexpr bool prime=internal::is_prime<m>;};
template<int id>struct dynamic_modint:internal::modint_base{using mint=dynamic_modint;public:static int mod(){return(int)(bt.umod());}static void set_mod(int m){assert(1<=m);bt=internal::barrett(m);}static mint raw(int v){mint x;x._v=v;return x;}dynamic_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>dynamic_modint(T v){ll x=(ll)(v%(ll)(mod()));if(x<0)x+=mod();_v=(ui)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>dynamic_modint(T v){_v=(ui)(v%mod());}ui val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v+=mod()-rhs._v;if(_v>=umod())_v-=umod();return*this;}
mint&operator*=(const mint&rhs){_v=bt.mul(_v,rhs._v);return*this;}mint&operator/=(const mint& rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(ll n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{auto eg=internal::inv_gcd(_v,mod());assert(eg.first==1);return eg.second;}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}private:ui _v;static internal::barrett bt;static ui umod(){return bt.umod();}};
template<int id>internal::barrett dynamic_modint<id>::bt(998244353);using modint998244353=static_modint<998244353>;using modint1000000007=static_modint<1000000007>;using modint=dynamic_modint<-1>;namespace internal{template<class T>using is_static_modint=is_base_of<internal::static_modint_base,T>;template<class T>using is_static_modint_t=enable_if_t<is_static_modint<T>::value>;template<class>struct is_dynamic_modint:public false_type{};template<int id>struct is_dynamic_modint<dynamic_modint<id>>:public true_type{};template<class T>using is_dynamic_modint_t=enable_if_t<is_dynamic_modint<T>::value>;}}
namespace atcoder{namespace internal{template<class mint,int g=internal::primitive_root<mint::mod()>,internal::is_static_modint_t<mint>* =nullptr>struct fft_info{static constexpr int rank2=bsf_constexpr(mint::mod()-1);array<mint,rank2+1>root;array<mint,rank2+1>iroot;array<mint,max(0,rank2-2+1)>rate2;array<mint,max(0,rank2-2+1)>irate2;array<mint,max(0,rank2-3+1)>rate3;array<mint,max(0,rank2-3+1)>irate3;
fft_info(){root[rank2]=mint(g).pow((mint::mod()-1)>>rank2);iroot[rank2]=root[rank2].inv();for(int i=rank2-1;i>=0;i--){root[i]=root[i+1]*root[i+1];iroot[i]=iroot[i+1]*iroot[i+1];}{mint prod=1,iprod=1;for(int i=0;i<=rank2-2;i++){rate2[i]=root[i+2]*prod;irate2[i]=iroot[i+2]*iprod;prod*=iroot[i+2];iprod*=root[i+2];}}{mint prod=1,iprod=1;for(int i=0;i<=rank2-3;i++){rate3[i]=root[i+3]*prod;irate3[i]=iroot[i+3]*iprod;prod*=iroot[i+3];iprod*=root[i+3];}}}};
template<class mint,internal::is_static_modint_t<mint>* =nullptr>void butterfly(std::vector<mint>&a){int n=int(a.size()),h=internal::ceil_pow2(n);static const fft_info<mint>info;int len=0;while(len<h){if(h-len==1){int p=1<<(h-len-1);mint rot=1;for(int s=0;s<(1<<len);s++){int offset=s<<(h-len);for(int i=0;i<p;i++){auto l=a[i+offset];auto r=a[i+offset+p]*rot;a[i+offset]=l+r;a[i+offset+p]=l-r;}if(s+1!=(1<<len))rot*=info.rate2[bsf(~(ui)(s))];}len++;}else{int p=1<<(h-len-2);mint rot=1,imag=info.root[2];for(int s=0;s<(1<<len);s++){mint rot2=rot*rot;mint rot3=rot2*rot;int offset=s<<(h-len);
for(int i=0;i<p;i++){auto mod2=1ULL*mint::mod()*mint::mod();auto a0=1ULL*a[i+offset].val();auto a1=1ULL*a[i+offset+p].val()*rot.val();auto a2=1ULL*a[i+offset+2*p].val()*rot2.val();auto a3=1ULL*a[i+offset+3*p].val()*rot3.val();auto a1na3imag=1ULL*mint(a1+mod2-a3).val()*imag.val();auto na2=mod2-a2;a[i+offset]=a0+a2+a1+a3;a[i+offset+1*p]=a0+a2+(2*mod2-(a1+a3));a[i+offset+2*p]=a0+na2+a1na3imag;a[i+offset+3*p]=a0+na2+(mod2-a1na3imag);}if(s+1!=(1<<len))rot*=info.rate3[bsf(~(ui)(s))];}len+=2;}}}
template<class mint,internal::is_static_modint_t<mint>* =nullptr>void butterfly_inv(std::vector<mint>&a){int n=int(a.size()),h=internal::ceil_pow2(n);static const fft_info<mint> info;int len=h;while(len){if(len==1){int p=1<<(h-len);mint irot=1;for(int s=0;s<(1<<(len-1));s++){int offset=s<<(h-len+1);for(int i=0;i<p;i++){auto l=a[i+offset];auto r=a[i+offset+p];a[i+offset]=l+r;a[i+offset+p]=(ull)(mint::mod()+l.val()-r.val())*irot.val();}if(s+1!=(1<<(len-1)))irot*=info.irate2[bsf(~(ui)(s))];}len--;}
else{int p=1<<(h-len);mint irot=1,iimag=info.iroot[2];for(int s=0;s<(1<<(len-2));s++){mint irot2=irot*irot;mint irot3=irot2*irot;int offset=s<<(h-len+2);for(int i=0;i<p;i++){auto a0=1ULL*a[i+offset+0*p].val();auto a1=1ULL*a[i+offset+1*p].val();auto a2=1ULL*a[i+offset+2*p].val();auto a3=1ULL*a[i+offset+3*p].val();auto a2na3iimag=1ULL*mint((mint::mod()+a2-a3)*iimag.val()).val();a[i+offset]=a0+a1+a2+a3;a[i+offset+1*p]=(a0+(mint::mod()-a1)+a2na3iimag)*irot.val();a[i+offset+2*p]=(a0+a1+(mint::mod()-a2)+(mint::mod()-a3))*irot2.val();a[i+offset+3*p]=(a0+(mint::mod()-a1)+(mint::mod()-a2na3iimag))*irot3.val();}if(s+1!=(1<<(len-2)))irot*=info.irate3[bsf(~(ui)(s))];}len-=2;}}}
template<class mint,internal::is_static_modint_t<mint>* =nullptr>vector<mint>convolution_naive(const vector<mint>&a,const vector<mint>&b){int n=int(a.size()),m=int(b.size());vector<mint>ans(n+m-1);if(n<m){for(int j=0;j<m;j++){for(int i=0;i<n;i++){ans[i+j]+=a[i]*b[j];}}}else{for(int i=0;i<n;i++){for(int j=0;j<m;j++){ans[i+j]+=a[i]*b[j];}}}return ans;}template<class mint,internal::is_static_modint_t<mint>* =nullptr>vector<mint>convolution_fft(vector<mint> a,vector<mint> b){int n=int(a.size()),m=int(b.size());int z=1<<internal::ceil_pow2(n+m-1);a.resize(z);
internal::butterfly(a);b.resize(z);internal::butterfly(b);for(int i=0;i<z;i++){a[i]*=b[i];}internal::butterfly_inv(a);a.resize(n+m-1);mint iz=mint(z).inv();for(int i=0;i<n+m-1;i++)a[i]*=iz;return a;}}template<class mint,internal::is_static_modint_t<mint>* =nullptr>vector<mint>convolution(vector<mint>&&a,vector<mint>&&b){int n=int(a.size()),m=int(b.size());if(!n||!m)return{};if(min(n,m)<=60)return convolution_naive(a,b);return internal::convolution_fft(a,b);}
template<class mint,internal::is_static_modint_t<mint>* =nullptr>vector<mint>convolution(const vector<mint>&a,const vector<mint>&b){int n=int(a.size()),m=int(b.size());if(!n||!m)return{};if(min(n,m)<=60)return convolution_naive(a,b);return internal::convolution_fft(a,b);}template<ui mod=998244353,class T,enable_if_t<internal::is_integral<T>::value>* =nullptr>vector<T>convolution(const vector<T>&a,const vector<T>&b){int n=int(a.size()),m=int(b.size());if(!n||!m)return{};
using mint=static_modint<mod>;vector<mint>a2(n),b2(m);for(int i=0;i<n;i++){a2[i]=mint(a[i]);}for(int i=0;i<m;i++){b2[i]=mint(b[i]);}auto c2=convolution(move(a2),move(b2));vector<T>c(n+m-1);for(int i=0;i<n+m-1;i++){c[i]=c2[i].val();}return c;}
vector<ll>convolution_ll(const vector<ll>&a,const vector<ll>&b){int n=int(a.size()),m=int(b.size());if(!n||!m)return{};static constexpr ull MOD1=754974721;static constexpr ull MOD2=167772161;static constexpr ull MOD3=469762049;static constexpr ull M2M3=MOD2*MOD3;static constexpr ull M1M3=MOD1*MOD3;static constexpr ull M1M2=MOD1*MOD2;static constexpr ull M1M2M3=MOD1*MOD2*MOD3;
static constexpr ull i1=internal::inv_gcd(MOD2*MOD3,MOD1).second;static constexpr ull i2=internal::inv_gcd(MOD1*MOD3,MOD2).second;static constexpr ull i3=internal::inv_gcd(MOD1*MOD2,MOD3).second;auto c1=convolution<MOD1>(a,b);auto c2=convolution<MOD2>(a,b);auto c3=convolution<MOD3>(a,b);vector<ll>c(n+m-1);for(int i=0;i<n+m-1;i++){ull x=0;x+=(c1[i]*i1)%MOD1*M2M3;x+=(c2[i]*i2)%MOD2*M1M3;x+=(c3[i]*i3)%MOD3*M1M2;ll diff=c1[i]-internal::safe_mod((ll)(x),(ll)(MOD1));if(diff<0)diff+=MOD1;static constexpr ull offset[5]={0,0,M1M2M3,2*M1M2M3,3*M1M2M3};x-=offset[diff%5];c[i]=x;}return c;}}
namespace atcoder{struct dsu{public:dsu():_n(0){}explicit dsu(int n):_n(n),parent_or_size(n,-1){}int merge(int a,int b){assert(0<=a&&a<_n);assert(0<=b&&b<_n);int x=leader(a),y=leader(b);if(x==y)return x;if(-parent_or_size[x]<-parent_or_size[y])swap(x,y);parent_or_size[x]+=parent_or_size[y];parent_or_size[y]=x;return x;}
bool same(int a,int b){assert(0<=a&&a<_n);assert(0<=b&&b<_n);return leader(a)==leader(b);}int leader(int a){assert(0<=a&&a<_n);if(parent_or_size[a]<0)return a;return parent_or_size[a]=leader(parent_or_size[a]);}int size(int a){assert(0<=a&&a<_n);return -parent_or_size[leader(a)];}vector<vector<int>>groups(){vector<int>leader_buf(_n),group_size(_n);for(int i=0;i<_n;i++){leader_buf[i]=leader(i);group_size[leader_buf[i]]++;}vector<vector<int>>result(_n);for(int i=0;i<_n;i++){result[i].reserve(group_size[i]);}
for(int i=0;i<_n;i++){result[leader_buf[i]].push_back(i);}result.erase(remove_if(result.begin(),result.end(),[&](const vector<int>&v){return v.empty();}),result.end());return result;}private:int _n;vector<int>parent_or_size;};}
namespace atcoder{template<class T>struct fenwick_tree{using U=internal::to_unsigned_t<T>;public:fenwick_tree():_n(0){}explicit fenwick_tree(int n):_n(n),data(n){}void add(int p,T x){assert(0<=p&&p<_n);p++;while(p<=_n){data[p-1]+=U(x);p+=p&-p;}}T sum(int l,int r){assert(0<=l&&l<=r&&r<=_n);return sum(r)-sum(l);}private:int _n;vector<U>data;U sum(int r){U s=0;while(r>0){s+=data[r-1];r-=r&-r;}return s;}};}
namespace atcoder{template<class S,S(*op)(S,S),S(*e)(),class F,S(*mapping)(F,S),F(*composition)(F,F),F(*id)()>struct lazy_segtree{public:lazy_segtree():lazy_segtree(0){}explicit lazy_segtree(int n):lazy_segtree(std::vector<S>(n,e())){}explicit lazy_segtree(const vector<S>&v):_n(int(v.size())){log=internal::ceil_pow2(_n);size=1<<log;d=vector<S>(2*size,e());lz=vector<F>(size,id());for(int i=0;i<_n;i++)d[size+i]=v[i];for(int i=size-1;i>=1;i--){update(i);}}void set(int p,S x){assert(0<=p&&p<_n);p+=size;for(int i=log;i>=1;i--)push(p>>i);d[p]=x;for(int i=1;i<=log;i++)update(p>>i);}
S get(int p){assert(0<=p&&p<_n);p+=size;for(int i=log;i>=1;i--)push(p>>i);return d[p];}S prod(int l,int r){assert(0<=l&&l<=r&&r<=_n);if(l==r)return e();l+=size;r+=size;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}S sml=e(),smr=e();while(l<r){if(l&1)sml=op(sml,d[l++]);if(r&1)smr=op(d[--r],smr);l>>=1;r>>=1;}return op(sml, smr);}S all_prod(){return d[1];}void apply(int p,F f){assert(0<=p&&p<_n);p+=size;for(int i=log;i>=1;i--)push(p>>i);d[p]=mapping(f,d[p]);for(int i=1;i<=log;i++)update(p>>i);}
void apply(int l,int r,F f){assert(0<=l&&l<=r&&r<=_n);if(l==r)return;l+=size;r+=size;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}{int l2=l,r2=r;while(l<r){if(l&1)all_apply(l++,f);if(r&1)all_apply(--r,f);l>>=1;r>>=1;}l=l2;r=r2;}for(int i=1;i<=log;i++){if(((l>>i)<<i)!=l)update(l>>i);if(((r>>i)<<i)!=r)update((r-1)>>i);}}template<bool(*g)(S)>int max_right(int l){return max_right(l,[](S x){return g(x);});}template<class G>int max_right(int l,G g){assert(0<=l&&l<=_n);assert(g(e()));if(l==_n)return _n;l+=size;for(int i=log;i>=1;i--)push(l>>i);S sm=e();do{while(l%2==0)l>>=1;
if(!g(op(sm,d[l]))){while(l<size){push(l);l=(2*l);if(g(op(sm,d[l]))){sm=op(sm,d[l]);l++;}}return l-size;}sm=op(sm,d[l]);l++;}while((l&-l)!=l);return _n;}template<bool(*g)(S)>int min_left(int r){return min_left(r,[](S x){return g(x);});}template<class G>int min_left(int r,G g){assert(0<=r&&r<=_n);assert(g(e()));if(r==0)return 0;r+=size;for(int i=log;i>=1;i--)push((r-1)>>i);S sm=e();do{r--;while(r>1&&(r%2))r>>=1;
if(!g(op(d[r],sm))){while(r<size){push(r);r=(2*r+1);if(g(op(d[r],sm))){sm=op(d[r],sm);r--;}}return r+1-size;}sm=op(d[r],sm);}while((r&-r)!=r);return 0;}private:int _n,size,log;vector<S>d;vector<F>lz;void update(int k){d[k]=op(d[2*k],d[2*k+1]);}void all_apply(int k,F f){d[k]=mapping(f,d[k]);if(k<size)lz[k]=composition(f,lz[k]);}void push(int k){all_apply(2*k,lz[k]);all_apply(2*k+1,lz[k]);lz[k]=id();}};}
namespace atcoder{ll pow_mod(ll x,ll n,int m){assert(0<=n&&1<=m);if(m==1)return 0;internal::barrett bt((ui)(m));ui r=1,y=(ui)(internal::safe_mod(x,m));while(n){if(n&1)r=bt.mul(r,y);y=bt.mul(y,y);n>>=1;}return r;}ll inv_mod(ll x,ll m){assert(1<=m);auto z=internal::inv_gcd(x,m);assert(z.first==1);return z.second;}pll crt(const vector<ll>&r,const vector<ll>&m){assert(r.size()==m.size());int n=int(r.size());ll r0=0,m0=1;for(int i=0;i<n;i++){assert(1<=m[i]);ll r1=internal::safe_mod(r[i],m[i]),m1=m[i];if(m0<m1){swap(r0,r1);swap(m0,m1);}if(m0%m1==0){if(r0%m1!=r1)return{0,0};continue;}
ll g,im;tie(g,im)=internal::inv_gcd(m0,m1);ll u1=(m1/g);if((r1-r0)%g)return{0,0};ll x=(r1-r0)/g%u1*im%u1;r0+=x*m0;m0*=u1;if(r0<0)r0+=m0;}return{r0,m0};}ll floor_sum(ll n,ll m,ll a,ll b){assert(0<=n&&n<(1LL<<32));assert(1<=m&&m<(1LL<<32));ull ans=0;if(a<0){ull a2=internal::safe_mod(a,m);ans-=1ULL*n*(n-1)/2*((a2-a)/m);a=a2;}if(b<0){ull b2=internal::safe_mod(b,m);ans-=1ULL*n*((b2-b)/m);b=b2;}return ans+internal::floor_sum_unsigned(n,m,a,b);}}
namespace atcoder{namespace internal{template<class T>struct simple_queue{vector<T>payload;int pos=0;void reserve(int n){payload.reserve(n);}int size()const{return int(payload.size())-pos;}bool empty()const{return pos==int(payload.size());}void push(const T&t){payload.push_back(t);}T&front(){return payload[pos];}void clear(){payload.clear();pos=0;}void pop(){pos++;}};}}
namespace atcoder{template<class Cap>struct mf_graph{public:mf_graph():_n(0){}explicit mf_graph(int n):_n(n),g(n){}int add_edge(int from,int to,Cap cap){assert(0<=from&&from<_n);assert(0<=to&&to<_n);assert(0<=cap);int m=int(pos.size());pos.push_back({from,int(g[from].size())});int from_id=int(g[from].size());int to_id=int(g[to].size());if(from==to)to_id++;g[from].push_back(_edge{to,to_id,cap});g[to].push_back(_edge{from,from_id,0});return m;}struct edge{int from,to;Cap cap,flow;};
edge get_edge(int i){int m=int(pos.size());assert(0<=i&&i<m);auto _e=g[pos[i].first][pos[i].second];auto _re=g[_e.to][_e.rev];return edge{pos[i].first,_e.to,_e.cap+_re.cap,_re.cap};}vector<edge>edges(){int m=int(pos.size());vector<edge>result;for(int i=0;i<m;i++){result.push_back(get_edge(i));}return result;}void change_edge(int i,Cap new_cap,Cap new_flow){int m=int(pos.size());assert(0<=i&&i<m);assert(0<=new_flow&&new_flow<=new_cap);auto&_e=g[pos[i].first][pos[i].second];auto&_re=g[_e.to][_e.rev];_e.cap=new_cap-new_flow;_re.cap=new_flow;}
Cap flow(int s,int t){return flow(s,t,numeric_limits<Cap>::max());}Cap flow(int s,int t,Cap flow_limit){assert(0<=s&&s<_n);assert(0<=t&&t<_n);assert(s!=t);vector<int>level(_n),iter(_n);internal::simple_queue<int>que;auto bfs=[&](){fill(level.begin(),level.end(),-1);level[s]=0;que.clear();que.push(s);while(!que.empty()){int v=que.front();que.pop();for(auto e:g[v]){if(e.cap==0||level[e.to]>=0)continue;level[e.to]=level[v]+1;if(e.to==t)return;que.push(e.to);}}};auto dfs=[&](auto self,int v,Cap up){if(v==s)return up;Cap res=0;int level_v=level[v];
for(int&i=iter[v];i<int(g[v].size());i++){_edge&e=g[v][i];if(level_v<=level[e.to]||g[e.to][e.rev].cap==0)continue;Cap d=self(self,e.to,min(up-res,g[e.to][e.rev].cap));if(d<=0)continue;g[v][i].cap+=d;g[e.to][e.rev].cap-=d;res+=d;if(res==up)return res;}level[v]=_n;return res;};Cap flow=0;while(flow<flow_limit){bfs();if(level[t]==-1)break;fill(iter.begin(),iter.end(),0);Cap f=dfs(dfs,t,flow_limit-flow);if(!f)break;flow+=f;}return flow;}vector<bool>min_cut(int s){vector<bool>visited(_n);internal::simple_queue<int>que;que.push(s);while(!que.empty()){int p=que.front();que.pop();visited[p]=true;
for(auto e:g[p]){if(e.cap&&!visited[e.to]){visited[e.to]=true;que.push(e.to);}}}return visited;}private:int _n;struct _edge{int to,rev;Cap cap;};vector<pair<int, int>>pos;vector<vector<_edge>>g;};}namespace atcoder{namespace internal{template<class E>struct csr{vector<int>start;vector<E>elist;explicit csr(int n,const vector<pair<int,E>>&edges):start(n+1),elist(edges.size()){for(auto e:edges){start[e.first+1]++;}for(int i=1;i<=n;i++){start[i]+=start[i-1];}auto counter=start;for(auto e:edges){elist[counter[e.first]++]=e.second;}}};}}
namespace atcoder{template<class Cap,class Cost>struct mcf_graph{public:mcf_graph(){}explicit mcf_graph(int n):_n(n){}int add_edge(int from,int to,Cap cap,Cost cost){assert(0<=from&&from<_n);assert(0<=to&&to<_n);assert(0<=cap);assert(0<=cost);int m=int(_edges.size());_edges.push_back({from,to,cap,0,cost});return m;}struct edge{int from,to;Cap cap,flow;Cost cost;};edge get_edge(int i){int m=int(_edges.size());assert(0<=i&&i<m);return _edges[i];}vector<edge>edges(){return _edges;}pair<Cap,Cost>flow(int s,int t){return flow(s,t,numeric_limits<Cap>::max());}
pair<Cap,Cost>flow(int s,int t, Cap flow_limit){return slope(s,t,flow_limit).back();}vector<pair<Cap,Cost>>slope(int s,int t){return slope(s,t,numeric_limits<Cap>::max());}vector<pair<Cap, Cost>>slope(int s,int t,Cap flow_limit){assert(0<=s&&s<_n);assert(0<=t&&t<_n);assert(s!=t);int m=int(_edges.size());vector<int>edge_idx(m);auto g=[&](){vector<int>degree(_n),redge_idx(m);vector<pair<int,_edge>>elist;elist.reserve(2*m);for(int i=0;i<m;i++){auto e=_edges[i];edge_idx[i]=degree[e.from]++;redge_idx[i]=degree[e.to]++;elist.push_back({e.from,{e.to,-1,e.cap-e.flow,e.cost}});elist.push_back({e.to,{e.from,-1,e.flow,-e.cost}});}
auto _g=internal::csr<_edge>(_n,elist);for(int i=0;i<m;i++){auto e=_edges[i];edge_idx[i]+=_g.start[e.from];redge_idx[i]+=_g.start[e.to];_g.elist[edge_idx[i]].rev=redge_idx[i];_g.elist[redge_idx[i]].rev=edge_idx[i];}return _g;}();auto result=slope(g,s,t,flow_limit);for(int i=0;i<m;i++){auto e=g.elist[edge_idx[i]];_edges[i].flow=_edges[i].cap-e.cap;}return result;}private:int _n;vector<edge>_edges;struct _edge{int to,rev;Cap cap;Cost cost;};vector<pair<Cap,Cost>>slope(internal::csr<_edge>&g,int s,int t,Cap flow_limit){vector<pair<Cost,Cost>>dual_dist(_n);vector<int>prev_e(_n);vector<bool>vis(_n);
struct Q{Cost key;int to;bool operator<(Q r)const{return key>r.key;}};vector<int>que_min;vector<Q>que;auto dual_ref=[&](){for(int i=0;i<_n;i++){dual_dist[i].second=numeric_limits<Cost>::max();}fill(vis.begin(),vis.end(),false);que_min.clear();que.clear();size_t heap_r=0;dual_dist[s].second=0;que_min.push_back(s);while(!que_min.empty()||!que.empty()){int v;if(!que_min.empty()){v=que_min.back();que_min.pop_back();}else{while(heap_r<que.size()){heap_r++;push_heap(que.begin(),que.begin()+heap_r);}v=que.front().to;
pop_heap(que.begin(),que.end());que.pop_back();heap_r--;}if(vis[v])continue;vis[v]=true;if(v==t)break;Cost dual_v=dual_dist[v].first,dist_v=dual_dist[v].second;for(int i=g.start[v];i<g.start[v+1];i++){auto e=g.elist[i];if(!e.cap)continue;Cost cost=e.cost-dual_dist[e.to].first+dual_v;if(dual_dist[e.to].second-dist_v>cost){Cost dist_to=dist_v+cost;dual_dist[e.to].second=dist_to;prev_e[e.to]=e.rev;if(dist_to==dist_v){que_min.push_back(e.to);}else{que.push_back(Q{dist_to,e.to});}}}}if(!vis[t]){return false;}
for(int v=0;v<_n;v++){if(!vis[v])continue;dual_dist[v].first-=dual_dist[t].second-dual_dist[v].second;}return true;};Cap flow=0;Cost cost=0,prev_cost_per_flow=-1;vector<pair<Cap,Cost>>result={{Cap(0),Cost(0)}};while(flow<flow_limit){if(!dual_ref())break;Cap c=flow_limit-flow;for(int v=t;v!=s;v=g.elist[prev_e[v]].to){c=min(c,g.elist[g.elist[prev_e[v]].rev].cap);}for(int v=t;v!=s;v=g.elist[prev_e[v]].to){auto&e=g.elist[prev_e[v]];e.cap+=c;g.elist[e.rev].cap-=c;}Cost d=-dual_dist[s].first;flow+=c;cost+=c*d;if(prev_cost_per_flow==d){result.pop_back();}result.push_back({flow,cost});prev_cost_per_flow=d;}return result;}};}
namespace atcoder{namespace internal{struct scc_graph{public:explicit scc_graph(int n):_n(n){}int num_vertices(){return _n;}void add_edge(int from,int to){edges.push_back({from,{to}});}pair<int,vector<int>>scc_ids(){auto g=csr<edge>(_n,edges);int now_ord=0,group_num=0;vector<int>visited,low(_n),ord(_n,-1),ids(_n);visited.reserve(_n);auto dfs=[&](auto self,int v)->void{low[v]=ord[v]=now_ord++;visited.push_back(v);for(int i=g.start[v];i<g.start[v+1];i++){auto to=g.elist[i].to;if(ord[to]==-1){self(self,to);low[v]=min(low[v],low[to]);}else{low[v]=min(low[v],ord[to]);}}
if(low[v]==ord[v]){while(1){int u=visited.back();visited.pop_back();ord[u]=_n;ids[u]=group_num;if(u==v)break;}group_num++;}};for(int i=0;i<_n;i++){if(ord[i]==-1)dfs(dfs,i);}for(auto&x:ids){x=group_num-1-x;}return{group_num,ids};}vector<vector<int>>scc(){auto ids=scc_ids();int group_num=ids.first;vector<int>counts(group_num);for(auto x:ids.second)counts[x]++;vector<vector<int>>groups(ids.first);for(int i=0;i<group_num;i++){groups[i].reserve(counts[i]);}for(int i=0;i<_n;i++){groups[ids.second[i]].push_back(i);}return groups;}private:int _n;struct edge{int to;};vector<pair<int,edge>>edges;};}}
namespace atcoder{struct scc_graph{public:scc_graph():internal(0){}explicit scc_graph(int n):internal(n){}void add_edge(int from,int to){int n=internal.num_vertices();assert(0<=from&&from<n);assert(0<=to&&to<n);internal.add_edge(from,to);}vector<vector<int>>scc(){return internal.scc();}private:internal::scc_graph internal;};}namespace atcoder{template<class S,S(*op)(S,S),S(*e)()>struct segtree{public:segtree():segtree(0){}explicit segtree(int n):segtree(vector<S>(n,e())){}explicit segtree(const vector<S>&v):_n(int(v.size())){log=internal::ceil_pow2(_n);size=1<<log;d=vector<S>(2*size,e());
for(int i=0;i<_n;i++){d[size+i]=v[i];}for(int i=size-1;i>=1;i--){update(i);}}void set(int p,S x){assert(0<=p&&p<_n);p+=size;d[p]=x;for(int i=1;i<=log;i++)update(p>>i);}S get(int p)const{assert(0<=p&&p<_n);return d[p+size];}S prod(int l,int r)const{assert(0<=l&&l<=r&&r<=_n);S sml=e(),smr=e();l+=size;r+=size;while(l<r){if(l&1)sml=op(sml,d[l++]);if(r&1)smr=op(d[--r],smr);l>>=1;r>>=1;}return op(sml,smr);}S all_prod() const{return d[1];}template<bool(*f)(S)>int max_right(int l)const{return max_right(l,[](S x){return f(x);});}template<class F>int max_right(int l,F f)const{assert(0<=l&&l<=_n);assert(f(e()));
if(l==_n){return _n;}l+=size;S sm=e();do{while(l%2==0)l>>=1;if(!f(op(sm,d[l]))){while(l<size){l=(2*l);if(f(op(sm,d[l]))){sm=op(sm,d[l]);l++;}}return l-size;}sm=op(sm,d[l]);l++;}while((l&-l)!=l);return _n;}template<bool(*f)(S)>int min_left(int r)const{return min_left(r,[](S x){return f(x);});}template<class F>int min_left(int r,F f)const{assert(0<=r&&r<=_n);assert(f(e()));if(r==0)return 0;r+=size;S sm=e();do{r--;while(r>1&&(r%2))r>>=1;if(!f(op(d[r],sm))){while(r<size){r=(2*r+1);if(f(op(d[r],sm))){sm=op(d[r],sm);r--;}}return r+1-size;}sm=op(d[r],sm);}while((r&-r)!=r);return 0;}private:int _n,size,log;vector<S>d;
void update(int k){d[k]=op(d[2*k],d[2*k+1]);}};}namespace atcoder{namespace internal{vector<int>sa_naive(const vector<int>&s){int n=int(s.size());vector<int>sa(n);iota(sa.begin(),sa.end(),0);sort(sa.begin(),sa.end(),[&](int l,int r){if(l==r)return false;while(l<n&&r<n){if(s[l]!=s[r])return s[l]<s[r];l++;r++;}return l==n;});return sa;}vector<int>sa_doubling(const vector<int>&s){int n=int(s.size());vector<int>sa(n),rnk=s,tmp(n);iota(sa.begin(),sa.end(),0);for(int k=1;k<n;k*=2){auto cmp=[&](int x,int y){if(rnk[x]!=rnk[y])return rnk[x]<rnk[y];int rx=x+k<n?rnk[x+k]:-1;int ry=y+k<n?rnk[y+k]:-1;return rx<ry;};
sort(sa.begin(),sa.end(),cmp);tmp[sa[0]]=0;for(int i=1;i<n;i++){tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);}swap(tmp, rnk);}return sa;}template<int THRESHOLD_NAIVE=10,int THRESHOLD_DOUBLING=40>vector<int>sa_is(const vector<int>&s,int upper){int n=int(s.size());if(n==0)return{};if(n==1)return{0};if(n==2){if(s[0]<s[1]){return{0,1};}else{return{1,0};}}if(n<THRESHOLD_NAIVE){return sa_naive(s);}if(n<THRESHOLD_DOUBLING){return sa_doubling(s);}vector<int>sa(n);vector<bool>ls(n);for(int i=n-2;i>=0;i--){ls[i]=(s[i]==s[i+1])?ls[i+1]:(s[i]<s[i+1]);}vector<int>sum_l(upper+1),sum_s(upper+1);
for(int i=0;i<n;i++){if(!ls[i]){sum_s[s[i]]++;}else{sum_l[s[i]+1]++;}}for(int i=0;i<=upper;i++){sum_s[i]+=sum_l[i];if(i<upper)sum_l[i+1]+=sum_s[i];}auto induce=[&](const vector<int>&lms){fill(sa.begin(),sa.end(),-1);vector<int>buf(upper+1);copy(sum_s.begin(),sum_s.end(),buf.begin());for(auto d:lms){if(d==n)continue;sa[buf[s[d]]++]=d;}copy(sum_l.begin(),sum_l.end(),buf.begin());sa[buf[s[n-1]]++]=n-1;for(int i=0;i<n;i++){int v=sa[i];if(v>=1&&!ls[v-1]){sa[buf[s[v-1]]++]=v-1;}}copy(sum_l.begin(),sum_l.end(),buf.begin());for(int i=n-1;i>=0;i--){int v=sa[i];if(v>=1&&ls[v-1]){sa[--buf[s[v-1]+1]]=v-1;}}};
vector<int>lms_map(n+1,-1);int m=0;for(int i=1;i<n;i++){if(!ls[i-1]&&ls[i]){lms_map[i]=m++;}}vector<int>lms;lms.reserve(m);for(int i=1;i<n;i++){if(!ls[i-1]&&ls[i]){lms.push_back(i);}}induce(lms);if(m){vector<int>sorted_lms;sorted_lms.reserve(m);for(int v:sa){if(lms_map[v]!=-1)sorted_lms.push_back(v);}vector<int>rec_s(m);int rec_upper=0;rec_s[lms_map[sorted_lms[0]]]=0;for(int i=1;i<m;i++){int l=sorted_lms[i-1],r=sorted_lms[i];int end_l=(lms_map[l]+1<m)?lms[lms_map[l]+1]:n;int end_r=(lms_map[r]+1<m)?lms[lms_map[r]+1]:n;bool same=true;if(end_l-l!=end_r-r){same=false;}else{while(l<end_l){
if(s[l]!=s[r]) {break;}l++;r++;}if(l==n||s[l]!=s[r])same=false;}if(!same)rec_upper++;rec_s[lms_map[sorted_lms[i]]]=rec_upper;}auto rec_sa=sa_is<THRESHOLD_NAIVE,THRESHOLD_DOUBLING>(rec_s,rec_upper);for(int i=0;i<m;i++){sorted_lms[i]=lms[rec_sa[i]];}induce(sorted_lms);}return sa;}}vector<int>suffix_array(const vector<int>&s,int upper){assert(0<=upper);for(int d:s){assert(0<=d&&d<=upper);}auto sa=internal::sa_is(s,upper);return sa;}template<class T>vector<int>suffix_array(const vector<T>&s){int n=int(s.size());vector<int>idx(n);iota(idx.begin(),idx.end(),0);sort(idx.begin(),idx.end(),[&](int l,int r){return s[l]<s[r];});
vector<int>s2(n);int now=0;for(int i=0;i<n;i++){if(i&&s[idx[i-1]]!=s[idx[i]])now++;s2[idx[i]]=now;}return internal::sa_is(s2,now);}vector<int>suffix_array(const string&s){int n=int(s.size());vector<int>s2(n);for(int i=0;i<n;i++){s2[i]=s[i];}return internal::sa_is(s2,255);}template <class T>vector<int>lcp_array(const vector<T>&s,const vector<int>&sa){int n=int(s.size());assert(n>=1);vector<int>rnk(n);for(int i=0;i<n;i++){rnk[sa[i]]=i;}vector<int>lcp(n-1);int h=0;for(int i=0;i<n;i++){if(h>0)h--;if(rnk[i]==0)continue;int j=sa[rnk[i]-1];for(;j+h<n&&i+h<n;h++){if(s[j+h]!=s[i+h])break;}lcp[rnk[i]-1]=h;}return lcp;}
vector<int>lcp_array(const string&s,const vector<int>&sa){int n=int(s.size());vector<int>s2(n);for(int i=0;i<n;i++){s2[i]=s[i];}return lcp_array(s2,sa);}template<class T>vector<int>z_algorithm(const vector<T>&s){int n=int(s.size());if(n==0)return{};vector<int>z(n);z[0]=0;for(int i=1,j=0;i<n;i++){int&k=z[i];k=(j+z[j]<=i)?0:min(j+z[j]-i,z[i-j]);while (i+k<n&&s[k]==s[i+k])k++;if(j+z[j]<i+z[i])j=i;}z[0]=n;return z;}vector<int>z_algorithm(const string&s){int n=int(s.size());vector<int>s2(n);for(int i=0;i<n;i++){s2[i]=s[i];}return z_algorithm(s2);}}
namespace atcoder{struct two_sat{public:two_sat():_n(0),scc(0){}explicit two_sat(int n):_n(n),_answer(n),scc(2*n){}void add_clause(int i,bool f,int j,bool g){assert(0<=i&&i<_n);assert(0<=j&&j<_n);scc.add_edge(2*i+(f?0:1),2*j+(g?1:0));scc.add_edge(2*j+(g?0:1),2*i+(f?1:0));}bool satisfiable(){auto id=scc.scc_ids().second;for(int i=0;i<_n;i++){if(id[2*i]==id[2*i+1])return false;_answer[i]=id[2*i]<id[2*i+1];}return true;}vector<bool>answer(){return _answer;}private:int _n;vector<bool>_answer;internal::scc_graph scc;};}

//——————————————————Atcoder Library———————————————————


#define endl "\n"              //←これ

using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rep2(i,a,b) for(ll i=a; i<=b; i++)
#define per(i,a,b) for(ll i=a; i>=b; i--)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define srt(v) sort(v.begin(),v.end())
#define trs(v) sort(v.rbegin(),v.rend())
#define rev(v) reverse(v.begin(),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define cou(x) __builtin_popcountll(x)
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(b<a){a=b;return 1;}return 0;}
ll gcd(ll x, ll y){return y? gcd(y,x%y) : x;}
ll lcm(ll x, ll y){return x / gcd(x,y) * y;}

vector<ll> vl(ll n,ll x){vector<ll> re(n,x);return re;}
vector<ld> vd(ll n,ld x){vector<ld> re(n,x);return re;}
vector<string> vs(ll n,ll m){vector<string> re(n,string(m,'.'));return re;}
vector<vector<ll>> vl(ll n, ll m,ll x){vector<vector<ll>> re(n,vector<ll>(m,x));return re;}
vector<vector<ld>> vd(ll n, ll m,ld x){vector<vector<ld>> re(n,vector<ld>(m,x));return re;}
vector<vector<vector<ll>>> vl(ll a, ll b, ll c,ll x){vector<vector<vector<ll>>> re(a,vector<vector<ll>>(b,vector<ll>(c,x)));return re;}
vector<vector<vector<ld>>> vd(ll a, ll b, ll c,ld x){vector<vector<vector<ld>>> re(a,vector<vector<ld>>(b,vector<ld>(c,x)));return re;}
vector<vector<vector<vector<ll>>>> vl(ll a, ll b, ll c,ll d,ll x){vector<vector<vector<vector<ll>>>> re(a,vector<vector<vector<ll>>>(b,vector<vector<ll>>(c,vector<ll>(d,x))));return re;}
vector<vector<vector<vector<ld>>>> vd(ll a, ll b, ll c,ll d,ld x){vector<vector<vector<vector<ld>>>> re(a,vector<vector<vector<ld>>>(b,vector<vector<ld>>(c,vector<ld>(d,x))));return re;}

template<class T>void out(T x) {cout << x << endl;}
template<class T>void out(T x,T y) {cout << x << " " << y << endl;}
template<class T>void out(T x,T y,T z) {cout << x << " " << y << " " << z << endl;}
template<class T>void out(T a,T b,T c,T d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<class T>void out(T a,T b,T c,T d,T e) {cout << a << " " << b << " " << c << " " << d << " " << e << endl;}
template<class T>void out(T a,T b,T c,T d,T e,T f) {cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;}
template<class T>void out(pair<T,T> p) {cout << p.fi << " " << p.se << endl;}
template<class T>void vout(vector<T> &v){if(v.size()>0){for(auto it = v.begin(); it < v.end(); it++){cout << *it;if(it != v.end()-1) cout<<" ";}}cout<<endl;}
template<class T>void pout(vector<T> &v){if(v.size()>0){for(auto it = v.begin(); it < v.end(); it++){cout << *it+1;if(it != v.end()-1) cout<<" ";}}cout<<endl;}
template<class T>void vout(vector<vector<T>> &v){if(v.size()>0){for(auto it = v.begin(); it < v.end(); it++) {vout(*it);}}}
template<class T>void vout(vector<pair<T,T>> &v){if(v.size()>0){for(auto it = v.begin(); it < v.end(); it++){out(*it);}}}
void sout(vector<string> &v){if(v.size()>0){for(auto it = v.begin(); it < v.end(); it++){cout << *it <<endl;}}}

vector<string> YES={"NO","YES"};
vector<string> Yes={"No","Yes"};
vector<string> yes={"no","yes"};
vector<string> POS={"IMPOSSIBLE","POSSIBLE"};
vector<string> Pos={"Impossible","Possible"};
vector<string> pos={"impossible","possible"};
vector<string> FIS={"SECOND","FIRST"};
vector<string> Fis={"Second","First"};
vector<string> fis={"second","first"};

//———————————————tento 転倒数—————————————————
  ll tento(vector<ll>v){
    ll n=v.size();
    vector<ll> v2(n);
    vector<pll> vp(n);
    rep(i,n) vp[i]={v[i],i};
    sort(all(vp));
    rep(i,n) v2[vp[i].se]=i;
    fenwick_tree<ll> bit(n);
    ll re=0;
    rep(i,n){
      re+=i-bit.sum(0,v2[i]+1);
      bit.add(v2[i], 1);      
    }
    return re;
  }
//———————————————————————————————————————————————

//——————————————————————————————LIS　最長増加部分列————————————————————————————————
template <typename T> size_t lis(const vector<T>& a,bool strict=true){
  vector<T> lis;
  for(auto& p : a){
    typename vector<T>::iterator it;
    if(strict) it = lower_bound(begin(lis),end(lis),p);
    else it = upper_bound(begin(lis),end(lis),p);
    if(end(lis) == it) lis.emplace_back(p);
    else *it = p;
  }
  return lis.size();
}
//—————————————————————————————————————————————————————————————————————————————

//ベクター入力
  vector<ll> pin(ll n){
    vector<ll> re(n);
    rep(i,n) cin>>re[i];
    return re;
  }
//ベクター入力 -1
  vector<ll> hin(ll n){
    vector<ll> re(n);
    rep(i,n){
      cin>>re[i];
      re[i]--;
    }
    return re;
  }

//二次元ベクター入力
  vector<vector<ll>> ppin(ll h,ll w){
    vector<vector<ll>> re(h,vector<ll>(w));
    rep(i,h) rep(j,w) cin>>re[i][j];
    return re;
  }

//ストリング入力
  vector<string> stin(ll n){
    vector<string> re(n);
    rep(i,n) cin>>re[i];
    return re;
  }

//グラフ入力
  vector<vector<ll>> gin(ll n,ll m,ll hoko,ll pl){
    vector<vector<ll>> re(n);
    rep(i,m){
      ll a,b;
      cin>>a>>b;
      a+=pl;b+=pl;
      re[a].pb(b);
      if(hoko==2) re[b].pb(a);
    }
    return re;
  }
//グラフdist
  vector<ll> gdis(vector<vector<ll>> &g, ll st){
    ll n=g.size();
    vector<ll> dist(n,INF);
    queue<ll> que;
    dist[st]=0;
    que.push(st);
    while(!que.empty()){
      ll x=que.front();
      que.pop();
      for(ll nx:g[x]){
        if(dist[nx]!=INF) continue;
        dist[nx]=dist[x]+1;
        que.push(nx);
      }
    }
    return dist;
  }

//グラフ距離入力
  vector<vector<pll>> ggin(ll n,ll m,ll hoko,ll pl){
    vector<vector<pll>> re(n);
    rep(i,m){
      ll a,b,c;
      cin>>a>>b>>c;
      a+=pl;b+=pl;
      re[a].pb({b,c});
      if(hoko==2) re[b].pb({a,c});
    }
    return re;
  }
//グラフ距離dist
  vector<ll> gdis(vector<vector<pll>> &g, ll st){
    ll n=g.size();
    vector<ll> dist(n,INF);
    priority_queue<pll,vector<pll>,greater<pll>> que;
    dist[st]=0;
    que.push({0,st});
    while(!que.empty()){
      pll z=que.top();
      que.pop();
      ll x=z.se;
      if(dist[x]!=z.fi) continue;
      for(pll nz:g[x]){
        ll nx=nz.fi;
        ll ny=nz.se;
        if(dist[nx]<=dist[x]+ny) continue;
        dist[nx]=dist[x]+ny;
        que.push({dist[nx],nx});
      }
    }
    return dist;
  }

//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//実行時間制約2秒では２×10^8回くらいまで計算できる
//「#define endl "\n"」はインタラクティブで消す！！！

//using mint = modint998244353;
using mint = modint1000000007;
//using mint = modint;
//下でmodint::set_mod(m);

void out(mint &x) {out(x.val());}
void out(mint &x,mint &y) {out(x.val(),y.val());}
void out(mint &x,mint &y,mint &z) {out(x.val(),y.val(),z.val());}
void out(mint &x,mint &y,mint &z,mint &a) {out(x.val(),y.val(),z.val(),a.val());}
void out(ll &x,mint &y) {out(x,(ll)y.val());}
void out(mint &x,ll &y) {out((ll)x.val(),y);}
void out(ll &x,ll &y,mint &z) {out(x,y,(ll)z.val());}
void out(ll &x,mint &y,mint &z) {out(x,(ll)y.val(),(ll)z.val());}

vector<mint> vm(ll n){vector<mint> re(n,0);return re;}
vector<vector<mint>> vm(ll n, ll m){vector<vector<mint>> re(n,vector<mint>(m,0));return re;}
vector<vector<vector<mint>>> vm(ll n, ll m, ll l){vector<vector<vector<mint>>> re(n,vector<vector<mint>>(m,vector<mint>(l,0)));return re;}
vector<vector<vector<vector<mint>>>> vm(ll a, ll b, ll c, ll d){vector<vector<vector<vector<mint>>>> re(a,vector<vector<vector<mint>>>(b,vector<vector<mint>>(c,vector<mint>(d,0))));return re;}
void vout(vector<mint> &v){ll n=v.size();rep(i,n-1) cout<<v[i].val()<<" ";cout<<v[n-1].val()<<endl;}
void vout(vector<vector<mint>> &v){ll n=v.size();if(n>0) rep(i,n) vout(v[i]);}

vector<ll> vx={1,-1,0,0,1,-1,1,-1,0};
vector<ll> vy={0,0,1,-1,1,-1,-1,1,0};





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


  ll n;
  cin>>n;

  ll x=0,y=0,z=0;
  rep(i,n){
    ll a;
    cin>>a;
    if(a==1) x++;
    else if(a==2) y++;
    else z++;
  }

  ll ans=x*(x-1)+y*(y-1)/2+z*(z-1)/2+3*x*y+y*z+2*z*x;

  out(ans);
}
yukicoder

結果

テストケース

ソースコード
