第22回日本情報オリンピック　二次予選

2022年12月13日
情報オリンピック日本委員会

問題文

JOI 市には 1 から N までの番号が付けられた N 人の住民がおり，住民 i (1 ≦ i ≦ N) の年齢は A_i 歳である．

JOI 市の住民の年齢 A₁, A₂, …, A_N が与えられる．i = 1, 2, …, N に対して，住民 i と他の住民との年齢の差の最大値を求めるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 250 000．
• 0 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (25 点) N = 2．
2. (30 点) N ≦ 1 000．
3. (45 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁ A₂ … A_N

出力

N 行出力せよ．i 行目 (1 ≦ i ≦ N) には，住民 i と他の住民との年齢の差の最大値を出力せよ．

入出力例

入力例 1
3
13 15 20

出力例 1
7
5
7

• 住民 1 と住民 2, 3 との年齢の差はそれぞれ 2, 7 歳である．これらの最大値は 7 歳であるから，1 行目には 7 を出力する．
• 住民 2 と住民 1, 3 との年齢の差はそれぞれ 2, 5 歳である．これらの最大値は 5 歳であるから，2 行目には 5 を出力する．
• 住民 3 と住民 1, 2 との年齢の差はそれぞれ 7, 5 歳である．これらの最大値は 7 歳であるから，3 行目には 7 を出力する．

この入力例は小課題 2, 3 の制約を満たす．

入力例 2
2
100 100

出力例 2
0
0

• 住民 1 と住民 2 との年齢の差は 0 歳である．したがって，1 行目には 0 を出力する．
• 住民 2 と住民 1 との年齢の差は 0 歳である．したがって，2 行目には 0 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 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 の制約を満たす．