Minimizing Binary Search Mismatch

You are given a positive integer n and a boolean array b = [b₁, b₂, ..., b_n] where each b_i is either true or false and n satisfies \(n=2^k-1\) for some positive integer \(k\). You are also provided with the following C++ function:

bool binary_search(int n, int p[], int target){
    int left = 1, right = n;
    while(left < right){
        int mid = (left + right) / 2;
        if(p[mid] == target)
            return true;
        else if(p[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if(p[left] == target) return true;
    else return false;
}

For any permutation p of \(\{1,2,\dots,n\}\), define the function \[ S(p)=\#\{ i \in \{1,2,\dots,n\} : binary_search(n, p, i) \neq b_i \}\]. Your task is to output a permutation p of \(\{1,2,\dots,n\}\) such that S(p) is minimized. In other words, for as many indices i as possible, the return value of binary_search(n, p, i) should equal bi as given in the input.

Note: It is guaranteed that \(n=2^k-1\) for some positive integer \(k\). There is no requirement to achieve the absolute minimum value of \(S(p)\); any permutation is acceptable as long as it adheres to the input/output format. A trivial solution is to output the identity permutation \(p=[1,2,\dots,n]\), which works correctly when all values in b are true.

inputFormat

The first line contains a positive integer n (\(n=2^k-1\) for some positive integer k).

The second line contains n space-separated tokens, each either true or false, representing b₁, b₂, ..., b_n.

outputFormat

Output a permutation p of \(\{1,2,\dots,n\}\) as n space-separated integers in one line. This permutation should aim to minimize \(S(p)\) as described in the problem.

sample

3
true true true

1 2 3