Tehtävänanto

JOI-kaupungissa on $N$ asukasta, jotka on numeroitu $1$:stä $N$:ään, ja asukkaan $i$ ($1 \le i \le N$) ikä on $A_i$ vuotta.

Annetaan JOI-kaupungin asukkaiden iät $A_1, A_2, \dots, A_N$. Kirjoita ohjelma, joka etsii kullekin $i = 1, 2, \dots, N$ suurimman ikäeron asukkaan $i$ ja muiden asukkaiden välillä.

Rajoitukset

• $2 \le N \le 250000$.
• $0 \le A_i \le 10^9$ ($1 \le i \le N$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($25$ pistettä) $N = 2$.
2. ($30$ pistettä) $N \le 1000$.
3. ($45$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan seuraavassa muodossa:

$N$ $A_1 \ A_2 \ \dots \ A_N$

Tuloste

Tulosta $N$ riviä. Tulosta $i$. riville ($1 \le i \le N$) suurin ikäero asukkaan $i$ ja muiden asukkaiden välillä.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

3
13 15 20

Esimerkkituloste 1

7
5
7

• Ikäerot asukkaan $1$ ja asukkaiden $2, 3$ välillä ovat $2, 7$ vuotta. Koska näistä suurin arvo on $7$ vuotta, $1$. riville tulostetaan $7$.
• Ikäerot asukkaan $2$ ja asukkaiden $1, 3$ välillä ovat $2, 5$ vuotta. Koska näistä suurin arvo on $5$ vuotta, $2$. riville tulostetaan $5$.
• Ikäerot asukkaan $3$ ja asukkaiden $1, 2$ välillä ovat $7, 5$ vuotta. Koska näistä suurin arvo on $7$ vuotta, $3$. riville tulostetaan $7$.

Tämä esimerkkisyöte täyttää osatehtävien $2, 3$ rajoitukset.

Esimerkkisyöte 2

2
100 100

Esimerkkituloste 2

0
0

• Ikäero asukkaan $1$ ja asukkaan $2$ välillä on $0$ vuotta. Siispä $1$. riville tulostetaan $0$.
• Ikäero asukkaan $2$ ja asukkaan $1$ välillä on $0$ vuotta. Siispä $2$. riville tulostetaan $0$.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkkisyöte 3

10
440894064 101089692 556439322 34369336 98417847 216265879 623843484 554560874 247445405 718003331

Esimerkkituloste 3

406524728
616913639
522069986
683633995
619585484
501737452
589474148
520191538
470557926
683633995

Tämä esimerkkisyöte täyttää osatehtävien $2, 3$ rajoitukset.