== include(page="template/taskheader" task_id="dif2") ==

Poveste şi cerinţă...

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=(X[~1~],X[~2~],…,X[~n~])$ 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=(Y[~1~],Y[~2~],…,Y[~n*n~])$ cu $n*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~] * X[~j~], 1 ≤ i, j ≤ 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.
 
h2. Cerinţă
 
Dându-se şirul $X$ cu $n$ elemente şi valorile p[~1~] şi p[~2~], determinaţi valorile d[~1~] şi d[~2~].

h2. Date de intrare

Fişierul de intrare $dif2.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $dif2.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 < n < 300.000$
* $1 ≤ p[~1~] < p[~2~] ≤ n^2^$
* $1 ≤ X[~i~] < 300.000, pentru 1 ≤ i ≤ 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 ≤ 100$

h2. Exemplu

table(example). |_. dif2.in |_. dif2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. dif2.in |_. dif2.out |_. Explicaţie |
| 1
  4
  3
  5
  2
  6
| 32
| Atenţie, C=1, deci se rezolvă doar cerinţa 1!
  Valoarea maximă d[~1~] va fi 32 şi se obţine efectuând diferenţa dintre 6*6 şi 2*2.
|
 
table(example). |_. dif2.in |_. dif2.out |_. Explicaţie |
| 2
  4 5 11
  3
  5
  2
  6
| 8
| Atenţie, C=2, deci se rezolvă doar cerinţa 2!
  Se obţin în Y următoarele 16 valori: 3*3, 3*5, 3*2, 3*6, 5*3, 5*5, 5*2, 5*6, 2*3, 2*5, 2*2, 2*6, 6*3, 6*5, 6*2, 6*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
|

== include(page="template/taskfooter" task_id="dif2") ==
 

== include(page="template/taskfooter" task_id="dif2") ==