생각역

면접 대비

시간 제한1초메모리 제한256 MB

요약

1부터 N까지의 각 K에 대해 앞에서부터 K개씩 블록으로 나누고 남는 부분은 버린 뒤, 뒤집어서 같으면 같은 종류로 묶어 종류 수를 세고, 그 수가 최대가 되는 K를 모두 출력한다.

난이도: 보통10점 중 6점
유형: 문자열, 해시맵, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

생각역으로 열차 한 대가 들어오고 있다. 이 열차는 차량 $K$ 대를 이어 붙인 묶음을 여러 개 연결해서 만든다. 차량이 좌우 대칭이라 묶음을 뒤집어 연결해도 되므로, 어떤 묶음과 그 묶음을 뒤집은 것은 같은 종류로 본다.

지금은 열차의 머리부터 차량 $N$ 대까지만 보이고, 보이는 차량의 색상은 모두 알고 있다.

열차를 구경하던 사람이 $1$ 이상 $N$ 이하의 정수 $K$ 를 하나 정한 다음, 보이는 차량을 머리 쪽부터 $K$ 대씩 끊어 묶음으로 나눈다. 맨 뒤에 $K$ 대를 채우지 못한 차량이 남으면 버린다. 이렇게 얻은 묶음 중에서 뒤집으면 일치하는 것끼리 한 종류로 묶었을 때, 서로 다른 종류가 몇 개인지 센다.

서로 다른 종류의 개수가 가장 많아지는 $K$ 를 모두 구하라.

입력

첫째 줄에 보이는 차량의 수 $N$ 이 주어진다. ( $1 \le N \le 2000$ )

둘째 줄에 머리에서 가까운 순서대로 차량 $N$ 대의 색상이 공백으로 구분되어 주어진다. 색상은 $1$ 이상 $1000$ 이하의 정수이다.

출력

첫째 줄에 서로 다른 종류의 개수의 최댓값과 그 최댓값을 만드는 $K$ 의 개수를 공백으로 구분해 출력한다.

둘째 줄에 그 $K$ 를 오름차순으로 공백으로 구분해 출력한다.

예제3

예제 1
입력
```
10
1 1 2 2 1 1 2 2 1 1
```
예상 출력
```
2 3
1 2 3
```
예제 2
입력
```
1
5
```
예상 출력
```
1 1
1
```
예제 3
입력
```
6
1 2 3 3 2 1
```
예상 출력
```
3 1
1
```