Answer k-step ancestor queries in a rooted tree

You are given a rooted tree encoded as a parent array par[1..n] where:

• Nodes are labeled 1..n .
• par[i] is the parent of node i .
• Exactly one node has par[i] = -1 (the root).

You must answer q queries. Each query provides a starting node u and an integer k.

Starting from u, apply the following operation exactly k times (or until you cannot move further):

• If the current node has a parent, move to its parent.
• If the current node is the root (parent is -1 ), you stay at the root for all remaining steps.

For each query, output the final node label after performing the moves.

Input format

• n
• array par[1..n]
• q
• q lines: u k

Output format

• For each query, one line with the final node label.

Constraints (typical interview scale)

• 1 <= n, q <= 2 * 10^5
• 0 <= k <= 10^9
• par[i] = -1 or 1 <= par[i] <= n

Example

If par = [-1, 1, 1, 2, 2, 2, 2] (meaning par[1]=-1, par[2]=1, ...):

• Query (u=7, k=2) goes 7 -> 2 -> 1 , output 1 .
• Query (u=4, k=10) ends at root 1 , output 1 .