33279번 - 특식 배분 스페셜 저지

문제

하늘이네 부대에 설날 특식으로 간식 $N$개가 지급되어 이를 각 생활관에 배분하려고 한다.

간식은 먼저 도착한 생활관부터 차례대로 가져간다. 그러나 앞 순서에서 너무 많이 가져가면 안 되기 때문에 각 생활관마다 수령할 간식의 수를 각각 무작위로 정하기로 했다.

더 구체적으로, 현재 차례에 간식이 $i$개 남아있다고 할 때 1ドル$ 이상 $K_i$ 이하의 정수 중 하나를 무작위로 정하여 그 개수만큼 가져가기로 했다. 즉, 지금 도착한 생활관이 수령할 간식의 개수는 1ドル$부터 $K_i$까지 확률이 $\frac{1}{K_i}$로 동일하다.

하늘이는 이러한 방식으로 특식을 배분하면 얼마나 많은 생활관이 간식을 수령할 수 있는지 궁금해졌다. 간식을 수령할 수 있는 생활관의 수의 기댓값을 구하시오.

입력

첫째 줄에 $N$이 주어진다. $(1\le N\le 100,000)$

둘째 줄에 $K_1,K_2,\cdots ,K_N$이 공백을 사이에 두고 주어진다. $(1\le K_i\le i;$ 1ドル\le i\le N)$

출력

첫째 줄에 간식을 수령할 수 있는 생활관의 수의 기댓값을 출력한다.

정답과의 절대오차 혹은 상대오차가 10ドル^{-6}$ 이하이면 정답으로 인정된다.

제한

힌트