시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 94 33 20 33.333%

문제

러시아 전통 목제인형인 마트료시카는 그 안에 크기가 계속 작아지는 인형들이 들어있는 인형이다. 마트료시카를 열면 그 안에 더 작은 인형이 있고, 그 작은 인형의 안엔 또다시 작은 인형이 들어있고, 안에 더는 인형이 없을 때까지 계속 반복된다. 

최근 러시아 마트료시카 박물관은 개수만 다르고 비슷하게 생긴 마트료시카 세트들을 모아놓은 콜렉션을 전시했다. 그런데 그만부모의 통제에서 벗어난 난폭한 어린이들이 이 세트들을 모두 분리시켜 일렬로 세워버렸다. 박물관 알바생인 준빈이는 해고 당하지 않기 위해 어린이들이 일렬로 세워놓은 총 n개의 마트료시카를(인형들의 크기는 정수로 나타낼 수 있다고 가정하자), 원래 마트료시카 세트들이 몇 개였는지 세트별로 몇 개였는지 모르는 채로, 마트료시카 세트들로 재조립 해야 한다. 확실한 것은 모든 완전한 마트료시카 세트의 인형들의 크기들은 각각 크기가 1부터 어떤 수 m까지의 연속된 정수라는 것이다. 물론 m은 각 세트마다 다르다.

재조립 과정에서 준빈이는 다음의 규칙을 따라야한다.

  • 작은 인형 안에는 큰 인형이 들어갈 수 없다.
  • 두 그룹(부분적으로 재조립이 완료된 그룹)의 인형들을 합치려면 그 두 그룹이 (줄에서)서로 인접해 있어야 한다.
  • 인형이 한 번 그룹에 들어가면 다른 그룹과 합치는 작업을 할 때 외에는, 절대로 다른 그룹으로 옮기거나 아예 분리될 수 없다.

오래 걸리면 걸릴 수록 시급에서 까인다. 따라서 최대한 빨리 이 일을 마쳐야 한다. 복구할 때 인형을 열고 닫는 시간만 고려하자. 따라서 여는 횟수를 최소화하면 된다.  예를 들어보자. 그룹 [1, 2, 6]과 [4]를 합칠 때 여는 횟수의 최솟값은 2이다. 크기 6인 인형과 4인 인형을 열어야 하기 때문이다. 그룹 [1, 2, 5]와 [3, 4]를 합칠 때는 최소 횟수가 3이다.

분해된 마트료시카 세트들을 다시 합치는데 인형들을 최소 몇 번 열어야하는지 계산하자.

입력

첫 번째 줄에는 일렬로 세워진 각 마트료시카 인형들의 개수 n(1 ≤ n ≤ 500)이 주어진다. 두 번째 줄에는 각 마트료시카 인형의 크기(1 ≤ 크기 ≤ 500)가 줄에 세워진 순서대로 주어진다.

출력

마트료시카 세트들을 복구하기 위해 인형들을 여는 횟수의 최솟값을 출력한다. 만약 재조립이 불가능하다면(아이들이 훔쳤을 수도 있다) "impossible"을 출력한다.

예제 입력 1

