# CFR 305 B. Mike and Feet ( UnionFind )

Problem - 547b - Codeforces

```struct UF{
vi fa;
vi size;
UF( int sz ){
fa = vi( sz );
size = vi( sz );
for( int i = 0; i < sz; ++i )
fa[ i ] = i,
size[ i ] = 1;
}
int find( int x ){
if( fa[ x ] == x )
return x;
return fa[ x ] = find( fa[ x ] );
}
int unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b )
return 0;
size[ a ] += size[ b ];
fa[ b ] = a;
return 1;
}
};

int N;
vi A;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ];
}

vi ans;

void preprocess(){
ans = vi( N + 1 );
UF *uf = new UF( N );
vp bear;
for( int i = 0; i < N; ++i )
bear.emplace_back( A[ i ], i );
sort( bear.begin(), bear.end(), greater< pii >() );
vi vis( N );
for( int i = 0, ans_ptr = 1; i < N; ++i ){
int v, p; tie( v, p ) = bear[ i ];
vis[ p ] = 1;
if( 0 <= p - 1 and vis[ p - 1 ] )
uf->unite( p - 1, p );
if( p + 1 < N and vis[ p + 1 ] )
uf->unite( p, p + 1 );
while( ans_ptr <= uf->size[ uf->find( p ) ] )
ans[ ans_ptr++ ] = v;
}
delete uf;
}

void solve(){
for( int i = 1; i <= N; ++i )
cout << ans[ i ] << " \n"[ i == N ];
}
```