I I solved it quickly not a long time ago, yet it tackles me now...
Let $k \in [n]$. How many permutations are in $S_n$ such that if $\sigma(i)=k$ then $\forall j<i\ \sigma(j)<k$, meaning $k$ is still the biggest element in the sequence up to it? Or - what is the probability to choose such a permutation, when chosen uniformly?
I know the answer is is $p=\frac{1}{n-(k-1)}$.
I tried to count it from different approaches, but I keep getting this sum: $\sum_{i=0}^k \frac{(k-1)!(n-i-1)!}{(k-1-i)!}$ which doesn't seem to be easy to calculate.
Paint the numbers $1,2,\ldots ,k-1$ white and the numbers $k,k+1,\ldots,n$ black. Then the specified permutations are precisely those in which $k$ is the earliest black number.
So to create any such permutation, we can arrange $k-1$ white beads and $n-k+1$ black beads in any order in a line, write $k$ on the leftmost black bead, and then choose a relative order first for the white numbers, and then for the remaining black numbers. The number of possible results is $$\binom{n}{k-1}(k-1)!(n-k)!=\frac{n!}{(n-k+1)}$$