Injectivity verification in o(n) space and O(n) time

Question

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $O(n)$ of hints, and I want an algorithm that will read $A$ and the oracle input (both read only) and determine either that $A$ has no duplicates, or that the oracle has given me a bad hint, in time $O(n)$ and much smaller read-write space ($O(1)$ or $O(\log n)$).

Can it be done?