409183: GYM103451 C Krosh and paths

Krosh has a graph of $$$n$$$ vertexes. For any vertex $$$1 \le i \le n - 2$$$ there are oriented edges $$$(i, i + 1)$$$ and $$$(i, i + 2)$$$, for vertex $$$n - 1$$$ there is oriented edge $$$(n - 1, n)$$$. Every vertex has it's value - $$$a_i$$$. Krosh considers paths from vertex $$$1$$$ to vertex $$$n$$$. Cost of the path is the maximum among all the values of the vertexes Krosh has visited. Help Krosh to calculate sum of costs over all the paths from $$$1$$$ to $$$n$$$. Output answer modulo $$$m$$$ where $$$m$$$ is given(can be non-prime).

In first line you are given two numbers $$$1 \le n \le 2 * 10^5$$$ and $$$10 \le m \le 10^9$$$ - number of vertexes and modulo.In next line you are given $$$n$$$ positive integres $$$1 \le a_i \le 10^9$$$ values of vertexes.

Output answer modulo m.

4 1000
2 3 5 3

13

1 1000000000
1000000000

0

5 583723
1000000000 1000000000 1000000000 1000000000 1000000000

412505