Hide

# Problem GGear Wheels

Gear wheels can be connected to form chains, where the teeth of adjacent gears interlock. This helps to transmit rotary motion over a long distance.

Now, you have $N$ gear wheels arranged on a straight line, numbered from $1$ to $N$ from left to right. Gear wheel $i$ has $T_ i$ teeth.

If we connect gear wheel $i$ to gear wheel $j$, we can calculate the gear ratio as $T_ i / T_ j$ (or $T_ j / T_ i$). For the transmission to work perfectly, the gear ratio must be an integer.

You would like to form a longest chain of gear wheels such that the transmission between every pair of adjacent gear wheels works perfectly. Also, as moving the gears around is a lot of work, you are not allowed to reorder the gears on a chain. That is, if gear wheels $w_1, w_2, \ldots , w_ k$ are connected in this order from left to right, then $w_1 < w_2 < \ldots < w_ k$.

That is an easy task for you, so you would like to challenge yourself further. On top of finding one longest chain of gear wheels, you wish to find the maximum number of longest chains of gear wheels that can be formed, while each gear wheel can only be used in one chain.

## Input

The first line of input contains an integer $N$ $(1 \leq N \leq 1000)$, the number of gear wheels.

The next line contains $N$ integers $T_1, T_2, \ldots , T_ N$ $(1 \leq T_ i \leq 10^{18})$, the number of teeth on each gear wheel.

## Output

Output two integers $L$ and $C$ on the first line: the length of the longest chain of gear wheels that can be formed, and the maximum number of longest chains of gear wheels that can be formed.

Then, output $C$ lines, each containing $L$ integers. The $i$-th line should contain the indices of the gear wheels in the $i$-th longest chain of gear wheels, in increasing order.

If there are multiple valid answers, you may output any of them.

Sample Input 1 Sample Output 1
7
9 7 18 11 14 2 3

3 2
1 3 7
2 5 6

Sample Input 2 Sample Output 2
5
2 3 4 6 12

3 1
1 3 5

Hide