# CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces

N ≤ 1e5

O( N^1.5 ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];

int ans[ MAXN + 1 ];

int calc( int k ){
static vector< int > cnt( MAXN + 1 );
int res = 0;
for( int i = 0; i < N; ){
++res;
int j = i;
int f = 0;
while( j < N and f <= k ){
if( f == k and cnt[ A[ j ] ] == 0 ) break;
f += ++cnt[ A[ j++ ] ] == 1;
}
while( i < j ){
--cnt[ A[ i++ ] ];
}
}
return res;
}

void dvcq( int lb, int rb ){ // ( lb, rb )
if( rb - lb < 2 ) return;
if( ans[ lb ] == ans[ rb ] ){
for( int i = lb + 1; i < rb; ++i ){
ans[ i ] = ans[ lb ];
}
return;
}
int mid = lb + rb >> 1;
ans[ mid ] = calc( mid );
dvcq( lb, mid );
dvcq( mid, rb );
}

signed main(){
ios::sync_with_stdio( 0 );
{ // input
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
}
{
ans[ 1 ] = calc( 1 );
ans[ N ] = calc( N );
dvcq( 1, N );
}
{
for( int i = 1; i <= N; ++i ){
cout << ans[ i ] << " \n"[ i == N ];
}
}
return 0;
}
```