Consider an ordered permutation of $n$ integers $\lbrace a_1,a_2,\ldots,a_{n} \rbrace$. Define a sandwich to be a pair $(a_i,a_j)$ such that $a_i,a_j > a_{i+1},a_{i+2},\ldots,a_{j-1}$. Find the minimum and maximum possible number of sandwiches among all the permutations of the first $n$ positive integers. Note that any two adjacent elements are counted as a sandwich.
For example, in the set $\lbrace 5,1,2,3,4 \rbrace$, $(5,4)$ is a sandwich as $5,4 > 1,2,3$. I have already found that the minimum occurs when all the numbers are consecutive, but I am not sure how to optimize the maximum.
Let's arrange the $n$ integers on a circle as the $n$ vertices of a $n$-sided polygon. We will draw an edge between two vertices whenever two vertices form a sandwich. This edge will go through the interior of the polygon.
Let $a<b<c<d$. It is impossible to have $(a, c)$ and $(b,d)$ as sandwiches. This means that no two edges can cross. Thus we can't have more sandwiches than edges in a polygon triangulation, which is $2n-3$.
The bound is attained by the permutation $(n, 1, 2, 3, ..., n-1)$