dif2

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă.

Se dă un șir $X= \left(X_1, X_2, \ldots, X_n\right)$ de numere naturale nenule și două numere naturale $p_1$ și $p_2$, unde $p_1 < p_2$.

Sandu trebuie să construiască un nou șir $Y=\left( Y_1, Y_2, \ldots,Y_{n \cdot n}\right)$ cu $n \cdot n$ elemente obținute din toate produsele de câte două elemente din șirul $X$ (fiecare element din șirul $Y$ este de forma $X_i \cdot X_j$, $1 \leq i$, $j \leq n$).

Sandu are de calculat două valori naturale $d_1$ și $d_2$ obținute din șirul $Y$. Valoarea $d_1$ este egală cu diferența maximă posibilă dintre două valori ale șirului $Y$. Pentru a obține valoarea $d_2$, Sandu trebuie să considere că șirul $Y$ are elementele ordonate descrescător iar $d_2$ va fi diferența dintre valorile aflate pe pozițiile $p_1$ și $p_2$ în șirul ordonat descrescător. Sandu a găsit rapid valorile $d_1$ și $d_2$ și, pentru a le verifica, vă roagă să le determinați și voi.

Cerință

Dându-se șirul $X$ cu $n$ elemente și valorile $p_1$ și $p_2$, determinați valorile $d_1$ și $d_2$.

Date de intrare

Fișierul de intrare dif2.in va conține pe prima linie un număr natural $C$ care poate fi doar $1$ sau $2$. Dacă $C = 1$, atunci pe linia a doua se va afla numărul natural $n$. Dacă $C = 2$, atunci pe linia a doua se vor afla numerele naturale $n$, $p_1$ și $p_2$ separate prin câte un spațiu. În ambele cazuri, pe următoarele $n$ linii se vor afla elementele șirului $X$, câte un număr natural pe fiecare linie a fișierului.

Date de ieșire

În cazul $C = 1$, fișierul de ieșire dif2.out va conține pe prima linie valoarea $d_1$ egală cu diferența maximă dintre oricare două valori din șirul $Y$. În cazul $C = 2$ fișierul de ieșire va conține pe prima linie un număr natural $d_2$ reprezentând diferența dintre valorile aflate pe pozițiile $p_1$ și $p_2$ din șirul $Y$, presupunând că ar fi ordonat descrescător.

Restricții și precizări

• $3 < N < 300 \ 000$
• $1 \leq p_1 < p_2 \leq n^2$
• $1 \leq X_i < 300 \ 000$, $i = \{ 1 \ldots n \}$
• Pentru teste valorând $30$ de puncte vom avea $C = 1$, iar pentru teste valorând $70$ de puncte vom avea $C = 2$
• Pentru teste valorând $10$ puncte vom avea $C = 2$ și $n \leq 100$

Exemplul 1

dif2.in

1
4
3
5
2
6

dif2.out

32

Explicație

Atenție, $C = 1$, deci se rezolvă doar cerința $1$!

Valoarea maximă d1 va fi $32$ și se obține efectuând diferența dintre $6 \cdot 6$ și $2 \cdot 2$.

Exemplul 2

dif2.in

2
4 5 11
3
5
2
6

dif2.out

8

Explicație

Atenție, $C = 2$, deci se rezolvă doar cerința $2$!
Se obțin în $Y$ următoarele $16$ valori: $3 \cdot 3$, $3 \cdot 5$, $3 \cdot 2$, $3 \cdot 6$, $5 \cdot 3$, $5 \cdot 5$, $5 \cdot 2$, $5 \cdot 6$, $2 \cdot 3$, $2 \cdot 5$, $2 \cdot 2$, $2 \cdot 6$, $6 \cdot 3$, $6 \cdot 5$, $6 \cdot 2$, $6 \cdot 6$. Valoarea $d_2$ va fi $8$, deoarece dacă vom considera șirul $Y$ ordonat descrescător ($36, 30, 30, 25, 18, 18, 15, 15, 12, 12, 10, 10, 9, 6, 6, 4$), atunci $Y[5] - Y[11] = 18 - 10 = 8$