Still has no solution so i'll post a sketch: $f$ is injective so $f(n)\ge n$. Show $f(1)=1,f(2)=3,f(3)=4, f(4)=9$. We claim all functions are of the following form: 1. $f(1)=1,f(2)=3,f(3)=4,f(4)=9$ 2. We keep a pointer $a$, which starts at $3$. 3. Assign $f$ of $f(a)$ to be $a^2$, $f$ of $f(a+1)$ to be $(a+1)^2$. 4. For $f$ values of inputs between $f(a)$ and $f(a+1)$, assign them to be any strictly increasing sequence of integers between $a^2$ and $(a+1)^2$. 5. Increment the pointer by 1: $a\rightarrow a+1$. It is not easy but straightforward to verify that this always work (in particular, just bound $f(x+1)-f(x)\le 2x$ by induction) To get the largest and smallest values of $f(n)$, simply take the local greedy move at every step. I.e. when choosing the inputs in ranges, pick the smallest possible at every step (or largest). It is easy to see that this is the extremal values.