Find the time when a given worm appears in the evolutionary chain described by sorted sizes.
Problem
You are given a collection of worms, each with a size value. The worms are arranged so that after sorting the sizes in nondecreasing order, the position of a worm in that sorted order determines its evolutionary stage.
For each query, determine whether a worm of a given size can be found in the collection and, if so, report its position in the sorted order. If the size does not exist, report that it is absent.
This is a straightforward search problem that becomes simple after sorting and using efficient lookup.
Intuition
The key idea is to sort the worm sizes once, then answer queries by locating the target size with binary search or an equivalent ordered lookup.
Input Format
- The first line contains an integer — the number of worms.
- The second line contains integers representing worm sizes.
- The next line contains an integer — the number of queries.
- Each of the next lines contains one integer representing a queried size.
Output Format
For each query, output:
- the 1-based position of in the sorted list if it exists, or
-1if no worm has that size.
Constraints
- worm sizes, queries
- Time limit suggests an solution.
Example 1
Input
5 4 1 7 3 3 4 3 5 1 8
Output
2 -1 1 -1
Explanation
After sorting, the sizes are [1, 3, 3, 4, 7].
- 3 appears first at position 2.
- 5 does not appear.
- 1 appears at position 1.
- 8 does not appear.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.