A new student dorm has been opened! It consists of
Each time a new student moves in a building, a big party is being held inside that building. The noise of the party is equal to the number of students located inside the building. The dorm management is not particularly fond of noise, so they will occasionally empty a certain building to keep the parties at a reasonable noise level. They do this by moving all its residents to a completely different student dorm. The management can decide to do this after any day, but they realized that it doesn't pay off to do it more than
Help the management! Knowing which buildings are being moved in by students, determine the minimal possible total noise level (the sum of noise levels of all
Input Specification
The first line of input contains the integers
The
Output Specification
The first and only line of output must contain the required minimal possible total noise level.
Scoring
In test cases worth 40 points,
In test cases worth 60 points, it will hold
In test cases worth 80 points, it will hold
Sample Input 1
5 1 2
1
1
1
1
1
Sample Output 1
7
Explanation of Output for Sample Input 1
The building is emptied after the first and the third day so the noise levels are, respectively, 1, 1, 2, 1, 2.
Sample Input 2
11 2 3
1
2
1
2
1
2
1
2
1
2
1
Sample Output 2
18
Explanation of Output for Sample Input 2
For example, building 1 is emptied after the fourth and eighth day and building 2 after the sixth day. The noise levels are, respectively, 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2.
Comments