You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 C 非常喜欢数字。 这次，他得到了一个长度为 n 的正整数数列 A，第 i 项为 ai。现在，小 C 想要找出来 A 中最长的子序列B = {b1, b2, ...... , bm}，使得对于任意的二元组 (i, j)，bi 和 bj 满足​倍数关系​。小 C 突然不会最长不下降子序列了，于是找到了你来帮他求出最长的子序列的长度。

​子序列：​对于长度为 n 的数列 A，对于 B ={b1, b2, ...... , bm}，若 b1= ap1 , b2=ap2, ......, bm= a​pm，则必须要满足 1 ≤ p1< p​2 ​< ...... < pm≤ n，这样的数列 B 称为 A 的子序列。其中子序列B可以为空。

输入格式

共两行，第一行有一个正整数 n，表示数列 A 的长度； 第二行有 n 个正整数，第 i 个数表示 ai。

输出格式

仅一行一个数，表示子序列长度的最大值。

输入输出样例

5 
1 2 3 8 16

4

10 
1 4 6 3 9 11 16 24 42 36

4

数据规模