시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 2 2 100.000%

문제

질량이 mi, 길이가 2, 높이가 h인 직사각형이 N개가 있다. 이 직사각형은 2차원 평면에 다음과 같이 쌓여져 있다.

  • 직사각형의 변은 모두 축에 평행하다.
  • 직사각형 아랫변의 y좌표는 모두 다르고, 다음이 0, h, 2h, 3h, ..., (N-1)h값을 갖는다.
  • 가장 아래에 있는 직사각형의 왼쪽 아래 좌표는 (-2,0)이고, 오른쪽 아래의 좌표는 (0,0)이다.

직사각형의 x중심은 아랫변의 중점이다.

하나 또는 그 이상 직사각형의 무게중심은 직사각형의 x좌표와 무게를 이용해서 아래와 같이 계산할 수 있다.

각 직사각형 A보다 위에 있는 직사각형의 무게중심과 A의 x중심의 거리가 많아야 1이 되도록 직사각형을 쌓는다면, 안정한 쌓기라고 한다.

직사각형을 안정하게 쌓는다면, 직사각형은 무너지지 않을 것이다. 왼쪽 그림은 안정한 배치가 아니다. 그 이유는 가장 위의 두 직사각형의 무게중심과 바로 아래있는 직사각형의 x중심의 거리가 1을 넘기 때문이다. 오른족 그림은 안정한 쌓기이다.

모든 직사각형의 질량이 주어졌을 때, 모든 직사각형의 꼭지점 중 가장 오른쪽에 있는 꼭지점이 크게 쌓는 방법을 구하는 프로그램을 작성하시오. 이 때, 직사각형은 안정한 쌓기이어야 하고, 입력으로 주어진 순서대로 쌓아야 한다.

입력

첫째 줄에 직사각형의 개수 N이 주어진다. (2 ≤ N ≤ 300,000)

다음 N개 줄에는 직사각형의 질량이 아래 직사각형부터 위 직사각형까지 순서대로 주어진다. 질량은 10,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 안정하게 쌓는 방법 중에서 가장 오른쪽 꼭지점이 클 때의 오른쪽 꼭지점의 x좌표를 출력한다. 정답과의 오차는 0.000001까지 허용한다.

예제 입력

2
1
1

예제 출력

1.000000

힌트