조 편성

어떤 캠프에 N(1 ≤ N ≤ 1,000)명의 학생이 참가했다. 학생들은 열심히 공부하던 중 조별 수업을 하게 되었다. 조별 수업의 목적은 실력이 높은 학생과 낮은 학생을 같은 조에 배치해 서로 자극을 받도록 하는 것이다. 따라서 한 조 안의 실력 차이가 클수록 좋다.

하지만 같은 조에 속한 학생들의 나이 차이가 너무 크면 오히려 부정적인 효과가 생길 수 있다. 그래서 선생님들은 먼저 학생들을 나이순으로 정렬한 뒤, 이 순서를 유지한 채 연속한 구간들로 나누어 조를 만들기로 했다. 조의 개수에는 제한이 없다.

한 조의 잘 짜여진 정도는 그 조에 속한 학생들 중 최고 점수와 최저 점수의 차이이다. 전체 조 편성의 잘 짜여진 정도는 모든 조의 잘 짜여진 정도를 더한 값이다. 한 명만 있는 조는 최고 점수와 최저 점수가 같으므로 값이 0이다.

학생들의 점수가 나이순으로 주어졌을 때, 전체 조 편성의 잘 짜여진 정도로 얻을 수 있는 최댓값을 구하시오.

첫째 줄에 학생 수 N이 주어진다.

둘째 줄에 N명의 학생 점수가 나이순으로 주어진다. 각 점수는 0 이상 10,000 이하의 정수이다.

가능한 조 편성 중 잘 짜여진 정도의 합의 최댓값을 출력한다.