매달린 둥지

튜링 제비갈매기(The Turing Tern)는 새로 발견된 새 종으로, 행동 패턴이 매우 규칙적인 것으로 알려져 있다. 무리의 각 구성원은 날개에 있는 색깔 점의 개수로 구별할 수 있다. 같은 점 개수를 가진 구성원은 없다.

무리가 새로운 지역으로 이동하면, 높은 나무를 찾아 가장 높은 가지 아래쪽에 갈고리 모양의 구조물을 만든다. 이어서 각 구성원이 자신의 둥지를 짓는다. 모든 둥지는 갈고리에 매달린다. 각 둥지의 아래쪽에는 최대 두 개의 갈고리가 있다. 하나는 맨 왼쪽, 다른 하나는 맨 오른쪽에 있다.

둥지는 다음 규칙에 따라 만든다.

1. 새들은 도착한 순서대로 둥지를 짓는다.
2. 모든 둥지는 다른 둥지의 갈고리나 갈고리 모양의 가지 중 정확히 하나에 매달린다. 한 갈고리에는 둥지를 최대 하나만 매달 수 있다.
3. 각 새는 먼저 원래의 갈고리 모양 가지에 둥지를 매달려고 한다. 그 갈고리가 사용 중이면 4번 규칙을 따른다.
4. 새가 사용하려는 갈고리에 이미 둥지가 매달려 있으면, 새는 자신의 점 개수와 그 둥지 주인의 점 개수를 비교한다. 점이 더 적으면 그 둥지의 왼쪽 갈고리를 시도하고, 그렇지 않으면 오른쪽 갈고리를 시도한다. 빈 갈고리를 찾을 때까지 이 과정을 반복한다.

둥지의 행거는 갈고리로 이어진 둥지들의 연속이다. 행거는 그 둥지에서 시작해 한 단계씩 아래로 내려가며(옆으로는 가지 않는다), 마지막 단계의 둥지에 도달하면 끝난다. 행거의 길이는 행거에 포함된 둥지의 개수이다.

둥지의 높이는 가장 긴 행거의 길이이다. 둥지의 불안정 지수는 왼쪽 갈고리에 있는 둥지의 높이와 오른쪽 갈고리에 있는 둥지의 높이 차이의 절댓값이다. 빈 갈고리는 높이가 0인 빈 둥지로 본다.

무리의 설명이 주어지면, 불안정 지수가 가장 큰 둥지에 사는 새의 점 개수를 출력한다. 같은 값이 여럿이면 가장 먼저 도착한 새를 출력한다.

첫 줄에는 무리의 개수를 나타내는 양의 정수 n이 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 무리의 새 수 f (1 ≤ f ≤ 5000)가 주어진다. 다음 줄에는 도착한 순서대로 각 새의 점 개수를 나타내는 양의 정수 f개가 주어진다. 두 새가 같은 점 개수를 가지지 않는다고 가정해도 된다. 각 새의 점 개수는 1개 이상 5000개 이하이다.

각 테스트 케이스마다 Flock #k: p 형식으로 한 줄을 출력한다. k는 무리 번호이고, p는 가장 불균형한 둥지에 사는 새의 점 개수이다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 한 줄 출력한다.