This problem can be solved with the sliding window technique.

The fundamental idea is to, for each point \(1,2,\ldots,N\), find the maximum \(M_i\) with \(i\leq M_i\leq N\) such that the distance from point \(i\) to point \(M_i\) is at most \(1\). The answer is \( (M_1-1)+(M_2-2)+\cdots+(M_N-N)\).

The important point is that \(M_1\leq M_2\leq \cdots \leq M_N\).
This is because when the distance from point \(i\) to points \(i+1,i+2,\ldots,M_i\) are all \(1\) or less, then the distance from point \((i+1)\) to points \(i+2, i+3,\ldots,M_i\) are all \(1\) or less.
Using this property, one can determine the value of \(M_i\) in the order of \(i=1,2,\ldots,N\) to reduce the number of questions by avoiding asking about pairs whose distance are already known to be \(1\) or less.

Specifically, we start from \(L=1,R=2\) and repeat the following operation:

• Ask if the distance between point \(L\) and point \(R\) is at most \(1\). Here, if \(L=R\), do not ask a question, but advance to the next step where the distance between points \(L\) and \(R\) is at most \(1\).
• If the distance between points \(L\) and \(R\) is at most \(1\), increase \(R\) by one, and advance to the next step. If it makes \(R>N\), determine \(M_L=M_{L+1}=\cdots=M_N=N\) and terminate the procedure.
• If the distance between points \(L\) and \(R\) is greater than \(1\), determine \(M_L=R-1\), and increase \(L\) by one. Here, by the fact mentioned above, note that the distances from the new point \(L\) to points \(L+1,\ldots,R-1\) are all \(1\) or below.

Here, \(L\) and \(R\) increases monotonically, or always \(L\leq R\). In one operation, \(L+R\) always increases by one, and once \(R>N\) the procedure terminates, so the loop iterates at most \((2N+1)-3=2N-2\) times. (In fact, one can prove that the number of queries is at most \((2N-3)\).)

Since you are allowed to ask a query to the judge system at most \(2N\) times, this satisfies the condition. The answer can be found in \(O(N)\) time based on \(M_1,M_2,\ldots,M_N\) obtained. Hence, the problem has been solved.

Sample code in 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;
}