题目描述

给定一个长度为 $n$ 的数组，请你找到一个最长的连续区间，使得区间内数字两两之间不存在共同因数（因子）。 找到之后，输出这个最长区间的长度。

例如 $2,6$ 之间存在共同因数（因子），因数为 $1,2$。

例如 $11,13$ 之间存在共同因数（因子），因数为 $1$。

输入格式

第一行包含一个正整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_i$ 代表数组内的元素。

输出格式

输出共一行，输出最长区间的长度。

样例

6
1 1 4 5 1 4

1

样例 1 解释

数组中对于任意相邻的两个数都有因数 $1$，不存在长度为 $2$ 的区间，所以区间的长度只能为 $1$。

6
6 6 6 6 6 6

1

样例 2 解释

数组中对于任意相邻的两个数都有因数 $1,6$，不存在长度为 $2$ 的区间，所以区间的长度只能为 $1$。

数据范围

对于 $100\%$ 的数据保证：$1 \le n \le 100,1 \le a_i \le 10^5$。