题目描述

给定一个单调上升序列 $a$，在这个序列中选若干个数（不要求相邻），满足相邻两个数不互质。问最多可以选多少个。

输入格式

第一行一个整数 $n$，$1\le n\le 10^5$。

第二行 $n$ 个整数 $a_i$，$1\le a_i\le 10^5$，保证升序。

输出格式

输出一个整数表示答案。

5
2 3 4 6 9

4

9
1 2 3 5 6 7 8 9 10

4