All-zero versus exactly-one-marked search promise

For every integer $N\ge 1$, use the identity encoding of Input encoding and size for algorithmic tasks and let $P_N=\{0^N\}\cup \{e_i:1\le i\le N\}$, where $0^N$ is the all-zero string and $e_i$ has a $1$ exactly in coordinate $i$. This is a promise decision task in the sense of QA task and promise domain: its yes set is $\{e_i:1\le i\le N\}$, its no set is $\{0^N\}$, and its output is $\mathrm{OR}(x)$.

For the associated search task, set ${\mathrm{\ell }}_N=\lceil {\log }_2(N+1)\rceil$ and let ${\mathrm{bin}}_{{\mathrm{\ell }}_N}(k)$ be the length-${\mathrm{\ell }}_N$ binary expansion of $k$, most significant bit first and padded with leading zeros. Its promise domain is $P_N$ and its witness relation is $R_N=\{(0^N,{\mathrm{bin}}_{{\mathrm{\ell }}_N}(0))\}\cup \{(e_i,{\mathrm{bin}}_{{\mathrm{\ell }}_N}(i)):1\le i\le N\}\mathrm{.}$ The output labels none and $i$ mean these encoded strings for $0$ and $i$, respectively. The marked query address corresponding to $e_i$ is $j=i-1$ in Boolean oracle query model for search lower bounds. Verifying a measured candidate costs a separate query. No correctness condition is imposed outside $P_N$.