# CFR 264 B. Good Sequences ( DP )

Problem - 264B - Codeforces

```int N;
vi A;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ];
int all_one = 1;
for( int i = 0; i < N; ++i )
all_one &= A[ i ] == 1;
if( all_one ){
cout << 1 << endl;
exit( 0 );
}
}

vi np;
vvi pf; // prime factor table

vi acnt;
vi dp;

void preprocess(){
np = vi( ( int ) 1e5 + 1 );
pf = vvi( ( int ) 1e5 + 1 );
for( int i = 2; i <= ( int ) 1e5; ++i )
if( not np[ i ] )
for( int j = i + i; j <= ( int ) 1e5; j += i )
np[ j ] = 1,
pf[ j ].emplace_back( i );
acnt = dp = vi( ( int ) 1e5 + 1 );
for( int i = 0; i < N; ++i )
++acnt[ A[ i ] ],
dp[ A[ i ] ] = 1;
for( int i = 2; i <= ( int ) 1e5; ++i )
for( int j = 0; j < pf[ i ].size(); ++j )
acnt[ pf[ i ][ j ] ] = 1;
for( int i = 2; i <= ( int ) 1e5; ++i ) if( acnt[ i ] ){
for( int j = 0; j < pf[ i ].size(); ++j ) if( acnt[ pf[ i ][ j ] ] )
upmax( dp[ i ], dp[ pf[ i ][ j ] ] + 1 );
for( int j = 0; j < pf[ i ].size(); ++j ) if( acnt[ pf[ i ][ j ] ] )
upmax( dp[ pf[ i ][ j ] ], dp[ i ] );
}
}

void solve(){
int ans = 0;
for( int i = 2; i <= ( int ) 1e5; ++i )
upmax( ans, dp[ i ] );
cout << ans << endl;
}
```