Overview

Given \(N\) mountains, the problem asks to find, for each mountain, the number of mountains whose elevation is strictly higher than it.

Analysis

First, a straightforward approach would be “for each mountain, check every other mountain one by one to see if it is higher.” However, this method performs \(N\) comparisons for each of the \(N\) mountains, resulting in an overall time complexity of \(O(N^2)\). Given the constraint \(N \leq 2 \times 10^5\), \(N^2\) is approximately \(4 \times 10^{10}\), which will not fit within the time limit.

Therefore, we consider the approach of sorting the elevations. Suppose we sort the mountains in descending order of elevation. For example, if the elevations are [10, 30, 20, 30], sorting in descending order gives [30, 30, 20, 10].

Now, if we look at the index (position counted from 0) of each element, we can observe the following: - The first 30 is at index 0: there are 0 mountains higher than it - The second 30 is at index 1: there are (strictly) 0 mountains higher than it - 20 is at index 2: there are 2 mountains higher than it (two 30s) - 10 is at index 3: there are 3 mountains higher than it (two 30s and one 20)

In other words, in the descending sorted list, the index where a given elevation “first appears” equals the number of mountains that are strictly higher than that elevation.

Algorithm

1. Copy the list of mountain elevations \(A\) and create a list \(A_{sorted}\) sorted in descending (largest first) order.
2. Scan \(A_{sorted}\) from the beginning and record in a dictionary (hash map) the “first position where each elevation appears.”
   • Elevations already registered in the dictionary are ignored; only the first occurrence of each elevation and its index are saved.
3. For each element in the original list \(A\), look up the corresponding index (number of mountains higher than it) from the dictionary and output it as the result.

Complexity

• Time complexity: \(O(N \log N)\)
  • Reading input takes \(O(N)\), sorting takes \(O(N \log N)\), and building the dictionary and constructing the result takes \(O(N)\). Overall, the sorting step dominates.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the sorted list and the dictionary that stores the count for each elevation.

Implementation Notes

• Fast I/O: Since \(N\) can be large, it is more efficient to read all input at once using sys.stdin.read().split() rather than calling Python’s input() repeatedly.

• Using a dictionary: A dictionary is used to retrieve the “number of mountains higher than a given value” in \(O(1)\).

• Handling duplicates: When multiple mountains have exactly the same elevation, they should not be considered “strictly higher” than each other. By recording the “first occurrence position” in the sorted list, this condition is naturally satisfied.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    # これにより、大量の入力データを高速に処理できる
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1番目の要素は山の数 N
    n = int(input_data[0])
    # 2番目以降の要素は各山の標高 A_i
    a = list(map(int, input_data[1:n+1]))
    
    # 標高を降順（高い順）にソートしたリストを作成する
    # 降順に並べたとき、ある値が最初に現れるインデックスは、
    # その値よりも厳密に大きい要素の数と一致する
    a_sorted = sorted(a, reverse=True)
    
    # 各標高に対して、自分より高い山がいくつあるかを格納する辞書
    higher_than_count = {}
    for i, val in enumerate(a_sorted):
        # 既に辞書に登録されている（＝同じ標高の山が既に現れている）場合はスキップ
        if val not in higher_than_count:
            # 最初に現れた時のインデックス i が、自分より高い山の数
            higher_than_count[val] = i
    
    # 元の山の順番に従って、自分より高い山の数をリストに格納する
    result = [higher_than_count[val] for val in a]
    
    # 結果をスペース区切りで1行に出力する
    sys.stdout.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.