Farmer John의 농장에는 1번부터 N번까지 번호가 매겨진 소들이 있으며, N는 2 이상 200,000 이하입니다. 선거를 통해 농장의 두 명의 새로운 우두머리 소를 결정하려고 합니다. 처음에, 소 i는 소 a_i에게 투표할 예정입니다 (1 ≤ a_i ≤ N).

두 명의 우두머리 소를 결정하는 절차는 다음과 같습니다.

농부 John은 소들 중 일부(전체가 아니며, 적어도 한 마리는 포함되는)를 임의로 선택하여 집합 S를 만듭니다.
집합 S에 속한 소들이 던진 표를 보고, 가장 많이 나온 표를 받은 소를 첫 번째 우두머리 소로 선택할 수 있습니다.
전체 소 중 S에 속하지 않은 소들의 표를 보고, 가장 많이 나온 표를 받은 소를 두 번째 우두머리 소로 선택할 수 있습니다.

단, 두 번 선택된 우두머리 소가 서로 다른 소여야 합니다. (만약 두 우두머리 소가 같다면, 다양도는 0으로 간주합니다.) 두 우두머리 소 x와 y의 다양도는 |x - y|로 정의됩니다. Farmer John은 리더들의 숫자가 너무 비슷하면 마음에 들지 않으므로, 다양도가 최대가 되도록 집합 S를 선택하려 합니다.

이때, 주어진 투표 정보를 바탕으로 다양한 집합 S 중에서 만들어질 수 있는 최대 다양도를 구하는 문제입니다.

#8419 upload 2 done 1 how_to_reg 1

Election Queries timer 3s memory 1024MB

#8419

Election Queries 3s 1024MB