2019.2.11 Problem C - pair

2019.2.11 Problem C - pair

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个长度为\(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提高组集训
供题人:于剑

2019.2.11补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
3
开始于
2019-02-11 17:30
结束于
2019-02-21 00:00
持续时间
222.5 小时
主持人
参赛人数
30