解题思路
核心贪心：能切就立刻切
从左到右维护当前未结束段的 gcd 与长度。当第一次出现
gcd≤当前长度
题目内容
给定一个长度为 n 的正整数数组 {a1,a2,…,an} ;
我们称一段连续子数组 al,al+1,...,ar 为优美段，当且仅当这段子数组的 gcd(al,al+1,...,ar)≤r−l+1 ;
请将整个数组划分成 k 段互不相交的优美段，覆盖原数组每个位置，求使 k 最大化，输出最大值 k 。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≦T≦104) ，表示测试用例的组数；
除此之外，保证所有测试用例的 n 之和不超过 2×105 ；
随后对每组测试数据，按以下格式输入：
-
第一行输入一个整数 n(1≦n≦2×105) ;
-
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109)
输出描述
对于每组测试数据，新起一行输出一个整数，表示将数组划分为优美段的最大段数，如果没有任何分割方式输出 ′−1′ 。
样例1
输入
2
5
5 4 4 2 1
3
4 4 4
输出
3
-1
