408111: GYM102986 G Expected Distance

Your guests are not committed to a standardised order of sandwich assembly, and that makes it difficult to know which order to place each of the $$$n$$$ ingredients in on the sandwich bar. You have lots of other food related things to do, so you decide to just place the ingredients down according to your own preference, at arbitrary distinct locations on your table top. Now your guests will have to travel back and forth along the table placing ingredients in their preferred order.

Supposing that order preferences are indeed uniformly random amongst your guests (that is, each permutation of ingredients is equally likely to be the preference), and given the positions of each of the locations of the ingredients in the order you like in meters, what is the expected time a guest takes to assemble a sandwich? Each guest travels at one meter per second. Answer in seconds.

Each guest begins at the leftmost end of the table, at position $$$0$$$, and exits the sandwich bar at the rightmost end, position $$$W$$$, where $$$W$$$ is the width of the table. Each guest takes every ingredient in exactly the order they prefer.

The first line contains two numbers $$$n, W$$$ with $$$1\le W\le 10^5$$$ and $$$1\le n< \min\{10^5, W\}$$$, respectively, the number of sandwich ingredients and the width of the table.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2,\cdots, a_n$$$ with $$$0 < a_i< W$$$ for each $$$i$$$. $$$a_i$$$ is the location in meters of the ingredient that you personally like to place at the $$$i$$$th position of your sandwiches.

Every guest travels at $$$1$$$ meter per second.

Output a single number that is the expected time in seconds for a random guest to collect the ingredients of their sandwich in the order they desire.

3 4
2 3 1

6.66666666666667

3 12
6 7 5

14.6666666666667