Dynamic array — Eolymp

Input

The first line contains two integers $n$ and $m (2 \leq n \leq m \leq 1 0^{5})$ m~(2 \le n \le m \le 10^5). The next line contains $n$ integers $a_{1}, a_{2}, ..., a_{n} (1 \leq a_{i} \leq 1 0^{6})$ a_1, a_2, ..., a_n~(1 \le a_i \le 10^6).

Output

Print the smallest possible value of the largest number written on the board.

Examples

Example 1.

1, 1 \to 1, 2, 1 \to 1, 3, 2, 1 \to 1, 3, 2, 3, 1

1, 1 → 1, 𝟐, 1 → 1, 𝟑, 2, 1 → 1, 3, 2, 𝟑, 1

Example 2.

4, 6, 3 \to 4, 6, 9, 3

4, 6, 3 → 4, 6, 𝟗, 3

Example 1

Loading

Example 2

Loading

Example 3

Loading