- All Contests
- ProjectEuler+
- Project Euler #158: Exploring strings

# Project Euler #158: Exploring strings

# 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**

```
3
```

**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 .