题目描述

Byteasar once decided to start manufacturing necklaces.

He subsequently bought a very long string of colourful coral beads for a bargain price.

Byteasar now also has a machine that, for a given (), can cut the string into pieces (or substrings) of coral beads (i.e., the first piece consists of the beads no.

, the second of , etc.).

If the length of the string (measured in coral beads) is not a multiple of , then the last piece is not used, as it has length smaller than .

From now on we denote the colours of the beads with positive integers.

Byteasar, always praising diversity, wonders how he should choose the number in order to get as many different substrings as possible.

The ends of the long string that will be cut are different: there are specific beginning and ending (rather than two interchangeable endpoints), and the machine of course starts cutting at the beginning. On the other hand, in the substrings obtained from cutting the endpoints are interchangeable, and so the substrings can be reversed. In other words, the substrings and are identical to us. Write a program that determines the optimum value of for Byteasar.

Zxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有k（k>0）个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。 Zxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串（1，2，3）和（3,2,1）是一样的。写一个程序，为Zxl决定最适合的k从而获得最多不同的子串。 例如：这一串珠子是： (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)， k=1的时候，我们得到3个不同的子串： (1),(2),(3) k=2的时候，我们得到6个不同的子串： (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3的时候，我们得到5个不同的子串： (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2) k=4的时候，我们得到5个不同的子串： (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)

输入格式

In the first line of the standard input there is an integer () denoting the length of the string to cut.

In the second line there are positive integers (), separated by single spaces, that denote the colours of successive beads in Byteasar's string.

输出格式

Two integers, separated by a single space, should be printed out to the first line of the standard ouput:

the (maximum) number of different substrings that can be obtained with an optimal choice of parameter , and the number of such optimal values of .

The second line should contain integers separated by single spaces:

the values of parameter that yield an optimum solution; these can be given in arbitrary order.

输出两行，第一行第一个数为最多可以得到的不同子串的个数，第二个数为取到最优解时的不同的k的个数。第二行包含若干个数，为取到最优解时的不同的k 。第二行中的不同的k可以按任意位置输出。

题目大意

【题目描述】

Byteasar 有 $n$ 个珠子，第 $i$ 个颜色为 $a_i$，和一台机器。

Byteasar 可以选定一个值 $k$，然后机器会让 $1\sim k$ 的珠子组成项链 $b_1$，$k+1\sim 2k$ 的珠子组成项链 $b_2$，以此类推，最后 $n\bmod k$ 个珠子不会组成项链，而是被丢弃。

现在让你求出一个 $k$ 值，使得在 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 个项链 $b$ 中，存在 不同的 项链数量最多。

项链可以反转，形式化地，$b_x$ 和 $b_y$ 不同，当且仅当存在至少一个 $i$，使得 $b_{x,i}\ne b_{y,i}$ 且 $b_{x,i} \ne b_{y,k-i+1}$。

例如 $[1,2,3]$ 和 $[3,2,1]$ 是相同的，而 $[1,2,3]$ 和 $[2,3,1]$ 是不同的。

【输入格式】

输入两行，第一行为 $n$。

第二行为 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$。

【输出格式】

输出两行。

第一行两个整数，分别代表不同的项链最多的数量，以及不同的项链最多时，$k$ 的个数。

第二行若干个整数，代表所有能使不同的项链最多的 $k$ 值，这可以按任意顺序输出。

【样例解释】

$a$ 为 $[1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1]$。

• $k=1$ 的时候，我们得到 $3$ 个不同的项链 $b$：$[1],[2],[3]$。
• $k=2$ 的时候，我们得到 $6$ 个不同的项链：$[1,1],[1,2],[2,2],[2,3],[3,3],[3,1]$。
• $k=3$ 的时候，我们得到 $5$ 个不同的项链：$[1,1,1],[2,2,2],[3,3,3],[1,2,3],[3,1,2]$。
• $k=4$ 的时候，我们得到 $5$ 个不同的项链：$[1,1,1,2],[2,2,3,3],[3,1,2,3],[3,1,2,2],[1,3,3,2]$。

【数据范围】

对于全部数据，$1\le n\le2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$。

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

提示

$1≤n≤2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$