Project Euler #158: Exploring strings

_{This problem is a programming version of Problem 158 from projecteuler.net}

Taking three different letters from the letters of the alphabet, character strings of length three can be formed.

Examples are abc, hat and zyx.

When we study these three examples we see that for abc two characters come lexicographically after its neighbour to the left.

For hat there is exactly one character that comes lexicographically after its neighbour to the left. For zyx there are zero characters that come lexicographically after its neighbour to the left.

In all there are strings of length for which exactly one character comes lexicographically after its neighbour to the left.

We now consider strings of different characters from some foreign alphabet consisting of characters. For every , is the number of strings of length for which exactly characters come lexicographically after their neighbour to the left.

For what is the maximum value of ?

Input Format

The first line of each test contains two integers: and which is the size of alphabet and the number of queries.
On the next line there are different numbers separated by single spaces given by .

Constraints

Output Format

Output one number i.e. .

Sample Input

2 2
0 1

Sample Output

Explanation

Let's assume our alphabet contains only letters 'A' and 'B'. Then we have the following values for :

(both words "A" and "B")
(word "BA")
(word "AB")

We now see that the maximum for is and the maximum for is .