/ TYWZ / 题库 /

2019.2.11 Problem C - pair

2019.2.11 Problem C - pair

题目描述

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

输入格式

第一行一个整数nn
第二行nn个正整数a1,a2ana_1, a_2 \cdots a_n

输出格式

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

样例

输入

5
4 6 9 3 6

输出

1 3
2

数据规模、时空限制

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

来源

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

信息

难度
7
分类
其他 | 二分查找RMQ 点击显示
标签
(无)
递交数
90
已通过
14
通过率
16%
上传者

相关