给定一棵包含 $N$ 个顶点的有根二叉树。顶点编号从 $1$ 到 $N$，根节点为 $1$ 号顶点。其他每个顶点在树中都有唯一的父节点。该树是二叉树，即每个顶点最多有两个子节点。

其中有一个特殊的顶点。你需要猜出它是哪一个。你可以进行以下形式的询问：“特殊顶点是否在顶点 $x$ 的子树中？”如果节点 $y$ 到 $1$ 号顶点的最短路径经过顶点 $x$，则称节点 $y$ 在顶点 $x$ 的子树中。注意，顶点 $x$ 本身也在其子树中。

你最多可以进行 $35$ 次询问。之后，你需要报告你的猜测。

实现细节

你需要实现以下函数：

int solve(int N, std::vector < int > p)

• $N$：顶点数量。
• $p$ 包含 $N - 1$ 个元素，用于描述这棵树：对于每个 $0 \le i \le N - 2$，顶点 $p[i]$（其中 $1 \le p[i] \le i + 1$）是顶点 $i + 2$ 的父节点。
• $p$ 中的任何元素出现次数不超过两次。
• 该函数应返回特殊顶点的编号。
• 该函数将被调用恰好一次。

上述函数可以调用以下函数：

int ask(int x)

• $x$：顶点编号。
• $1 \le x \le N$
• 如果特殊顶点在 $x$ 的子树中，返回 $1$，否则返回 $0$。

样例

考虑以下调用：

solve(5, [1, 1, 2, 4])

该树包含边 $(1,2), (1,3), (2,4)$ 和 $(4,5)$。

你的程序进行了如下调用：

ask(4)

返回 $1$。之后你的程序进行了如下调用：

ask(5)

返回 $0$。

你的程序推断出 $4$ 号顶点是特殊顶点并返回 $4$。

数据范围

• $2 \le N \le 100\,000$

子任务

1. ($20$ 分) $N \le 35$
2. ($30$ 分) 对于每个 $0 \le i \le N - 2$，满足 $p[i] = i + 1$
3. ($15$ 分) 对于每个 $0 \le i \le N - 2$，满足 $p[i] = \lfloor i/2 \rfloor + 1$
4. ($35$ 分) 无附加限制。

样例交互器

样例交互器按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$p[0], p[1], \dots, p[N - 2]$

样例交互器按以下格式输出每个询问：

• 第 $1$ 行：? x

样例交互器按以下格式读取每个回答：

• 第 $1$ 行：$y$

样例交互器按以下格式输出猜测：

• 第 $1$ 行：! x