尺取り法を用いてこの問題を解くことができます。

基本的な考え方としては、各点 \(1,2,\ldots,N\) について、点 \(i\) から点 \(M_i\) までの距離が \(1\) 以下であるような最大の \(i\leq M_i\leq N\) を求めることを考えます。答えは、\( (M_1-1)+(M_2-2)+\cdots+(M_N-N)\) となります。

ここで重要なことは、\(M_1\leq M_2\leq \cdots \leq M_N\) が成り立つことです。
これは、点 \(i\) から点 \(i+1,i+2,\ldots,M_i\) までの距離がすべて \(1\) 以下であるとき、点 \(i+1\) から点 \(i+2, i+3,\ldots,M_i\) までの距離は必ず \(1\) 以下となるためです。
このことを用いると、\(i=1,2,\ldots,N\) の順に \(M_i\) の値の探索を行うことで、すでに \(1\) 以下と判明している点の組についての質問を避けて質問の回数を削減することができます。

具体的には、\(L=1,R=2\) から初めて次の操作を繰り返し行います。

• 点 \(L\) と点 \(R\) の距離が \(1\) 以下かを質問する。ただし、\(L=R\) ならば（距離は \(0\) であるため、）質問を行うことなく、以下の 点 \(L\) と点 \(R\) の距離が \(1\) 以下の場合の手順へ移行する。
• 点 \(L\) と点 \(R\) の距離が \(1\) 以下ならば、\(R\) を \(1\) 増やし、次の操作を行う。ただし、\(R>N\) となったならば、\(M_L=M_{L+1}=\cdots=M_N=N\) として操作を終了する。
• 点 \(L\) と点 \(R\) の距離が \(1\) より大きいならば、\(M_L=R-1\) とし、\(L\) を \(1\) 増加させる。ここで、先に述べた事実より、新しい点 \(L\) と点 \(L+1,\ldots,R-1\) までの距離は \(1\) 以下であることが保証されることに注意する。

ここで、 \(L,R\) は操作の中で単調増加かつつねに \(L\leq R\) です。一度の操作で \(L+R\) は必ず \(1\) 増加し、\(R>N\) になり次第操作は終了することから操作を繰り返す回数は高々 \((2N+1)-3=2N-2\) 回となります。（さらに、実は質問を伴う操作の回数は \(2N-3\) 回以下となることが証明できます。）

ジャッジシステムへは \(2N\) 回まで質問を行うことができるため、問題ありません、答えの計算も求めた \(M_1,M_2,\ldots,M_N\) を用いて \(O(N)\) で求めることができるため、よってこの問題を解くことができました。

C++ による実装例:

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;

	cin>>n;

	int l=1,r=2,ans=0;
	string s;

	while(r<=n){
		cout<<"? "<<l<<" "<<r<<endl;
		cin>>s;
		if(s=="Yes"){
			r++;
		}
		else{
			ans+=(r-l-1);
			l++;
			if(l==r)r++;
		}
	}
	while(l<n){
		ans+=(r-l-1);
		l++;
	}
	
	cout<<"! "<<ans<<endl;
	return 0;
}