A subsequence can be derived from an array by removing zero or more elements without changing the order of the remaining elements. For example, , , , and are subsequences of array , while is not a subsequence of array .
A subsequence is microwavable if the subsequence consists of at most two distinct values and each element differs from its adjacent elements. For example, , , and are microwavable, while and are not microwavable.
Denote a function as the length of the longest microwavable subsequence of array such that each element within the subsequence is either or . Find the sum of for all .
输入格式
The first line consists of two integers ( ).
The second line consists of integers ( ).
输出格式
Output a single integer representing the sum of for all .
样例
样例输入 1
5 4
3 2 1 3 2
样例输出 1
13
样例输入 2
3 3
1 1 1
样例输出 2
2
数据范围与提示
Explanation for the sample input/output #1
The value of is , taken from the subsequence that can be obtained by removing and . The value of is , taken from the subsequence that can be obtained by removing and . The value of is , taken from the subsequence that can be obtained by removing . The value of , , and are all .
Explanation for the sample input/output #2
The value of and are both , while the value of is .
