Let $f^*(k)$ be the optimal payment outcome given that Bessie starts at the point $k$. We know that $f^*(k) = \max\left(f(k), \frac{f^*(k-1) + f^*(k+1)}{2}\right)$. However, the most straightforward ways of solving such a system require inverting matrices, which takes $O(n^3)$ time, nowhere near fast enough. We need to find a faster way by understanding the structure of the problem better.

Let's consider another straightforward algorithm:

• Initialize $g(k) = f(k)$ for every $k$.
• Repeat as long as we can: Find a $k$ such that $g(k) < \frac{g(k-1) + g(k+1)}{2}$, and set $g(k) = \frac{g(k-1) + g(k+1)}{2}$.

After we're finished (we can't find any more $k$ to improve), we simply output the value of $g(k)$ for each $k$.

In other words, we are defining $g(k)$ to be the best payment outcome starting at position $k$ that we can find, so far. The question is, after this process is finished, can we guarantee that each $g(k) = f^*(k)$?

The key insight is to visualize this problem on a 2D coordinate axis. If we plot each point as $(k, f(k))$, then this process will give us the upper convex hull of all these points. Taking into the properties of convex hulls, it becomes more clear that this process always gives the correct answer: the value of $f^*(k)$ for any $k$ is always equal to the weighted average of points within the hull, and so this value must also be within the upper hull.

Using our favorite convex hull algorithm, we simply find the upper hull of all the points $(k, f(k))$, and output the y-value along the hull for each possible value of $k$ from $1$ to $N$. This takes $O(N \log N)$ time overall.

Here's Dhruv's code. Note that the computation is done entirely in integers, to avoid precision issues:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define MAXN 100000
 
int N;
long long f[MAXN+2];
int l[MAXN+2];
int r[MAXN+2];
 
int main()
{
	cin >> N;
	for(int i=1;i<=N;i++)
		cin >> f[i];
	f[0] = f[N+1] = 0;
	vector<int> hull;
	hull.push_back(0);
	for(int k=1;k<=N+1;k++)
	{
		while(hull.size() >= 2)
		{
			int i = hull[hull.size()-2];
			int j = hull[hull.size()-1];
			if((k-i)*f[j] < (j-i)*f[k] + (k-j)*f[i])
				hull.pop_back();
			else
				break;
		}
		hull.push_back(k);
	}
	for(int j=0;j<hull.size()-1;j++)
	{
		for(int i=hull[j]+1;i<hull[j+1];i++)
		{
			l[i] = hull[j];
			r[i] = hull[j+1];
		}
		l[hull[j]] = r[hull[j]] = hull[j];
	}
	l[N+1] = r[N+1] = N+1;
	for(int i=1;i<=N;i++)
	{
		if(l[i]==r[i]) cout << 100000LL*f[i] << '\n';
                else cout << (100000ULL*(((unsigned long long)(r[i]-i))*((unsigned long long)f[l[i]]) + ((unsigned long long)(i - l[i]))*((unsigned long long)f[r[i]])))/((unsigned long long)(r[i]-l[i])) << '\n';
        }
	return 0;
}