두 명이서 교대로 수열의 양쪽 끝을 선택하는 게임을 한다.

첫 번째 플레이어는 이길 수 있는 최선의 선택을 하고 , 두 번째 플레이어는 양쪽 끝 수 중 무조건 큰 수를 선택하면서 게임을 진행한다.( 만약 양끝 수가 같으면 왼쪽 끝 수를 선택한다.)

이렇게 게임을 마친 경우 첫 번째 플레이어와 두 번째 플레이어와 의 점수 차를 구하는 것이 문제이다.

입력

출력

입출력 예

입력

4 
3 2 10 4

출력

the greedy strategy might lose by as many as 7 points.

입출력 보충

• player1 왼쪽 끝 3 를 가져 감(3) ... 2 10 4
• player2 오른쪽 끝 4 를 가져 감(4) ... 2 10
• player1 오른쪽 10 을 가져감(3+10) ... 2
• player2 2 를 가져감(4+2)

출처:East Central North America 2005