题目背景

本题对洛谷交互格式进行了适配，你可以在以下代码的基础上进行实现：

#include<bits/stdc++.h>
using namespace std;
extern "C" bool ask(int x);
extern "C" int solve(int n,vector<int> p)
{
  	assert(ask(1)==1);
	return 20080520;
}

题目描述

这是一道交互题。

给定一棵 $N$ 个点的有根二叉树 $T$，保证根结点的编号为 $1$。

树上恰有一个未知的结点是特殊的，你需要找出这个结点。

你每次可以向交互库询问一棵子树中是否含有特殊结点，你可以询问至多 $35$ 次。

【实现细节】

你需要实现下列函数：

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

• $N$：树的结点数量。
• $p$：长度为 $N-1$ 的数组，描述树的形态。第 $i$ 个元素 $p_i$ 满足 $1\leq p_i\leq i+1$，代表编号为 $i+2$ 的结点的父亲编号。
• $p$ 中的元素两两不同。
• 你需要返回特殊结点的编号。
• 这个函数只会被调用恰好一次。

你可以调用以下函数：

int ask(int x)

• $x$：询问的子树根结点编号。
• 你需要保证 $1\leq x\leq N$。
• 如果子树包含特殊结点，返回值为 $1$，否则为 $0$。

输入格式

以下为下发 grader 的输入格式，你不应该从标准输入中读入任何信息。

第一行输入一个整数 $N$。

第二行输入 $N-1$ 个整数 $p_i$。

接下来对于每个询问，输入一个整数代表询问的返回值。

输出格式

以下为下发 grader 的输出格式，你不应该向标准输出中打印任何信息。

对于每个询问，输出一行 ? x，其中 $x$ 为询问的结点。

最后输出一行 ! x，其中 $x$ 为猜测的结点编号。

5
1 1 2 4

1

0
 

 

? 4

? 5

! 4

提示

【数据范围】

本题采用捆绑测试。

• Subtask 1（20 pts）：$N\leq 35$。
• Subtask 2（30 pts）：$p_i=i+1$。
• Subtask 3（15 pts）：$p_i=\frac{i}{2}+1$。
• Subtask 4（35 pts）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\leq N\leq 10^5$。