Team Formation

N (1 ≤ N ≤ 1,000) students are attending a camp. During their studies, the teachers decide to hold team-based classes. The goal is to place students with high scores and students with low scores in the same team so they can motivate one another. Therefore, a larger score difference inside a team is better.

However, if the age gap inside a team is too large, the team may have a negative effect instead. The teachers first sort the students by age, then split this ordered list into contiguous groups. The number of teams is unrestricted.

The quality of one team is the difference between the highest score and the lowest score among the students in that team. The total quality of a formation is the sum of the qualities of all teams. A team with only one student has quality 0 because its highest and lowest scores are the same.

Given the students' scores in age order, find the maximum possible total quality.

The first line contains the number of students N.

The second line contains the scores of the N students in age order. Each score is an integer between 0 and 10,000, inclusive.

Print the maximum possible sum of team qualities over all valid team formations.