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 p1 și p2, unde p1<p2. 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 d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Cerința

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.

Date de intrare

Fișierul de intrare dif2.in 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 p1 p2 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 d1 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 d2 reprezentând diferența dintre valorile aflate pe pozițiile p1 și p2 din șirul Y, presupunând că ar fi ordonat descrescător.

Restricții și precizări

• 3 < n < 300 000
• 1 ≤ p1 < p2 ≤ n2
• 1 ≤ X[i] < 300 000, i=1..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

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*6 și 2*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*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 d2 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