The key piece of information turns out to be that $$$A[1] = 0$$$ and $$$A[n] = 1$$$. If we didn't have this, linear is the best we can do. One way to interpret this info is that at some point between $$$1$$$ and $$$n$$$, we switch from $$$0$$$ to $$$1$$$. As a result, we can check the index $$$m$$$ that's half-way between $$$1$$$ and $$$n$$$.

If $$$A[m]=0$$$, then we can repeat the argument and see that we must switch from $$$0$$$ to $$$1$$$ at some point between $$$m$$$ and $$$n$$$. So, we can solve the problem in the right half. Similarly, if $$$A[m]=1$$$, then we must switch from $$$0$$$ to $$$1$$$ at some point between $$$1$$$ and $$$m$$$. We may then solve the problem in the left half.

The code turns out to be very simple. The exit condition (r - l) > 1 makes us continue until l and r are consecutive.

int l = 1;
int r = n;

while ((r - l) > 1) {
    int m = midpoint(l, r);
    if(A[m]) r = m;
    else l = m;
}

Notice that before the loop starts and after every iteration, we know:

• A[l] = 0
• A[r] = 1
• l < r

This ensures that we've found a solution.

We'll apply our binary search technique of non-monotone predicates to this CSES problem. Let's imagine arranging the chairs in a line. First, notice that there will always be two adjacent chairs with the same colour (this has to do with the $$$n$$$ being odd condition). Next, we'll reduce the problem down to being on an array instead of a circle. Specifically, notice that we may assume chair $$$1$$$ and chair $$$n$$$ have different colours. If they have the same colour, then we may return $$$n$$$.

After making this reduction, it turns out that the problem is equivalent to having an array $$$A$$$ of odd-length containing integers $$$0$$$ and $$$1$$$ such that $$$A[1]\neq A[n]$$$, and we want to find consecutive indices $$$1\leq i \lt j\leq n$$$ such that $$$A[i] = A[j]$$$. Do you see how similar this is to our original motivating problem? The only difference is that we wanted $$$A[i]\neq A[j]$$$ (in particular $$$A[i]=0$$$ and $$$A[j]=1$$$), and we knew $$$A[1] = 0$$$ and $$$A[n] = 1$$$. An easy way to fix the former is to consider parity (even or odd) in our predicate. We'll do this using the XOR operation: $$$\bigoplus$$$. We can try: $$$P(i) : A[i] \bigoplus (i \% 2)$$$ However, we want $$$P(1) = 0$$$ and $$$P(n) = 1$$$. So, to fix that we can instead consider: $$$P(i) : A[i] \bigoplus 1 \bigoplus A[1] \bigoplus (i \% 2)$$$. It's not hard to see that $$$P(1) = 0$$$ and $$$P(n) = 1$$$ because we note that $$$A[1] \neq A[n]$$$ by our earlier reduction. Now, the implementation is easy.

#include <bits/stdc++.h>
using namespace std;

int get(int i){
    cout << "? " << i << endl;
    char c;
    cin >> c;
    return c == 'R';
}
 
void answer(int i){
    cout << "! " << i << endl;
}
 
int main(){
    int n;
    cin >> n;
 
    // first, we determine if the first and last chairs are the same colour
    int c1 = get(1);
    int cn = get(n);
    if(c1 == cn){
        answer(n);
        return 0;
    }
    
    // otherwise, we binary search on our predicate
    auto P = [&](int i) -> int {
        return get(i) ^ 1 ^ c1 ^ (i % 2);
    };
 
    // template binary search
    int l = 1;
    int r = n;
 
    while((r - l) > 1){
        int m = midpoint(l, r);
        if(P(m)) r = m;
        else l = m;
    }
 
    // now, P(l) = 0 and P(r) = 1 (and they're one apart)
    // so we can report l
    answer(l);
}

The main idea of the meet in the middle problem above is that we're able to calculate the following function in $$$\mathcal O(n2^{n/2})$$$: $$$S(i)$$$ which equals the number of non-empty subsets (of the given set) whose sum is $$$i$$$. After implementing this, you may realize that after an $$$\mathcal O(n2^{n/2})$$$ preprocessing step, we're able to not only calculate $$$S(i)$$$ in $$$\mathcal O(2^{n/2})$$$ time, but we can also calculate the function $$$S(\leq i)$$$: which equals the number of non-empty subsets whose sum is at most $$$i$$$. This function will be used in our predicate.

Recall that by definition, we have: $$$S(\leq 2^n-2)=2^n-1$$$. In particular, $$$S(\leq 2^n-2) \gt 2^n-2$$$. This was the reason we're guaranteed to have two subsets with the same sum. Generalizing, observe that if $$$S(\leq i) \gt i$$$, then there must exist two subsets that both sum to the same value which is at most $$$i$$$. This inspires us to make our predicate: $$$P(i): S(\leq i) \gt i$$$. Indeed, if we have consecutive $$$i$$$ and $$$j$$$ such that $$$P(i)=0$$$ and $$$P(j)=1$$$, we can prove that there exist two subsets summing to $$$j$$$. Note:

Therefore, we may use binary search on this problem. We set $$$\ell=0$$$ since $$$P(0)=0$$$, and we set $$$r=2^n-2$$$ as $$$P(2^n-2)=1$$$. Also, since $$$\log(r-\ell) \lt \log(2^n)=n$$$, the complexity of this step will be $$$\mathcal O(n2^{n/2})$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// compute the sum of every subset of the input vector, and return it in sorted order
vector<ll> all_sums(vector<ll>a){
    int n = a.size();
    vector<ll>sums(1 << n);
    for(int i=0; i<1<<n; i++){
        for(int j=0; j<n; j++)
            sums[i] += a[j] * (1 & (i >> j));
    }
    sort(sums.begin(), sums.end());
    return sums;
}

int main(){
    int n;
    cin >> n;

    // split the input into two arrays as in the meet in the middle technique
    vector<ll> v1, v2;
    for(int i=0; i<n; i++){
        ll v;
        cin >> v;
        if(i&1) v1.push_back(v);
        else v2.push_back(v);
    }

    auto s1 = all_sums(v1), s2 = all_sums(v2);

    // define our S(<= m) function with 2-pointers
    auto S = [&](ll m) {
        ll s = 0;
        int j = s2.size() - 1;
        for(int i=0; i<s1.size(); i++){
            while(j >= 0 && s1[i] + s2[j] > m) j--;
            s += j+1;
        }
        return s - 1; // subtract the empty set
    };

    auto P = [&](ll i) {
        return S(i) > i;
    };

    // template binary search
    ll l = 0;
    ll r = (1ll << n) - 2;
 
    while((r - l) > 1){
        ll m = midpoint(l, r);
        if(P(m)) r = m;
        else l = m;
    }

    cout << r << '\n';
}