E. Executive's Holidays
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A company is in the process of designing a groundbreaking new game and has decided to hold several executive meetings to kick off the project.

Over the next $$$t$$$ days, the company needs to schedule $$$n$$$ executives to attend these meetings. On any given day, $$$i$$$, the company requires at least $$$a_i$$$ executives to be present.

Each executive's "satisfaction" is determined by the length of their longest continuous break from attending meetings. For instance, if an executive attends meetings on days $$$1$$$, $$$5$$$, and $$$7$$$ during a $$$7$$$-day period, their satisfaction value would be 3, representing the break they get from day $$$2$$$ to day $$$4$$$. If an executive does not attend any meetings during the entire period, their satisfaction value would be $$$t$$$.

You have been tasked by the CEO of the company to determine the maximum total satisfaction of all executives.

Input

The first line contains two integers $$$n,t$$$ $$$(1 \le n,t \le 2,000,000)$$$ denoting the number of executives in total and the number of days of meetings.

The second line contains $$$t$$$ integers $$$a_1, a_2,...,a_t$$$ $$$(0 \le a_i \le n)$$$ — the minimum number of executives required on the $$$i$$$-th day.

Output

Output the maximum sum of satisfaction of all the executives.

Examples
Input
3 7
0 1 1 3 2 0 1
Output
9
Input
10 10
6 1 2 5 5 0 7 3 4 2
Output
54
Note

In the first example, one way to arrange the meeting is as follows:

  • Executive $$$1$$$ attends the meeting on day $$$2$$$, $$$3$$$ and $$$4$$$, having the satisfaction value of $$$3$$$.
  • Executive $$$2$$$ attends the meeting on day $$$4$$$ and $$$5$$$, having the satisfaction value of $$$3$$$.
  • Executive $$$3$$$ attends the meeting on day $$$4$$$, $$$5$$$ and $$$7$$$, having the satisfaction value of $$$3$$$.
The total satisfaction is $$$3+3+3=9$$$.