Finite-cyclic discrete logarithms

Suppose $G=\langle g\rangle$ is a finite cyclic group of known order $N$, and an element $x\in G$ satisfies $x=g^r$ for a unique $r\in\{0,\ldots,N-1\}$. Let $n = \lceil\log_2 N\rceil$. Given access to an oracle $U_x$ such that $U_x\ket{a,b,y}=\ket{a,b,y\,g^a x^{-b}}$, there exists a quantum algorithm that outputs $r$ with success probability at least $2/3$, using one query to $U_x$, $3n$ qubits, $2n$ Hadamard gates, $n(n-1)$ controlled-phase gates, $2\lfloor n/2\rfloor$ SWAP gates, maximal circuit depth $1+2n+n(n-1)+2\lfloor n/2\rfloor$, and $7$ classical arithmetic operations.