이탈리아의 체세나티코(Cesenatico)는 아드리아해에 접해 있는 항구 도시로, 운하로 유명하다. 운하에는 배가 정박해 있으며 관광지로도 알려져 있다. 여기서 현실을 단순화한 다음과 같은 상황을 생각해 보자. 운하는 직선 형태이며, 한쪽 면만 아드리아해와 연결되어 있다. 운하에는 1부터 \(N\)까지 번호가 붙은 \(N\)척의 배가 정박해 있으며, 배 \(i\) (\(1 \le i \le N\))는 아드리아해에서 거리 \(A_i\) 떨어진 곳에 정박해 있다. 번호가 작은 배일수록 아드리아해에 가까이 정박해 있다. 즉 \(A_1 < A_2 < \cdots < A_N\)이 성립한다. 마을 축제를 위해 배에 색을 칠하기로 했다. 각 배마다 색 1부터 색 \(N\)까지 \(N\)가지 색 중 1가지를 골라 그 색으로 칠한다. 다음 조건을 만족하고 싶다.
배의 보기를 더 좋게 하기 위해 아래와 같이 아름다움을 정의한다.
배 정보가 주어졌을 때, 조건을 만족하는 칠하는 방법이 있는지 판별하고, 있으면 아름다움으로 가능한 최댓값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(A_3\) \(\cdots\) \(A_N\)
제약 조건
- \(2 \le N \le 3{,}500\)
- \(1 \le A_i \le 10^9\) (\(1 \le i \le N\))
- \(A_i < A_{i+1}\) (\(1 \le i \le N - 1\))
- 입력되는 값은 모두 정수이다.
부분문제
- (8점) \(A_i = i\) (\(1 \le i \le N\))
- (11점) \(N \le 7\)
- (12점) \(N \le 100\)
- (39점) \(N \le 700\)
- (30점) 추가 제약 조건 없음
다음 형식으로 출력한다.
조건을 만족하는 칠하는 방법이 없으면 -1을 출력한다. 있으면 아름다움으로 가능한 최댓값을 1줄에 출력한다.
예를 들어, 조건을 만족하지 않는 칠하는 방법으로는 배 1을 색 1로, 배 2를 색 2로 칠하는 것이 있다. 이 방법에서는 색 1로 칠한 배가 1척이므로 조건을 만족하지 않는다.
조건을 만족하는 칠하는 방법으로는 배 1과 배 2를 모두 색 2로 칠하는 것이 있다. 색 1로 칠한 배는 없으므로 색 1에 대한 조건을 만족한다. 색 2로 칠한 배의 거리를 오름차순으로 나열하면 \((1, 2)\)이며 등차수열이므로 색 2에 대한 조건도 만족한다.
이 방법에서 같은 색으로 칠한 2척은 배 1과 배 2뿐이며, 거리는 \(|A_1 - A_2| = |1 - 2| = 1\)이다. 따라서 아름다움은 1이다. 아름다움을 2 이상으로 만들 수 없으므로 1을 출력한다.
어떤 색이든 그 색으로 칠한 배 수를 1척이 아니게 하려면 배 1, 2, 3을 같은 색으로 칠해야 한다. 이때 그 색으로 칠한 배의 거리를 오름차순으로 나열하면 \((1, 10, 100)\)이며 등차수열이 아니다. 따라서 조건을 만족하는 칠하는 방법이 없으므로 -1을 출력한다.
예를 들어, 배 1·3·5를 색 1로, 배 2·4를 색 4로 칠하면 조건을 만족한다. 같은 색으로 칠한 2척 집은 배 1과 3, 배 1과 5, 배 2와 4, 배 3과 5의 4쌍이며, 거리는 각각 3, 6, 3, 3이다. 따라서 아름다움은 3이다. 아름다움을 4 이상으로 만들 수 없으므로 3을 출력한다.