問題文

JOIG 高校には，1 から N までの番号が付けられた N 個のクラスがある．

今日は JOIG 高校の運動会で，最後の競技を残すのみとなった．最後の競技が始まる直前でのクラス i (1\leqq i \leqq N) の得点は A_i である． 最後の競技では，N 個のクラスすべてが出場し，各クラスに 1 位から N 位までの相異なる順位が付けられる．

最後の競技では， j (1\leqq j \leqq N) 位のクラスの得点に N - j + 1 点が加算され，その後最終的な順位が決定される． 最終的な順位は，得点の高いクラスが上の順位となり，同点の場合はクラスの番号が小さい方が上の順位となる．

JOIG 高校の運動会実行委員である葵さんは，競技終了後各クラスに授与する賞状を予め作っておきたいと考えている． そこで，最終的に各クラスが何種類の順位を取りうるか知りたい．

最後の競技が終わった後，各クラスが取りうる最終的な順位の種類数を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 1\,000\,000．
• 1 \leqq A_i \leqq 10^9 (1\leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (12 点) N \leqq 9．
2. (27 点) N \leqq 300．
3. (21 点) N \leqq 5\,000．
4. (29 点) N \leqq 200\,000．
5. (11 点) 追加の制約はない．

入力例 1

4
5 2 3 6

出力例 1

3 2 3 3

例として，最後の競技の結果がクラスの番号順に 2 位，3 位，1 位，4 位である場合を考える．それぞれのクラスの得点に 3 点，2 点，4 点，1 点が加算されるため， 最終的な得点は順に 8 点，4 点，7 点，7 点となる．したがって，最終的な順位はそれぞれ 1 位，4 位，2 位，3 位となる．

このように，最後の競技の順位としてありうるものすべてを考慮したとき，各クラスが取りうる最終的な順位は以下のようになる．

• クラス 1 が取りうる最終的な順位は 1 位，2 位，3 位の 3 種類である．
• クラス 2 が取りうる最終的な順位は 3 位，4 位の 2 種類である．
• クラス 3 が取りうる最終的な順位は 2 位，3 位，4 位の 3 種類である．
• クラス 4 が取りうる最終的な順位は 1 位，2 位，3 位の 3 種類である．

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

入力例 2

3
1000000000 1 1

出力例 2

1 2 2

クラス 1 は最後の競技結果によらず最終的な順位が 1 位となるため，1 番目には 1 を出力する．

クラス 2 とクラス 3 は，最後の競技で上の順位を取ったほうが 2 位，下の順位を取ったほうが 3 位となるため，2 番目と 3 番目にはそれぞれ 2 を出力する．

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

入力例 3

7
11 10 17 10 15 7 11

出力例 3

7 6 3 6 5 4 6

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