There are $N$ students standing in a line. Each student has his own intelligence level which is denoted by the array $A$ where $A[i]$ denotes the intelligence level of the $i^{th}$  student in the line. Now the teacher wants to distribute students in $K$ groups. Each group should be formed from adjacent standing students only.

The beauty of a group is defined by the fact that if there is a person with intelligence level $A[i]$ then if there are students of less intelligence level that are in the same group standing after the student $i$, the beauty increases by count of such pairs of students. In simple words, the beauty of the group is the total number of pairs of students in that group such that $i \lt j$ and $A[i] \gt A[j]$. 

Now the teacher is worried about the sum of the beauty of all the groups that she forms. You being the most intelligent student has to suggest a plan such that if students are divided in that way, the sum of the beauty of all groups is maximized. You need to print this maximum value which can be obtained.

Input
The first line of input contains two space-separated integers $N$ and $K$. The next line of input contains $N$ space separated integers that denote intelligence level of the $i^{th}$ student.

Output
In the output print the maximum beauty sum that can be obtained over all possible ways to distribute the students into $K$ groups.

Constraints
$1 \le N \le 500$
$1 \le K \le N$
$1 \le A[i] \le 10^5$