Count the maximum in each queried suffix

You are given an integer array nums of length n and an array query of 0-based start indices.

For each index i in query, look at the suffix nums[i], nums[i+1], ..., nums[n-1]. Find the largest value in that suffix and report how many times it occurs in the suffix. Return the answers as a list in the same order as query.

def suffix_max_counts(nums: list[int], query: list[int]) -> list[int]: ...

Constraints

• 1 <= n <= 10^5, 0 <= len(query) <= 10^5
• -10^9 <= nums[j] <= 10^9
• 0 <= query[k] < n; indices may repeat and come in any order.

Aim for better than rescanning the suffix for every query.

Example 1

nums  = [4, 9, 1, 9, 3]
query = [0, 2, 4, 1]
output: [2, 1, 1, 2]

The suffix from index 0 is [4, 9, 1, 9, 3]; its maximum 9 occurs twice. The suffix from index 2 is [1, 9, 3]; 9 occurs once. The suffix from index 4 is [3].

Example 2

nums  = [6, 6, 6]
query = [2, 0, 1, 0]
output: [1, 3, 2, 3]