60000 먼 카드 Silver V

문제

자연수가 적힌 카드 2N장이 일렬로 왼쪽에서 오른쪽으로 나열되어 있다. 각 카드에는 1 이상 N 이하의 자연수가 정확히 하나씩 적혀 있으며, 1부터 N까지의 각 자연수는 정확히 두 장의 카드에 적혀 있다.

자연수 k가 적힌 두 카드 사이에 놓인 카드의 개수를 “k 사이 카드 수”라고 정의한다.

카드 배열이 주어질 때, 모든 “k 사이 카드 수” 중 가장 큰 값을 구하시오.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 200,000)

둘째 줄에 2N개의 정수가 공백으로 구분되어 주어진다.

출력

모든 “k 사이 카드 수” 중 가장 큰 값을 출력한다.

4
1 2 2 4 3 1 3 4

4

4
1 2 3 4 4 3 2 1

6