7
1 2 3 2 4 1 3

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6Ijg4ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWQyYjhcdWI4Y2NcdWMyZGNcdWNlNzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjdlY1x1YzJkY1x1YzU0NCBcdWM4MDRcdWQxYjUgXHViYWE5XHVjODFjXHVjNzc4XHVkNjE1XHVjNzc4IFx1YjljOFx1ZDJiOFx1YjhjY1x1YzJkY1x1Y2U3NFx1YjI5NCBcdWFkZjggXHVjNTQ4XHVjNWQwIFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjYzRcdWMxOGQgXHVjNzkxXHVjNTQ0XHVjOWMwXHViMjk0IFx1Yzc3OFx1ZDYxNVx1YjRlNFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNzc4XHVkNjE1XHVjNzc0XHViMmU0LiZuYnNwO1x1YjljOFx1ZDJiOFx1YjhjY1x1YzJkY1x1Y2U3NFx1Yjk3YyBcdWM1ZjRcdWJhNzQgXHVhZGY4IFx1YzU0OFx1YzVkMCBcdWIzNTQgXHVjNzkxXHVjNzQwIFx1Yzc3OFx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWRmOCBcdWM3OTFcdWM3NDAgXHVjNzc4XHVkNjE1XHVjNzU4IFx1YzU0OFx1YzVkNCBcdWI2MTBcdWIyZTRcdWMyZGMgXHVjNzkxXHVjNzQwIFx1Yzc3OFx1ZDYxNVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWFjZTAsIFx1YzU0OFx1YzVkMCBcdWIzNTRcdWIyOTQgXHVjNzc4XHVkNjE1XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAmbmJzcDtcdWFjYzRcdWMxOGQgXHViYzE4XHViY2Y1XHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL01hdHJ5b3Noa2EucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIwMHB4OyB3aWR0aDoyNjFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmMmbmJzcDtcdWI3ZWNcdWMyZGNcdWM1NDQgXHViOWM4XHVkMmI4XHViOGNjXHVjMmRjXHVjZTc0IFx1YmMxNVx1YmIzY1x1YWQwMFx1Yzc0MCBcdWFjMWNcdWMyMThcdWI5Y2MgXHViMmU0XHViOTc0XHVhY2UwJm5ic3A7XHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjIFx1YzBkZFx1YWUzNCBcdWI5YzhcdWQyYjhcdWI4Y2NcdWMyZGNcdWNlNzQgXHVjMTM4XHVkMmI4XHViNGU0XHVjNzQ0IFx1YmFhOFx1YzU0NFx1YjE5M1x1Yzc0MCBcdWNmNWNcdWI4MDlcdWMxNThcdWM3NDQgXHVjODA0XHVjMmRjXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhZGY4XHViOWNjXHViZDgwXHViYWE4XHVjNzU4IFx1ZDFiNVx1YzgxY1x1YzVkMFx1YzExYyBcdWJjOTdcdWM1YjRcdWIwOWMgXHViMDljXHVkM2VkXHVkNTVjJm5ic3A7XHVjNWI0XHViOWIwXHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc3NCBcdWMxMzhcdWQyYjhcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YmQ4NFx1YjlhY1x1YzJkY1x1Y2YxYyBcdWM3N2NcdWI4MmNcdWI4NWMgXHVjMTM4XHVjNmNjXHViYzg0XHViODM4XHViMmU0LiBcdWJjMTVcdWJiM2NcdWFkMDAgXHVjNTRjXHViYzE0XHVjMGRkXHVjNzc4IFx1YzkwMFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWQ1NzRcdWFjZTAgXHViMmY5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNWI0XHViOWIwXHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWMxMzhcdWM2Y2NcdWIxOTNcdWM3NDAmbmJzcDtcdWNkMWQgblx1YWMxY1x1Yzc1OCBcdWI5YzhcdWQyYjhcdWI4Y2NcdWMyZGNcdWNlNzRcdWI5N2MoXHVjNzc4XHVkNjE1XHViNGU0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwKSwgXHVjNmQwXHViNzk4Jm5ic3A7XHViOWM4XHVkMmI4XHViOGNjXHVjMmRjXHVjZTc0IFx1YzEzOFx1ZDJiOFx1YjRlNFx1Yzc3NCBcdWJhODcgXHVhYzFjXHVjNjAwXHViMjk0XHVjOWMwIFx1YzEzOFx1ZDJiOFx1YmNjNFx1Yjg1YyBcdWJhODcgXHVhYzFjXHVjNjAwXHViMjk0XHVjOWMwIFx1YmFhOFx1Yjk3NFx1YjI5NCZuYnNwO1x1Y2M0NFx1Yjg1YywgXHViOWM4XHVkMmI4XHViOGNjXHVjMmRjXHVjZTc0IFx1YzEzOFx1ZDJiOFx1YjRlNFx1Yjg1YyBcdWM3YWNcdWM4NzBcdWI5YmQgXHVkNTc0XHVjNTdjJm5ic3A7XHVkNTVjXHViMmU0LiBcdWQ2NTVcdWMyZTRcdWQ1NWMgXHVhYzgzXHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM2NDRcdWM4MDRcdWQ1NWMgXHViOWM4XHVkMmI4XHViOGNjXHVjMmRjXHVjZTc0IFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWM3NzhcdWQ2MTVcdWI0ZTRcdWM3NTggXHVkMDZjXHVhZTMwXHViNGU0XHVjNzQwJm5ic3A7XHVhYzAxXHVhYzAxJm5ic3A7XHVkMDZjXHVhZTMwXHVhYzAwIDFcdWJkODBcdWQxMzAgXHVjNWI0XHViNWE0IFx1YzIxOCBtXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWM4MTVcdWMyMThcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiM2NcdWI4NjAgbVx1Yzc0MCBcdWFjMDEgXHVjMTM4XHVkMmI4XHViOWM4XHViMmU0IFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVjODcwXHViOWJkIFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWM5MDBcdWJlNDhcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI1MzBcdWI3N2NcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzkxXHVjNzQwIFx1Yzc3OFx1ZDYxNSZuYnNwO1x1YzU0OFx1YzVkMFx1YjI5NCBcdWQwNzAgXHVjNzc4XHVkNjE1XHVjNzc0IFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHVhZGY4XHViOGY5KFx1YmQ4MFx1YmQ4NFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM3YWNcdWM4NzBcdWI5YmRcdWM3NzQgXHVjNjQ0XHViOGNjXHViNDFjIFx1YWRmOFx1YjhmOSlcdWM3NTggXHVjNzc4XHVkNjE1XHViNGU0XHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YjgyNFx1YmE3NCBcdWFkZjggXHViNDUwIFx1YWRmOFx1YjhmOVx1Yzc3NCAoXHVjOTA0XHVjNWQwXHVjMTFjKVx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc4XHVkNjE1XHVjNzc0IFx1ZDU1YyBcdWJjODggXHVhZGY4XHViOGY5XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YmE3NCBcdWIyZTRcdWI5NzggXHVhZGY4XHViOGY5XHVhY2ZjIFx1ZDU2OVx1Y2U1OFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTYwIFx1YjU0YyBcdWM2NzhcdWM1ZDBcdWIyOTQsIFx1YzgwOFx1YjMwMFx1Yjg1YyBcdWIyZTRcdWI5NzggXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YzYyZVx1YWUzMFx1YWM3MFx1YjA5OCBcdWM1NDRcdWM2MDggXHViZDg0XHViOWFjXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjI0XHViNzk4IFx1YWM3OFx1YjlhY1x1YmE3NCBcdWFjNzhcdWI5YjQgXHVjMjE4XHViODVkIFx1YzJkY1x1YWUwOVx1YzVkMFx1YzExYyBcdWFlNGNcdWM3NzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHViOWM4XHVjY2QwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViY2Y1XHVhZDZjXHVkNTYwIFx1YjU0YyBcdWM3NzhcdWQ2MTVcdWM3NDQgXHVjNWY0XHVhY2UwIFx1YjJlYlx1YjI5NCBcdWMyZGNcdWFjMDRcdWI5Y2MgXHVhY2UwXHViODI0XHVkNTU4XHVjNzkwLiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNWVjXHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiAmbmJzcDtcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0XHViY2Y0XHVjNzkwLiBcdWFkZjhcdWI4ZjkgWzEsIDIsIDZdXHVhY2ZjIFs0XVx1Yjk3YyBcdWQ1NjlcdWNlNjAgXHViNTRjIFx1YzVlY1x1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQwJm5ic3A7Mlx1Yzc3NFx1YjJlNC4gXHVkMDZjXHVhZTMwIDZcdWM3NzggXHVjNzc4XHVkNjE1XHVhY2ZjIDRcdWM3NzggXHVjNzc4XHVkNjE1XHVjNzQ0IFx1YzVmNFx1YzViNFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWFkZjhcdWI4ZjkgWzEsIDIsIDVdXHVjNjQwIFszLCA0XVx1Yjk3YyBcdWQ1NjlcdWNlNjAgXHViNTRjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWFjMDAgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDg0XHVkNTc0XHViNDFjIFx1YjljOFx1ZDJiOFx1YjhjY1x1YzJkY1x1Y2U3NCBcdWMxMzhcdWQyYjhcdWI0ZTRcdWM3NDQgXHViMmU0XHVjMmRjIFx1ZDU2OVx1Y2U1OFx1YjI5NFx1YjM3MCBcdWM3NzhcdWQ2MTVcdWI0ZTRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVjNWY0XHVjNWI0XHVjNTdjXHVkNTU4XHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHVjNzdjXHViODJjXHViODVjIFx1YzEzOFx1YzZjY1x1YzljNCZuYnNwO1x1YWMwMSBcdWI5YzhcdWQyYjhcdWI4Y2NcdWMyZGNcdWNlNzQgXHVjNzc4XHVkNjE1XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOCBuKDEgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjljOFx1ZDJiOFx1YjhjY1x1YzJkY1x1Y2U3NCBcdWM3NzhcdWQ2MTVcdWM3NTggXHVkMDZjXHVhZTMwKDEgJmxlOyBcdWQwNmNcdWFlMzAgJmxlOyA1MDApXHVhYzAwIFx1YzkwNFx1YzVkMCBcdWMxMzhcdWM2Y2NcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5YzhcdWQyYjhcdWI4Y2NcdWMyZGNcdWNlNzQgXHVjMTM4XHVkMmI4XHViNGU0XHVjNzQ0IFx1YmNmNVx1YWQ2Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzc4XHVkNjE1XHViNGU0XHVjNzQ0IFx1YzVlY1x1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzdhY1x1Yzg3MFx1YjliZFx1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQoXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzc0IFx1ZDZkNFx1Y2NlNFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KSAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4ODg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiXHUwNDNjXHUwNDMwXHUwNDQyXHUwNDQwXHUwNDUxXHUwNDQ4XHUwNDNhXHUwNDMwIiwiZGVzY3JpcHRpb24iOiI8cD5NYXRyeW9zaGthcyBhcmUgc2V0cyBvZiB0cmFkaXRpb25hbCBSdXNzaWFuIHdvb2RlbiBkb2xscyBvZiBkZWNyZWFzaW5nIHNpemUgcGxhY2VkIG9uZSBpbnNpZGUgdGhlIG90aGVyLiBBIG1hdHJ5b3Noa2EgZG9sbCBjYW4gYmUgb3BlbmVkIHRvIHJldmVhbCBhIHNtYWxsZXIgXHVmYjAxZ3VyZSBvZiB0aGUgc2FtZSBzb3J0IGluc2lkZSwgd2hpY2ggaGFzLCBpbiB0dXJuLCBhbm90aGVyIFx1ZmIwMWd1cmUgaW5zaWRlLCBhbmQgc28gb24uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvTWF0cnlvc2hrYS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjAwcHg7IHdpZHRoOjI2MXB4XCIgXC8+VGhlIFJ1c3NpYW4gTWF0cnlvc2hrYSBNdXNldW0gcmVjZW50bHkgZXhoaWJpdGVkIGEgY29sbGVjdGlvbiBvZiBzaW1pbGFybHkgZGVzaWduZWQgbWF0cnlvc2hrYSBzZXRzLCBkaWZmZXJpbmcgb25seSBpbiB0aGUgbnVtYmVyIG9mIG5lc3RlZCBkb2xscyBpbiBlYWNoIHNldC4gVW5mb3J0dW5hdGVseSwgc29tZSBvdmVyLXplYWxvdXMgKGFuZCBvYnZpb3VzbHkgdW5zdXBlcnZpc2VkKSBjaGlsZHJlbiBzZXBhcmF0ZWQgdGhlc2Ugc2V0cywgcGxhY2luZyBhbGwgdGhlIGluZGl2aWR1YWwgZG9sbHMgaW4gYSByb3cuIFRoZXJlIGFyZSBuIGRvbGxzIGluIHRoZSByb3csIGVhY2ggd2l0aCBhbiBpbnRlZ2VyIHNpemUuIFlvdSBuZWVkIHRvIHJlYXNzZW1ibGUgdGhlIG1hdHJ5b3Noa2Egc2V0cywga25vd2luZyBuZWl0aGVyIHRoZSBudW1iZXIgb2Ygc2V0cyBub3IgdGhlIG51bWJlciBvZiBkb2xscyBpbiBlYWNoIHNldC4gWW91IGtub3cgb25seSB0aGF0IGV2ZXJ5IGNvbXBsZXRlIHNldCBjb25zaXN0cyBvZiBkb2xscyB3aXRoIGNvbnNlY3V0aXZlIHNpemVzIGZyb20gMSB0byBzb21lIG51bWJlciBtLCB3aGljaCBtYXkgdmFyeSBiZXR3ZWVuIHRoZSBkaWZmZXJlbnQgc2V0cy48XC9wPlxyXG5cclxuPHA+V2hlbiByZWFzc2VtYmxpbmcgdGhlIHNldHMsIHlvdSBtdXN0IGZvbGxvdyB0aGVzZSBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Zb3UgY2FuIHB1dCBhIGRvbGwgb3IgYSBuZXN0ZWQgZ3JvdXAgb2YgZG9sbHMgb25seSBpbnNpZGUgYSBsYXJnZXIgZG9sbC48XC9saT5cclxuXHQ8bGk+WW91IGNhbiBjb21iaW5lIHR3byBncm91cHMgb2YgZG9sbHMgb25seSBpZiB0aGV5IGFyZSBhZGphY2VudCBpbiB0aGUgcm93LjxcL2xpPlxyXG5cdDxsaT5PbmNlIGEgZG9sbCBiZWNvbWVzIGEgbWVtYmVyIG9mIGEgZ3JvdXAsIGl0IGNhbm5vdCBiZSB0cmFuc2ZlcnJlZCB0byBhbm90aGVyIGdyb3VwIG9yIHBlcm1hbmVudGx5IHNlcGFyYXRlZCBmcm9tIHRoZSBncm91cC4gSXQgY2FuIGJlIHRlbXBvcmFyaWx5IHNlcGFyYXRlZCBvbmx5IHdoZW4gY29tYmluaW5nIHR3byBncm91cHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciB0aW1lIGlzIHZhbHVhYmxlLCBhbmQgeW91IHdhbnQgdG8gZG8gdGhpcyByZWFzc2VtYmx5IHByb2Nlc3MgYXMgcXVpY2tseSBhcyBwb3NzaWJsZS4gVGhlIG9ubHkgdGltZS1jb25zdW1pbmcgcGFydCBvZiB0aGlzIHRhc2sgaXMgb3BlbmluZyBhbmQgc3Vic2VxdWVudGx5IGNsb3NpbmcgYSBkb2xsLCBzbyB5b3Ugd2FudCB0byBtaW5pbWl6ZSBob3cgb2Z0ZW4geW91IGRvIHRoaXMuIEZvciBleGFtcGxlLCB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlbmluZ3MgKGFuZCBzdWJzZXF1ZW50IGNsb3NpbmdzKSB3aGVuIGNvbWJpbmluZyBncm91cCBbMSwgMiwgNl0gd2l0aCB0aGUgZ3JvdXAgWzRdIGlzIHR3bywgc2luY2UgeW91IGhhdmUgdG8gb3BlbiB0aGUgZG9sbHMgd2l0aCBzaXplcyA2IGFuZCA0LiBXaGVuIGNvbWJpbmluZyBncm91cCBbMSwgMiwgNV0gd2l0aCB0aGUgZ3JvdXAgWzMsIDRdLCB5b3UgbmVlZCB0byBwZXJmb3JtIHRocmVlIG9wZW5pbmdzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVuaW5ncyByZXF1aXJlZCB0byBjb21iaW5lIGFsbCBkaXNhc3NlbWJsZWQgbWF0cnlvc2hrYSBzZXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIHRlc3QgY2FzZS4gQSB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyA1MDApIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGluZGl2aWR1YWwgZG9sbHMgaW4gdGhlIHJvdy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gcG9zaXRpdmUgaW50ZWdlcnMgc3BlY2lmeWluZyB0aGUgc2l6ZXMgb2YgdGhlIGRvbGxzIGluIHRoZSBvcmRlciB0aGV5IGFwcGVhciBpbiB0aGUgcm93LiBFYWNoIHNpemUgaXMgYmV0d2VlbiAxIGFuZCA1MDAgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkRpc3BsYXkgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZW5pbmdzIHJlcXVpcmVkIHdoZW4gcmVhc3NlbWJsaW5nIHRoZSBtYXRyeW9zaGthIHNldHMuIElmIHJlYXNzZW1ibGluZyBjYW5ub3QgYmUgZG9uZSAoc29tZSBvZiB0aGUga2lkcyBtaWdodCBoYXZlIGJlZW4gZXhjZXNzaXZlbHkgemVhbG91cyBhbmQgdGFrZW4gc29tZSBkb2xscyksIGRpc3BsYXkgdGhlIHdvcmQgaW1wb3NzaWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > World Finals > 2013 World Finals H번