Why Work?

준성 is unwilling to work and only wants a quick score, so he starts analyzing the prices of $N$ cryptocurrencies! Here is what he found. $P_i$ is the price of the $i$-th cryptocurrency.

1. $P_i$ is either 1 or 2.
2. $P_1$ changes every day. That is, if $P_1$ is 1, it becomes 2, and if it is 2, it becomes 1.
3. $P_{i+1}$ changes every day if $P_1, P_2, \dots, P_i$ were all 2 yesterday. Otherwise, it does not change. $(1 \leq i \leq N-1)$
4. Apart from the conditions above, $P_i$ never changes, and each cryptocurrency has an unlimited supply.

Because a huge investor could enter the market and make the analysis useless,준성 trades only one unit of each cryptocurrency per day, either buying or selling.

Junseong is diligent, so he starts trading as soon as prices are updated. Trading takes negligibly little time. None of his intended trades fail. If he wants to buy, he can always buy, and if he wants to sell, he can sell immediately.

Assume the analysis is correct at all times and his capital is always large enough to buy. Find the maximum profit he can earn by trading over $T$ days.

The first line contains integers $N$ and $T$, separated by a space. $(1 \leq N \leq 111222;\ 1 \leq T \leq 10^{12})$

The second line contains the values of $P_i$ on the day Junseong starts trading, given in order with no spaces.

Print the answer to the problem on the first line.

Cryptocurrencies that Junseong still holds when trading ends are not counted in the profit.