Codeforces 264 B. Good Sequences

Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a1, a2, ..., an are good.

Now she is interested in good sequences. A sequence x1, x2, ..., xk is called good if it satisfies the following three conditions:

The sequence is strictly increasing, i.e. xi < xi + 1 for each i (1 ≤ i ≤ k - 1).
No two adjacent elements are coprime, i.e. gcd(xi, xi + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).
All elements of the sequence are good integers.

Find the length of the longest good sequence.

Input

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 105) — the number of good integers. The second line contains a single-space separated list of good integers a1, a2, ..., an in strictly increasing order (1 ≤ ai ≤ 105; ai < ai + 1).

Output

Print a single integer — the length of the longest good sequence.

Examples

input

5
2 3 4 6 9

output

input

9
1 2 3 5 6 7 8 9 10

output

Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

题目链接

题意

给一个严格递增的序列，求出最长的相邻元素不互质的递增序列。

分析

不互质则必有相同的因子，那么只要相邻的有相同的因子，那么就可以一段拼一段，从而拼出最长的。先预处理每个数的因子，对于当前序列，处理每个数的因子出现的次数，用来更新维护dp[i](最后一对元素的公共因子为i的最长长度)，即先从该数的所以因子中选出dp值最大的那个，这就说明当前这个数可以拼接上去，形成新的序列，长度+1，此时再更新当前数的所有因子的dp值。最后再遍历一边，找出最大长度。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const int mod = 772002+233;
typedef pair<int,int> pii;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ms(a,b) memset(a,b,sizeof(a))
vector<int> p[maxn];
int n;
void init(){
    for(int i=2;i<maxn;i++){
        for(int j=i;j<maxn;j+=i){
            p[j].pb(i);
        }
    }
}
int a[maxn];
int d[maxn];
int main(){
//    freopen("in.txt","r",stdin);
    init();
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        int maxx=0;
        for(int j=0;j<p[a[i]].size();j++){
//            cout<<p[a[i]][j]<<" ";
            maxx = max(maxx,d[p[a[i]][j]]);
        }
        for(int j=0;j<p[a[i]].size();j++){
            d[p[a[i]][j]]=maxx+1;
        }
//        puts("");
    }
    int maxx = 1;
    for(int i=0;i<maxn;i++) maxx = max(maxx,d[i]);
    cout<<maxx;
    return 0;
}