echilibru

Echilibrul unui șir $x_1, x_2, \cdots, x_k$ este egal cu $max (x_1, x_2, \cdots, x_k) - min (x_1, x_2, \cdots, x_k)$.

De exemplu, echilibrul șirului $4, 7, 6$ este $7 - 4 = 3$, echilibrul șirului $9, 1, 2$ este $9 - 1 = 8$, iar echilibrul șirului $7, 7, 7$ este $7 - 7 = 0$.

Se dă $P$, $N$ și un șir de $N$ numere naturale $a_1$, $a_2$, $\cdots$, $a_N$.

Cerință

Dacă $P$ = 1, aflați echilibrul șirului $a$.

Dacă $P$ = 2, aflați echilibrul minim al unei subsecvențe de lungime cel puțin $2$ a șirului $a$.

Date de intrare

Pe prima linie a fișierului de intrare echilibru.in se află două numere naturale $P$ și $N$ separate printr-un spațiu. Pe cea de-a 2-a linie se află $N$ numere naturale separate prin câte un spațiu, reprezentând șirul $a$.

Date de ieșire

Pe prima linie din fișierul de ieșire echilibru.out se află un număr natural reprezentând raspunsul la cerința 1 dacă $P$ = 1, altfel la cerința 2.

Restricții și precizări

• Datorită vitezei mari ale evaluatorului kilonova, limita de timp este diferită față de cea din concurs.
• O subsecvență a șirului $a$ este un șir de elemente de pe poziții consecutive din șirul $a$
• $P = 1$ sau $P = 2$
• $2 \leq N \leq 100 \ 000$
• $1 \leq a_i \leq 10^9$
• Pentru 30 de puncte $P = 1$.
• Pentru 20 de puncte $P = 2$, dar $N \leq 100$.
• Pentru 20 de puncte $P = 2$, dar $100 < N \leq 1 \ 000$.

Exemplul 1

echilibru.in

1 8
2 5 8 9 3 1 6 25

echilibru.out

24

Exemplul 2

echilibru.in

2 8
2 5 8 9 3 1 6 25

echilibru.out

1

Exemplul 3

echilibru.in

2 8
8 5 7 10 7 9 7 3

echilibru.out

2

Explicații

În primul exemplu, maximul șirului este $25$, iar minimul șirului este $1$, așadar echilibrul șirului este $25 - 1 = 24$.

La al doilea exemplu, echilibrul minim este 1. Subsecvența alesă este cea formată din numerele $8$ și $9$ (pozițiile $3$ și $4$). Echilibrul șirului $8, 9$ este $9 - 8 = 1$.

La al treilea exemplu, echilibrul minim este 2. Subsecvențele care au echilibrul 2 sunt: $(5, 7), (7, 9)$ și $(7, 9, 7)$.