Find Marble · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Hash Maps

Sorting

Find Marble

Find the 1-based position of a target marble after tracking swaps among a sequence of marbles.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given a collection of marbles initially placed in a known order. One marble is special: the query asks for the position of a particular marble after a sequence of updates/swaps is processed.

Your task is to determine where the queried marble ends up.

A typical solution keeps track of where each marble is located instead of simulating the entire arrangement from scratch after every operation.

Notes

Positions are usually considered from left to right.
The answer is expected as an index/position in the final arrangement.
When multiple operations are present, efficiency matters more than brute-force re-scanning.

Input Format

The first line contains an integer $n$ .
The next line contains the initial ordering or labels of the marbles.
The following lines describe operations/queries involving a target marble.
Exact formatting may vary by platform version; process the sequence and report the final position of the queried marble.

Output Format

Print the position of the queried marble after processing all operations.
Use the indexing convention required by the statement (typically 1-based).

Constraints

$1 \le n$ is assumed to be small to moderate in statement variants, but the intended solution should be efficient.
Marble labels are distinct in the standard formulation.
The number of operations may be large enough that repeated linear scans are undesirable.

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 2 3 4 5
query 3

Output

Explanation

The marble labeled 3 is already in position 3.

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.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress