Amplitude estimation

Let $0<\epsilon\leq1$, $0<\eta\leq1$, $n_a=\lceil\log_2(\pi/(\epsilon\eta))\rceil$, $k=2^{n_a}-1$ and $0<p<1$ such that $p(1-p)=\Omega(1)$. Consider an $n$-qubit state-preparation oracle $U$ such that $U\ket{0}=\sqrt{p}\ket{\psi_1}+\sqrt{1-p}\ket{\psi_0}$, and a reflection oracle $R_1=I-2\ket{\psi_1}\!\bra{\psi_1}$ for some orthogonal states $\ket{\psi_0}$ and $\ket{\psi_1}$. Given access to $U$, $U^\dagger$ and controlled-$R_1$, there exists a quantum algorithm that estimates $p$ to precision $\epsilon$ with failure probability at most $\eta$, using at most $n+n_a$ logical qubits, $k+1$ queries to $U$, $k$ queries to $U^\dagger$, $k$ queries to controlled-$R_1$, and the following gate counts: $$ \begin{array}{c|ccc} n & \text{Toffoli gates} & \text{CNOT gates} & \text{Single-qubit gates} \\ \hline 1 & 0 & n_a(n_a-1)+3\lfloor n_a/2\rfloor+k & n_a(3n_a+1)/2+2k \\ 2 & k & n_a(n_a-1)+3\lfloor n_a/2\rfloor & n_a(3n_a+1)/2+7k \\ 3 & 4k & n_a(n_a-1)+3\lfloor n_a/2\rfloor & n_a(3n_a+1)/2+9k \\ 4 & 10k & n_a(n_a-1)+3\lfloor n_a/2\rfloor & n_a(3n_a+1)/2+11k \\ n\geq5 & 8(n-3)k & n_a(n_a-1)+3\lfloor n_a/2\rfloor & n_a(3n_a+1)/2+(2n+3)k \end{array} $$