Background

To repair the wound as soon as possible, the platelets are carrying coagulation factors. They (nothing wrong) are discussing how to distribute them. Since they are so cute, you are asked to solve this problem.

Problem Description

The platelets have two different types of containers. In the first type, each container can hold only one kind of coagulation factor. In the second type, in each container, each kind of coagulation factor can appear at most once. For convenience, the platelets want to use only one type of container to hold all coagulation factors.

In other words, partition $n$ positive integers $a_1$ ~ $a_n$ into some disjoint sets $S_1$ ~ $S_m$, satisfying one of the following two conditions:

1. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m]$, we have $a_i=a_j$.
2. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m],\ i\neq j$, we have $a_i\neq a_j$.

Since there are not many platelets, you need to put all coagulation factors into as few containers as possible. They want to know how to partition them so that the total number of containers is minimized.

Input Format

The first line contains a positive integer $n$, the number of coagulation factors.

The second line contains $n$ positive integers $a_i$, each representing the type of a coagulation factor.

Output Format

The first line contains two positive integers. The first is the minimum number of containers $m$, and the second is the type of container used ($1$ or $2$).

In the next $m$ lines, in each line, the first positive integer $c_i$ represents the number of coagulation factors in this container, followed by $c_i$ integers representing the type of each coagulation factor in this container.

Output any valid optimal solution. The output order does not matter.

7
1 2 3 5 4 4 4

3 2
1 4
5 3 1 2 4 5
1 4

3
20181110 20181111 20181111

2 1
1 20181110
2 20181111 20181111

3
20181110 20181111 20181111

2 2
2 20181110 20181111
1 20181111

5
3 2 3 2 3

2 1
3 3 3 3
2 2 2

Hint

Constraints: $1\le n\le 1000,\ \ 1\le a_i\le 10^9$。

Input Format

Output Format

Hint

Translated by ChatGPT 5