You can store the data in an array and apply each fetch by moving the ith element to the end of the array (i.e, O(n) per operation).
A better way is to use the square root decomposition technique.
You can build chunks of size sqrt(n). For each fetch operation, You can search for the chunk which has the ith element and update it (i.e., O(sqrt(n)) per operation), and move this element to an empty chunk at the end.