Overview

For each mountain, determine how many mountains have a strictly higher elevation.

Approach

For each mountain \(i\), we need to find how many values in the entire array are greater than \(A_i\).
A naive approach would compare each mountain against all other mountains in \(O(N^2)\), but
under the constraint \(N \leq 2 \times 10^5\), this cannot be computed within the time limit (TLE).

Therefore, we use the following idea:
- For each element \(A_i\), we want to efficiently find the number of elements greater than it.
- This can be achieved using binary search after sorting the entire array.

Specifically: - Prepare a sorted array sorted_A of all elements. - For each \(A_i\), use binary search to find the leftmost position in sorted_A of an element greater than \(A_i\). - The number of elements from that position onward is the count of elements greater than \(A_i\).

For example, if \(A = [3, 1, 4, 1, 5]\): - Sorting gives sorted_A = [1, 1, 3, 4, 5] - For \(A_1 = 3\), bisect_right(sorted_A, 3) returns index 3. - Therefore, the number of elements greater than 3 is \(5 - 3 = 2\).

In this way, each query can be processed in \(O(\log N)\).

Algorithm

1. Read the input list of mountain elevations \(A\).
2. Create a sorted list sorted_A from \(A\).
3. For each \(A_i\), find the number of elements in sorted_A that are greater than \(A_i\).
   • Use bisect.bisect_right(sorted_A, A_i) to obtain the smallest index of an element greater than \(A_i\).
   • Subtract that index from the total number of elements \(N\) to get the answer.
4. Output the results in order.

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting, \(O(N \log N)\) for binary search on each element
• Space complexity: \(O(N)\)
  • For storing the sorted array and results

Implementation Notes

• bisect.bisect_right returns “the first position exceeding the specified value,” so it can be used to easily compute “the number of strictly greater elements.”

• It is more efficient to collect all results and output them together at the end.

  Source Code

import bisect

N = int(input())
A = list(map(int, input().split()))

sorted_A = sorted(A)

result = []
for a in A:
    idx = bisect.bisect_right(sorted_A, a)
    result.append(N - idx)

print(' '.join(map(str, result)))

This editorial was generated by qwen3-coder-480b.