How to choose a seed (binary search problem)?

Question

C++ / C#

Hello everyone, I have a task
https://codeforces.com/problemset/problem/1386/A
Screenshot of the conditions:

I understand that there you need to perform a binary search by difference, well, that is, from 1...n, but I can't choose a starting number.
The competition has already ended:

Available code:

#include <bits/stdc++.h>
using namespace std;
int main() {
  //IOS;
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long l = 0;// гарантировано не подходит
    long long r = n+1;// гарантировано не подходит
    long long last= //начальное число которое надо найти (придумать как-нибудь)
    long long ans = n;
    cout << "? " << last << endl;
    int a;
    cin >> a;
    while (r > l + 1) {
      long long m = (l + r) / 2;
      if (last + m <= n) {
        last += m;
      }
      else {
        if (last > m) {
          last -= m;
        }
      }
      cout << "? " << last << endl;
      int a;
      cin >> a;
      if (a) {
        r = m;
        ans = m;
      }
      else l = m;
    }
    cout << "= " << ans << endl;
  }
}

Thank you in advance.

Answer 1

It is not enough to choose only the first number and run the usual binary search. An important limitation is that you cannot use the same color twice. There is also a special effect that the cases c=n-1 and c=n can only be divided by repainting from 1 to n or vice versa. Those. you can't paint at 1 or n-1 unless you know for sure that C is less than n or that C is one of the two extremes.
We need to come up with some kind of pattern, how to compactly arrange all requests in the range from 1 to n without repetition.