403183: GYM101063 A Giant Snail Maze

It is the year of 2016 and Mars is still not colonized. A daring group of immortal, rich explorers based in São Carlos decided that it is about time to do something about it, so they founded a space exploration company called GEMA - Go Explore Mars Already!

Fast forward to 2017. The first mission of GEMA has finally landed on Mars, but it seems like the rocket fell in the middle of some ancient ruins that form a giant maze resembling a snail. The maze is composed of N circular sectors all centered at the crash site of the rocket.

The circular sectors of the maze all have a railway running through their middle, and some portions of the walls are open, making it possible to leave to the next sector. The rails connecting sectors are straight, radial lines through the opening, connecting the rails of the two sectors. There is always a straight line connecting the crash site to the first sector railway through the openings. The only safe way to travel in this maze is by using these rails.

The crew of the GEMA mission wants to leave the maze as soon as possible. Luckily, they are in possession of small carts that fit the railway. Help them find the path with the minimum length to leave the maze. You are out of the maze as soon as you cross the boundary of the outermost wall.

The above figure illustrates the first sample test case. Dashed lines represent the railways that run through the middle of the sectors, whose boundaries are represented by solid circles. The best solution in this case is to go from points A, B, C, D and then E, going through the sectors railways through points X, Y, W and Z, as indicated by the green line.

The input begins with an integer N (1 ≤ N ≤ 10⁵), the number of circular sectors of the Snail Maze. The next line has N integers r, the radius of each of the sectors (1 ≤ r ≤ 10⁹). The next line contains an integer Q (N ≤ Q ≤ 10⁵), the number of openings. The next Q lines contains an integer and a real number each. The first integer, r_i (1 ≤ r_i ≤ 10⁹) gives the radius of a wall (that radius will be one of the N numbers given in the second line), and the real number d, gives the angle, in radians, where the opening is located (0 ≤ d ≤ 2π). The angle is measured in clockwise direction with respect to west (the positive x-axis).

It is guaranteed that there is a path to leave the maze, i.e., every wall has at least one opening. There will not be two openings closer than 10^- 4 radians.

Output the length of the shortest path to leave the maze. Your answer will be considered correct if its absolute or relative error does not exceed 10^- 6.

3
4 10 6
4
4 1.0472
4 1.5707
6 4.7123
10 4.1857

27.30323