How to approach Vertical Sticks challenge

This problem is taken from interviewstreet.com

We are given an array of integers $Y=\{y_1,...,y_n\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y_i)$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, $v_1, ..., v_n$, where $v_i$ is equal to length of ray shot from the top of segment $i$. We define $V(y_1, ..., y_n)
= v_1 + ... + v_n$.

For example, if we have $Y=[3,2,5,3,3,4,1,2]$, then $[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$, as shown in the picture below:

For each permutation $p$ of $[1,...,n]$, we can calculate $V(y_{p_1}, ..., y_{p_n})$. If we choose a uniformly random permutation $p$ of $[1,...,n]$, what is the expected value of $V(y_{p_1}, ..., y_{p_n})$?

If we solve this problem using the naive approach it will not be efficient and run practically forever for $n=50$. I believe we can approach this problem by indepdently calculating the expected value of $v_i$ for each stick but I still need to know wether there is another efficient approach for this problem. On what basis can we calculate the expected value for each stick independently?

Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.

Returning to this problem, a particular stick is interested in how many sticks (including itself) are as high or higher. If this number is $k$, then the expected gap to its left is also $\frac{n+1}{k+1}$.

So the algorithm is simply to find this value for each stick and add up the expectation. For example, starting with heights of $[3,2,5,3,3,4,1,2]$, the number of sticks with a greater or equal height is $[5,7,1,5,5,2,8,7]$ so the expectation is $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$.

This is easy to program: for example a single line in R

V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

gives the values in the sample output in the original problem

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15

StackExchange Computer Science Q#1076, answer score: 25