题目描述
给出一个长度为n的正整数序列a1,a2⋯an。定义一个区间[L,R]为“特殊区间”,当且仅当存在一个k∈[L,R],对于任意的i∈[L,R],都有ak∣ai。特殊区间[L,R]的价值为R−L。
你的任务是求出所有特殊区间的最大价值是多少,有多少个达到最大价值的特殊区间,这些区间又分别是哪些。
x∣y表示x整除y,即ymodx=0。
输入格式
第一行一个整数n;
第二行n个正整数a1,a2⋯an。
输出格式
第一行包含两个整数num,val,分别表示价值最大的特殊区间的个数和最大价值;
第二行num个整数,按照升序输出每个价值最大的特殊区间的左端点L1⋯Lnum。
输出时一行内的两个数之间用1个空格隔开。
样例
输入
输出
数据规模、时空限制
对于30%的数据,1≤n≤30,1≤ai≤32
对于60%的数据,1≤n≤3000,1≤ai≤1024
对于100%的数据,1≤n≤105,1≤ai<231
时间限制1s,空间限制512MB。
来源
2019.2 TYWZ提高组集训
供题人:于剑