Same Songs

Time limit2sMemory limit512 MB

Summary

Remove songs from a fixed playlist so that the remaining list has the maximum number of adjacent equal pairs, and output one such list.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Implementation, Array
Solved: No attempts yet

Problem

Masha has a playlist of several songs in her music player. She listens to the songs in order. The playlist is not cyclic: when the last song ends, the player turns off. Masha likes repetitions, so she feels happy every time a song ends and the same one starts playing. When the same songs are separated by another one, Masha does not consider it a repetition.

The player has no option to add songs to the playlist or shuffle it. It can remove songs from the list. Your task is to remove some songs to maximize the number of repetitions. You may also remove everything or nothing from the list.

Input

The first line contains an integer $n$ : the number of songs in the playlist ( $1 \le n \le 50$ ). The second line contains $n$ space-separated numbers: the songs in the list. The songs are denoted by integer numbers from $1$ to $50$ .

Output

On the first line, print two space-separated numbers $m$ and $k$ : the number of songs in the edited playlist and the number of repetitions in it. On the second line, print the playlist: $m$ space-separated numbers.

If there are several possible answers, print any one of them. If the list is empty, you can either print or not print the second line, which would be empty.

Examples2

Example 1
Input
```
3
1 2 1
```
Expected output
```
2 1
1 1
```
Example 2
Input
```
7
2 1 2 1 3 2 5
```
Expected output
```
4 2
2 2 2 5
```