Rényi–Berlekamp–Ulam searching game with bi-interval queries and two lies

We consider the following searching game: there are two players, say Questioner and Responder. Responder chooses a number x∈Sn={1,2,…,n}x∈Sn={1,2,…,n}, Questioner has to find out the number xx by asking bi-interval queries   and Responder is allowed to lie at most two times throughout the game. The minimal number q∗(n)q∗(n) of bi-interval queries sufficient to find the unknown integer xx is determined for all integers nn. This solves completely Rényi–Berlekamp–Ulam searching game with bi-interval queries and two lies, partially solved by Mundici and Trombetta. Their solution applied only to the case when nn is a power of 2.