Overview

For each mountain \(i\), determine how many mountains in total have an elevation strictly higher than \(A_i\).

Analysis

A naive approach would be, for each \(i\), to iterate over all mountains \(j\) and count those with \(A_j > A_i\), but this is \(O(N^2)\), which is too slow for \(N \le 2 \times 10^5\).

The key observation is as follows:

• What we want is “the number of mountains higher than ourselves” = “subtract from the total \(N\) the count of those with elevation at most \(A_i\) (\(A_j \le A_i\))”
• In other words, we can write \(B_i = N - \#\{j \mid A_j \le A_i\}\).

So how do we efficiently compute \(\#\{j \mid A_j \le A_i\}\)? If we sort the elevation array in advance, we can use binary search to find “up to where in the sorted array the elements are at most \(A_i\).”

Example: For \(A = [4, 2, 4, 1]\), sorting gives \(SA = [1,2,4,4]\) - When \(A_i=2\), elements \(\le 2\) are \([1,2]\), which is 2 → mountains strictly higher: \(4-2=2\) - When \(A_i=4\), elements \(\le 4\) are 4 → mountains strictly higher: \(4-4=0\)

Since we want “strictly higher,” note that mountains with the same elevation should not be counted. For this reason, counting “the number of elements \(\le A_i\)” works perfectly, and in Python we can use bisect_right (which returns the position to the right of all equal values).

Algorithm

1. Sort array \(A\) to create \(SA\).
2. For each \(a = A_i\), use bisect_right(SA, a) to:
   • Obtain the number of elements \(\le a\): \(k = \#\{j \mid A_j \le a\}\)
3. The answer is \(B_i = N - k\).

Reason for using bisect_right: - bisect_right(SA, a) returns “the rightmost position where \(a\) can be inserted while maintaining order” = “the number of elements \(\le a\)” - Therefore, \(N - bisect\_right(SA, a)\) gives “the number of elements strictly greater than \(a\).”

Complexity

• Time complexity: \(O(N \log N)\) for sorting, \(O(\log N)\) per binary search done \(N\) times for \(O(N \log N)\), totaling \(O(N \log N)\)
• Space complexity: \(O(N)\) for the sorted array \(SA\), etc.

Implementation Notes

• Since we need “strictly higher,” we must exclude mountains with the same elevation. For this reason, using bisect_right instead of bisect_left to count “elements \(\le A_i\)” is the clean approach.

• Since the output requires \(N\) values on a single line separated by spaces, converting to strings and combining with " ".join(...) is efficient.

  Source Code

import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    SA = sorted(A)
    ans = [str(N - bisect_right(SA, a)) for a in A]
    print(" ".join(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.