E - Mountain View Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は N 個の山が一列に並んでいる風景を眺めています。それぞれの山には 1 から N までの番号が付けられており、山 i の標高は A_i メートルです。

高橋君は、各山について「その山以外に、標高が厳密に高い山がいくつあるか」を調べたいと思っています。これは、その山の頂上に立ったとき、自分より高い山が全部でいくつ存在するかを把握するための参考になるからです。

N 個の山それぞれについて、その山以外の山のうち標高が厳密に高い山の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、山の数を表す整数 N が与えられる。
  • 2 行目には、各山の標高を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • A_i は山 i の標高（メートル）を表す。

出力

B_1 B_2 \ldots B_N
  • N 個の整数をスペース区切りで 1 行に出力せよ。
  • B_i は、山 i 以外の山のうち標高が A_i より厳密に高い山の数を表す。

入力例 1

5
3 1 4 1 5

出力例 1

2 3 1 3 0

入力例 2

8
100 200 150 200 300 100 250 300

出力例 2

6 3 5 3 0 6 2 0

入力例 3

12
1000000000 1 500000000 999999999 1000000000 250000000 750000000 1 999999998 500000000 250000000 750000001

出力例 3

0 10 6 2 0 8 5 10 3 6 8 4

Score : 333 pts

Problem Statement

Takahashi is looking at a landscape where N mountains are lined up in a row. Each mountain is numbered from 1 to N, and mountain i has an elevation of A_i meters.

For each mountain, Takahashi wants to find out "how many other mountains have a strictly higher elevation." This serves as a reference for understanding how many mountains taller than himself exist when standing at the summit of that mountain.

For each of the N mountains, determine the number of other mountains that have a strictly higher elevation.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of mountains.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the elevation of each mountain.
  • A_i represents the elevation (in meters) of mountain i.

Output

B_1 B_2 \ldots B_N
  • Output N integers separated by spaces on a single line.
  • B_i represents the number of mountains other than mountain i that have a strictly higher elevation than A_i.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

2 3 1 3 0

Sample Input 2

8
100 200 150 200 300 100 250 300

Sample Output 2

6 3 5 3 0 6 2 0

Sample Input 3

12
1000000000 1 500000000 999999999 1000000000 250000000 750000000 1 999999998 500000000 250000000 750000001

Sample Output 3

0 10 6 2 0 8 5 10 3 6 8 4