수열이 주어져 있을 때, 이 수열을 몇 개의 구간으로 나누어서 "구간 값"의 합을 최대로 하고 싶습니다.

구간 값 이란, 특정 구간의 최댓값과 최솟값의 차이를 의미합니다.
만약 한 구간의 숫자가 (3, 4, 9) 이였으면 최댓값은 9, 최솟값은 3이므로 구간 값은 6이 됩니다.

위와 같은 수열이 주어 지고, (2, 5), (7, 1), (3, 4, 8), (6, 9, 3) 으로 구간이 나뉘어 있을 때,
구간 값들은 3, 6, 5, 6 으로, 그 합은 20이 됩니다.

수열이 주어졌을 때, 이 수열을 몇 개의 구간으로 적절히 나누어 구간 값의 합을 최대로 하는 프로그램을 작성 해 주세요. 단, 한개의 구간은 적어도 2개 이상의 숫자로 이루어져 있어야 하며 수열 상에서 연속되어 있어야 합니다.

첫 줄에는 수열의 길이 N (2 <= N <= 100)이 주어집니다.
둘째 줄에는 수열을 이루는 N개의 숫자 M (0 <= M <= 500)이 주어집니다.

구간 값 합의 최댓값을 출력 해 주세요.