I was solving https://codeforces.net/problemset/problem/1265/E, but I misunderstood the problem and could not solve it. When I jumped to the editorial, I realized my mistake, and I quickly returned back to the problem, read the statement carefully, and pieced together the solution.

But I am still not able to solve my "misunderstood" problem. I pose that to you:

There are $$$n$$$ coins that turn up head with probabilities $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ ... $$$p_n$$$ respectively. A person starts cyclicly tossing coins – in the order 1, 2, 3 .... n, 1, 2, ... , i.e. after coin $$$n$$$, they toss coin $$$1$$$ again. They will stop when they have a streak of $$$n$$$ heads.

What is the expected number of coin tosses?

Constraint: $$$n <= 200,000$$$.

The Markov chain(s) that I am constructing to solve problem have $$$O(n^{2})$$$ edges – which is too large for the constraints. Can we do better?