Limits 1.5s, 512 MB

Antman is in the quantum realm. He has nn orbits which are concentric and circular. These are called Schrödinger's orbits because whenever Antman observes orbit ii, exactly two points at random on this orbit become photon sources and a light ray emerges connecting these two sources.

A ray of light is called kk-bright if it comes in contact with exactly kk orbits.

It is 9:40 in the morning at CS427, and being late in statistics class Mahadi challenges Shamik with the following—

If Antman is currently observing orbit ii, what is the probability that a kk-bright light will emerge?

Shamik, not being a Marvel fan, claims the problem is so trivial that it is left as an exercise for the contestants.


The first line of input contains a single integer n  (1n105)n\;(1 \le n \le 10^5)— the number of orbits.

The second line contains nn integers r1,r2,,rn  (1ri109)r_1, r_2,…, r_n \;(1 \le r_i \le 10^9)— where rir_i is the radius of orbit ii.

The third line contains a single integer q  (1q5105)q\;(1 \le q \le 5\cdot10^5)— the number of queries to to answer.

Following each of the next qq lines contain two integers i  (1in)i\;(1 \le i \le n)and k  (0kn)k\;(0 \le k \le n)— the orbit in observation and the desired brightness of the light.

It is guaranteed that all rir_i are distinct.


For each query, print the desired probability in a single line.

Your answer is considered correct if its absolute or relative error doesn’t exceed 10610^{-6}.


239 77 169
2 3
1 1

There are infinitely many points in an orbit and there can be zero or infinitely many pairs of points that can produce a ray of light with our desired brightness.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.