Subtask #1

这个点，随便乱问都能过好吧。
可以考虑每次 $n^2$ 遍，确定每个数的大小关系。然后输出最大的就没了。

Subtask #2

稍微想想性质，就会发现加操作最多只会改变 $2$ 个相邻的大小关系，并且每次操作完之后最大值只有可能出现在操作区间右端点或操作区间左端点减一，以及之前的某个最大值可能点。到第 $m$ 次询问时，一共会有 $2m$ 个最大值可能点，挨个问一遍，找出最大的即可。

Subtask #3

发现操作是区间操作且询问是区间操作，所以考虑线段树维护区间最大值位置。建树时比较简单，区间最大值位置一定在最右边。修改操作时，假装修改，只在 pushup 时询问两边最大值的大小关系，一次操作最多只会查询 $2\log n$ 次，如下代码：

void change(int k,int l,int r){
	if(x<=l&&r<=y)return;//假装进行了修改
	if(x<=mid)change(ls,l,mid);
	if(y>mid)change(rs,mid+1,r);
	s[k]=ask(s[ls],s[rs])?s[ls]:s[rs];//在pushup时询问
}

但是这样做大概率会 TLE 一个点（除非你比较会卡常），因此需要加上一个剪枝：

void change(int k,int l,int r){
	if(x<=l&&r<=y)return;
	int lns=s[ls],rns=s[rs];
	if(x<=mid)change(ls,l,mid);
	if(y>mid)change(rs,mid+1,r);
	if(x<=s[ls]&&s[rs]<=y&&lns==s[ls]&&rns==s[rs])return;
	//如果上次查询的最值在修改范围内时，不需要查询
	else s[k]=ask(s[ls],s[rs])?s[ls]:s[rs];
}

完整代码：

#include<bits/stdc++.h>
#define ll long long
#define gc getchar
#define pc putchar
#define sc scanf
#define pr printf
#define fu(v,s,e) for(int v=s;v<=(e);v++)
#define fd(v,s,e) for(int v=s;v>=(e);v--)
#define ciallo cerr<<"Ciallo~\n"
#define fuck cerr<<"Fuck you\n"
#define ___ cerr<<"----------------\n"
#define ___2 cerr<<"================\n"
#define mem(a,x) memset(a,x,sizeof(a))
#define itn int
#ifdef DEBUG
#define debug(...) __VA_ARGS__
#else
#define debug(...)
#endif
using namespace std;
#ifdef INFO
struct __info{~__info(){cerr<<'\n';___;cerr<<"Time: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";FILE* mem=fopen("/proc/self/status","r");char str[128];while(fgets(str,128,mem)!=NULL) if(strncmp(str,"VmRSS:",6)==0){cerr<<"Memory: "<<atoi(str+6)/1024.0<<" MB.\n";break;}}}_info_tmp;
#endif
inline int in(){char c=gc();int x=0,f=1;while((c<'0'||c>'9')&&c!='-') c=gc();if(c=='-') f=-1,c=gc();while(c>='0'&&c<='9') x=x*10+c-'0',c=gc();return x*f;}
int n,m,k;
int tr[400005];
#define lc (i<<1)
#define rc (lc|1)
void build(int i,int l,int r){
    tr[i]=r;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lc,l,m);
    build(rc,m+1,r);
}
void modify(int i,int l,int r,int L,int R){
    if(L<=l&&r<=R) return;
    int m=(l+r)>>1;
    itn tlc=tr[lc],trc=tr[rc];
    if(L<=m) modify(lc,l,m,L,R);
    if(R>m) modify(rc,m+1,r,L,R);
    if(tr[lc]==tlc&&tr[rc]==trc&&((tlc<L&&trc>R)||(tlc>=L&&trc<=R))) return;    //剪枝
    pr("? %d %d\n",tr[lc],tr[rc]);
    fflush(stdout);
    int res=in();
    if(res) tr[i]=tr[lc];
    else tr[i]=tr[rc];
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=in(),m=in(),k=in();
    build(1,1,n);
    while(m--){
        int l=in(),r=in();
        modify(1,1,n,l,r);
        pr("! %d\n",tr[1]);
        fflush(stdout);
    }
    return 0;
}