난이도:정보올림피아드

문제: 순간이동 포탈의 최대 거리

컴돌이 연구소에는 번호가 적힌 포탈 장치가 총 2N개 놓여 있다.

각 포탈에는 1 이상 N 이하의 번호가 하나 적혀 있으며,
같은 번호가 적힌 포탈은 정확히 두 개씩 존재한다.

포탈들은 일렬로 배치되어 있고, 왼쪽에서부터 차례로 번호가 주어진다.

같은 번호의 두 포탈은 서로 연결되어 있으며,
한 포탈에서 다른 포탈로 순간이동할 수 있다.

컴돌이는 어떤 번호 k에 대해,
번호 k의 두 포탈 사이를 이동할 때 지나쳐야 하는 포탈의 개수를
"k의 이동 거리"라고 부르기로 했다.

즉,

  • 두 포탈이 바로 붙어 있으면 이동 거리는 0

  • 사이에 포탈이 3개 있으면 이동 거리는 3

이다.

컴돌이는 모든 번호의 이동 거리 중 가장 큰 값을 구하려고 한다.

포탈들의 번호가 순서대로 주어질 때,
가장 긴 이동 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다.

둘째 줄에 길이 2N의 수열이 주어진다.

  • 수열의 각 값은 1 이상 N 이하이다.

  • 각 숫자는 정확히 두 번 등장한다.

출력

모든 번호의 이동 거리 중 최댓값을 출력한다.

제한

  • 1 ≤ N ≤ 2000

예제 입력 1

4
1 2 2 4 3 1 3 4

예제 출력 1

4

예제 입력 2

4
1 2 3 4 4 3 2 1

예제 출력 2

6

추가 설명

두 번째 예제에서:

  • 1의 두 위치 사이에는 6개의 포탈이 있다.

  • 2의 두 위치 사이에는 4개의 포탈이 있다.

  • 3의 두 위치 사이에는 2개의 포탈이 있다.

  • 4의 두 위치는 붙어 있으므로 0개이다.

따라서 정답은 6이다.