E. Water Balance--------------------------思維(貪心)難

There are n water tanks in a row, i-th of them contains ai liters of water. The tanks are numbered from 1 to n from left to right.

You can perform the following operation: choose some subsegment [l,r] (1≤l≤r≤n), and redistribute water in tanks l,l+1,…,r evenly. In other words, replace each of al,al+1,…,ar by al+al+1+⋯+arr−l+1. For example, if for volumes [1,3,6,7] you choose l=2,r=3, new volumes of water will be [1,4.5,4.5,7]. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence a is lexicographically smaller than a sequence b of the same length if and only if the following holds: in the first (leftmost) position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input

The first line contains an integer n (1≤n≤106) — the number of water tanks.

The second line contains n integers a1,a2,…,an (1≤ai≤106) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.

Output

Print the lexicographically smallest sequence you can get. In the i-th line print the final volume of water in the i-th tank.

Your answer is considered correct if the absolute or relative error of each ai does not exceed 10−9.

Formally, let your answer be a1,a2,…,an, and the jury’s answer be b1,b2,…,bn. Your answer is accepted if and only if |ai−bi|max(1,|bi|)≤10−9 for each i.

Examples

inputCopy

4

7 5 5 7

outputCopy

5.666666667

5.666666667

5.666666667

7.000000000

inputCopy

5

7 8 8 10 12

outputCopy

7.000000000

8.000000000

8.000000000

10.000000000

12.000000000

inputCopy

10

3 9 5 5 1 7 5 3 8 7

outputCopy

3.000000000

5.000000000

5.000000000

5.000000000

5.000000000

5.000000000

5.000000000

5.000000000

7.500000000

7.500000000

Note

In the first sample, you can get the sequence by applying the operation for subsegment [1,3].

In the second sample, you can’t get any lexicographically smaller sequence.

題意:

給定n個數，每次可以選取一段區間[l,r]，使得[l,r]之間的數都變成[l,r]區間之和/區間長度。

問最小的字典序。

解析:

假設現在存在兩塊區域的平均數 第一塊平均數為x1,第二塊為x2。題目要求是最小的字典序。我們可以貪心選擇，如果下一個數是y，且<x2 那麼把y加入到第二塊區域中，平均數x2就會減，假設把y加入到x2的結果為B2，然後B2要和x1去比較了 如果B2<x1 那麼x1這塊區域的平均數也要變小

貪心選擇小于平均數。加入進來後，去更新一下後面的平均數。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1000;
double a[N],st[N],len[N];
int n;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lf",&a[i]);
	int p=0;
	for(int i=0;i<n;i++) 
	{
		st[++p]=a[i];len[p]=1;//st[i]儲存平均數，len儲存st[i]這個平均數有多少個數 
		while(p>1&&st[p]<st[p-1])//更新後面的數
		{
			st[p-1]=(st[p]*len[p]+st[p-1]*len[p-1])/(len[p]+len[p-1]);
			len[p-1]+=len[p];//更新長度，因為又多了一部分進來
			p--;
		}
	}
	for(int i=1;i<=p;i++) //一共p塊區域
	{
		for(int j=1;j<=len[i];j++) //每塊區域的個數
		printf("%.8lf\n",st[i]);
	}
}