You are given a linked list of size $n$. An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed is at index $i$ and it belongs to a list of size $n$. Once an index $i$ is accessed, the list is broken into two lists. One list contains the first $i$ elements and the second list contains the rest of the elements. It has something to do with cartesian trees, but I am not clear how to proceed with this chain of thought.
Show that the total cost incurred to access all the elements is any arbitrary order is $O(n)$.