题目描述

给出一个长度为$n$的正整数序列$a_1,a_2 \cdots a_n$。定义一个区间$[L,R]$为“特殊区间”，当且仅当存在一个$k \in [L,R]$，对于任意的$i \in [L,R]$，都有$a_k \vert a_i$。特殊区间$[L,R]$的价值为$R-L$。
你的任务是求出所有特殊区间的最大价值是多少，有多少个达到最大价值的特殊区间，这些区间又分别是哪些。
$x \vert y$表示$x$整除$y$，即$y \mod x = 0$。

输入格式

第一行一个整数$n$；
第二行$n$个正整数$a_1, a_2 \cdots a_n$。

输出格式

第一行包含两个整数$num,val$，分别表示价值最大的特殊区间的个数和最大价值；
第二行$num$个整数，按照升序输出每个价值最大的特殊区间的左端点$L_1 \cdots L_{num}$。
输出时一行内的两个数之间用1个空格隔开。

样例

输入

5
4 6 9 3 6

输出

1 3
2

数据规模、时空限制

对于30%的数据，$1 \le n \le 30, \quad 1 \le a_i \le 32$
对于60%的数据，$1 \le n \le 3000,\quad 1 \le a_i \le 1024$
对于100%的数据，$1 \le n \le 10^5, \quad 1 \le a_i < 2^{31}$
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