#130. 「一本通 2.1 练习 5」珍珠项链 Beads

「一本通 2.1 练习 5」珍珠项链 Beads

题目描述

译自 POI 2010 Stage 1.「Beads

Byteasar 决定制造一条项链,她买了一串珠子,她有一个机器,能把这条珠子切成很多段,使得每段恰有 kk 个珠子 (k>0)(k>0) ,如果这条珠子的长度不是 kk 的倍数,最后一块长度小于 kk 的段就被丢弃了。
Byteasar 想知道,选择什么数字 kk 可以得到最多的不同的段。注意这里的段是可以反转的,即,子串 1,2,31,2,33,2,13,2,1 被认为是一样的。

输入格式

第一行一个正整数 nn ,表示珠子的长度。
第二行 nn 个空格隔开的正整数 a1,a2,ana_1,a_2,\cdots a_n ,描述这一串珠子的颜色。

输出格式

第一行两个空格隔开的正整数,第一个表示能获得的最大不同的段的个数,第二个表示能获得最大值的 kk 的个数。
第二行若干空格隔开的正整数 kk ,表示所有能够取得最大值的 kk ,请将kk按照从小到大的顺序输出。

样例

21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1
6 1
2

数据范围与提示

对于 100%100\% 的数据, 1n2×1051\le n\le 2\times 10^5 ,且 1in\forall 1\le i\le n ,有 1ain1\le a_i\le n

Translated By diamond_duke