Leaderboard rank: hints, no solution

A quiz platform keeps its scores in a list ordered from highest to lowest. Several players can share a score, and scores may be negative because wrong answers cost points.

Several new players finish with the scores in queries. For each one, report how many recorded scores are strictly higher than that score. A player's rank is one more than that count, with ties sharing the better rank. Return only the counts, in the order of queries, with 0 where nothing is higher or the list is empty.

The list is long and every query reads the same list, so avoid reading every entry for each one.

Examples

Input

scores = [90, 80, 80, 60, 40], queries = [80, 70]

Output

[1, 3]

Note

Only the 90 beats 80; three scores are above 70.

Input

scores = [50, 50, 50], queries = [50, 49]

Output

[0, 3]

Note

Equal scores do not count as higher.

Constraints

• 0 <= scores.length <= 100000
• scores is sorted in descending order and may contain duplicates
• -1000000 <= scores[i] <= 1000000
• 0 <= queries.length <= 2000; -1000000 <= queries[j] <= 1000000

Hint 1: a nudge

Think about where the new score would sit if you slipped it into the list. What does that position tell you about how many scores are above it?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing