โจทย์ปัญหา

ในเมือง JOI มีพลเมือง $N$ คนที่มีหมายเลขตั้งแต่ $1$ ถึง $N$ และอายุของพลเมือง $i$ ($1 \le i \le N$) คือ $A_i$ ปี

กำหนดอายุของพลเมืองในเมือง JOI คือ $A_1, A_2, \dots, A_N$ มาให้ จงเขียนโปรแกรมเพื่อหาค่าสูงสุดของผลต่างของอายุระหว่างพลเมือง $i$ กับพลเมืองคนอื่น ๆ สำหรับแต่ละ $i = 1, 2, \dots, N$

ข้อจำกัด

• $2 \le N \le 250000$
• $0 \le A_i \le 10^9$ ($1 \le i \le N$)
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

ปัญหาย่อย

1. ($25$ คะแนน) $N = 2$
2. ($30$ คะแนน) $N \le 1000$
3. ($45$ คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะกำหนดให้ในรูปแบบต่อไปนี้:

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

ข้อมูลส่งออก

จงแสดงผล $N$ บรรทัด ในบรรทัดที่ $i$ ($1 \le i \le N$) ให้แสดงผลค่าสูงสุดของผลต่างของอายุระหว่างพลเมือง $i$ กับพลเมืองคนอื่น ๆ

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

ตัวอย่างข้อมูลนำเข้า 1

3
13 15 20

ตัวอย่างข้อมูลส่งออก 1

7
5
7

• ผลต่างของอายุระหว่างพลเมือง $1$ กับพลเมือง $2, 3$ คือ $2, 7$ ปี ตามลำดับ เนื่องจากค่าสูงสุดของค่าเหล่านี้คือ $7$ ปี จึงแสดงผล $7$ ในบรรทัดที่ $1$
• ผลต่างของอายุระหว่างพลเมือง $2$ กับพลเมือง $1, 3$ คือ $2, 5$ ปี ตามลำดับ เนื่องจากค่าสูงสุดของค่าเหล่านี้คือ $5$ ปี จึงแสดงผล $5$ ในบรรทัดที่ $2$
• ผลต่างของอายุระหว่างพลเมือง $3$ กับพลเมือง $1, 2$ คือ $7, 5$ ปี ตามลำดับ เนื่องจากค่าสูงสุดของค่าเหล่านี้คือ $7$ ปี จึงแสดงผล $7$ ในบรรทัดที่ $3$

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของปัญหาย่อยที่ $2, 3$

ตัวอย่างข้อมูลนำเข้า 2

2
100 100

ตัวอย่างข้อมูลส่งออก 2

0
0

• ผลต่างของอายุระหว่างพลเมือง $1$ กับพลเมือง $2$ คือ $0$ ปี ดังนั้นจึงแสดงผล $0$ ในบรรทัดที่ $1$
• ผลต่างของอายุระหว่างพลเมือง $2$ กับพลเมือง $1$ คือ $0$ ปี ดังนั้นจึงแสดงผล $0$ ในบรรทัดที่ $2$

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของทุกปัญหาย่อย

ตัวอย่างข้อมูลนำเข้า 3

10
440894064 101089692 556439322 34369336 98417847 216265879 623843484 554560874 247445405 718003331

ตัวอย่างข้อมูลส่งออก 3

406524728
616913639
522069986
683633995
619585484
501737452
589474148
520191538
470557926
683633995

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของปัญหาย่อยที่ $2, 3$