eolymp
bolt
Try our new interface for solving problems

Robot

Time limit 2 seconds
Memory limit 128 MiB

You are participating in a robot programming contest. In the next competition, your robot has to pass through n points on a plane in a fixed order. However, your robot's path must satisfy the following requirements:

  • Each part of the path between two adjacent points must be either a line segment or a circular arc.

  • The whole path must form a smooth curve. In particular, it means that the directed tangents to adjacent parts of the path in their common point must coincide.

In order to win, you have to find a path for your robot which has the minimum possible length.

Input data

The first line contains a single integer n (2n1000), the number of points. Each of the next n lines contains two integers x[i] and y[i] not exceeding 10^6 by absolute value: the coordinates of the i-th point. The robot must visit these points in the order they are given in the input. Every two adjacent points are distinct. However, it is not guaranteed that all points in the input will be distinct.

Output data

Print one real number: the length of the shortest path. Your answer will be accepted if the absolute or relative error is no more than 10^(-6).

Examples

Input example #1
2
0 0
3 4
Output example #1
5.0000000000
Input example #2
5
1 0
0 1
-1 0
0 -1
1 0
Output example #2
6.2831853072
Source 2013 Petrozavodsk, MIPT contest, August 25, Problem B