0 이상 500 이하의 숫자들로 이루어진 수열이 있다.

이 수열들을 몇 개의 구간으로 적절히 나누어서 구간 값의 합을 최대로 하고 싶다. 이 문제에서는 구간이란 연속된 둘 이상의 숫자를 묶는 것이다.

다음 그림은 10 개의 숫자로 이루어진 수열을 4 개의 구간으로 나눈 예이다.

구간 값이란 어떤 구간에서의 최대값과 최소값을 뺀 것이다.

예를들어 , 네 번째 구간의 구간 값은 9-3 =6 이다.위의 방법으로 구간을 나누었을 때 구간 값의 합은 3+6+5+6 = 20 이다. 위의 수열에서는 이렇게 나누는 방법으로 최대 구간값의 합을 얻을 수 있다.

수열이 주어질 때, 이 수열을 몇 개의 구간으로 적절히 나눠 구간 값의 합을 최대로 하는 프로그램을 작성하시오.

입력 형식

• 첫 줄에는 수열의 길이 N( 2 <= N <=100)이 주어지고,
• 둘째 줄에는 수열을 이루는 N 개의 숫자(0 이상 500 이하)가 빈칸을 두고 주어진다.

출력형식

• 첫 줄에는 구한 구간 값의 합,
• 둘 째 줄에는 나눈 구간 값의 수,
• 셋 째 줄에는 그 구간들의 길이를 빈 칸을 사이에 두고 앞에서부터 차례대로 출력한다.

입출력 예

입력

10
2 5 7 1 3 4 8 6 9 3

출력

20
4
2 2 3 3