팽수와 버미는 크리스마스 트리를 꾸미기 시작했다.

긴 일자형 원통에 들어있는 크리스마스 장식품을 N개를 구매했다.

i번째 장식품은 a_i색상을 가지고 있으며, 일자형 원통은 양 끝이 열려 있어 왼쪽이나 오른쪽에서 장식품을 꺼낼 수 있다.

상자는 투명하기 때문에 팽수와 버미는 각 장식품의 색상을 알 수 있다.

위 그림은 두 번째 예제의 초기 상태를 보여준다. 첫 번째 행동으로, 팽수는 왼쪽에서 1번 색상을 꺼내거나 오른쪽에서 3번 색상을 꺼낼 수 있다.

팽수는 트리 꾸미기가 지루해져서 게임을 하기로 했다.

게임의 규칙은 팽수와 버미가 번갈아가며 행동하며, 팽수가 먼저 시작한다.

차례가 올 때마다 플레이어는 상자에서 장식품을 하나 뽑아서 트리에 올린다. (상자의 왼쪽이나 오른쪽에서 가져올 수 있음).

장식품의 색상이 아직 뽑힌 적이 없는 경우, 플레이어는 한 점을 획득한다. 게임은 상자에서 마지막 장식품이 뽑힐 때 종료된다.

게임의 승자는 더 많은 점수를 획득한 플레이어이므로 팽수와 버미 모두 최대한 많은 점수를 얻고 싶어한다.

둘 다 명문 남극 유치원 졸업생이기에 항상 최적으로 게임을 진행한다. 게임이 끝날 때 결과를 출력하라.

트리 꾸미기 timer 0.5s memory 512MB

트리 꾸미기 0.5s 512MB