环上问题比较麻烦，考虑断环成链。

一个观察：如果起始位置不是最小值，那么最小值一定最后一个被取走。起始位置为最小值可以直接 $\mathcal O(n)$ 模拟。下面将最小值旋转到下标 $n$，转化为 $[1,n-1]$ 上的序列问题。

这个问题与序列上的区间和数的大小有关，可以考虑建出笛卡尔树。具体地，建出小根堆的笛卡尔树，那么以 $x$ 为起始位置时，一定会先取走 $x$ 子树里的所有数，然后再取子树外的数。

先考虑子树外的贡献。可以发现如果已经取走 $x$ 子树内所有数，下一步一定是取走 $fa_x$，然后设 $fa_x$ 对应的区间为 $[l,r]$，若 $x$ 为 $fa_x$ 的左儿子（即对应区间为 $[l,x-1]$），接下来会从左往右取走 $[x+1,r]$ 内所有数；若 $x$ 为 $fa_x$ 的右儿子（即对应区间为 $[x+1,r]$），接下来会从左往右取走 $[x+1,r]$ 内所有数。这样问题就转化成立取走 $fa_x$ 子树内所有数的情况。故可以设 $f_{x,0/1}$ 表示已经取走 $x$ 子树内所有数，此时 JOI 是先/后手，他在剩下的数中会获得的数的总和。按照上面的过程从上往下 dp，容易发现只需要求一个子树（即序列上的区间）的大小的奇偶性和所有奇/偶下标的数之和。

再考虑子树内的贡献。为了方便，我们将这一部分放在序列上考虑。考虑从左到右和从右到左分别做一次单调栈，求出 $L_{i,1},L_{i,2},\dots,L_{i,m_i}$，其中 $L_{i,1}=i-1$，$a_{L_{i,j+1}}$ 为 $L_{i,j}$ 左边第一个比 $a_{L_{i,j}}$ 小的数，且 $a_{L_{i,j}}<a_i$ 当且仅当 $j=m_i$，同理求出右边的 $R_{i,1},R_{i,2},\dots,R_{i,k_i}$。根据单调栈的均摊有 $\sum_i(m_i+k_i)=\mathcal O(n)$。求出 $L,R$ 是基于这样一个观察：由于 $a_{L_{i,j}}$ 是区间 $(L_{i,j+1},L_{i,j}]$ 内的最小数，所以当 $L_{i,j}$ 被取走，这个区间内所有数都会紧接着从右往左被依次取走。注意 $L_{i,m_i}$ 和 $R_{i,k_i}$ 不在笛卡尔树上 $i$ 的子树内（即 $i$ 的子树对应的区间为 $[L_{i,m_i}+1,R_{i,k_i}-1]$）。所以只需要对 $L_{i,1\sim m_i-1}$ 和 $R_{i,1\sim k_i-1}$ 按照 $a$ 的从大到小进行归并即可求出 $g_i$ 表示从 $i$ 开始，取完 $i$ 的子树后 JOI 获得的数的总和。

设点 $x$ 的子树大小为 $s_x$，那么从 $x$（注意这里是旋转后的下标）开始的答案即为 $g_x+f_{x,s_x\bmod 2}+a_n\times(n\bmod 2)$。

使用线性建笛卡尔树算法可以做到总复杂度 $\mathcal O(n)$。

一种线性建笛卡尔树的算法（区别于最常见的一次单调栈）是发现点 $i$ 的父亲即为上面求出的 $L_{i,m_i}$ 和 $R_{i,k_i}$ 中 $a$ 较大的那个。

参考实现：

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
typedef unsigned long long ULL;
#define MP std::make_pair
#define fi first
#define se second
int read()
{
	int s = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) f ^= (c == '-');
	for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);
	return f ? s : -s;
} 
template<typename T> void write(T x, char end = '\n')
{
	if (x < 0) putchar('-'), x = -x;
	static int d[100]; int cur = 0;
	do { d[++cur] = x % 10; } while (x /= 10);
	while (cur) putchar(48 ^ d[cur--]);
	putchar(end);
}
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> void Fmax(T &x, T y){ if (x < y) x = y; }
template<typename T> void Fmin(T &x, T y){ if (y < x) x = y; }
const int MAXN = 300005;
int n, a[MAXN], dlt;
LL ans[MAXN], sum[MAXN][2], f[MAXN][2], g[MAXN];
void input()
{
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	dlt = std::min_element(a + 1, a + n + 1) - a;
	std::rotate(a + 1, a + dlt + 1, a + n + 1);
//	printf("------- %d --------\n", dlt);
//	for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
	ans[n] = a[n];
	for (int i = 2, l = 1, r = n - 1; i <= n; i++)
	{
		int v = a[l] >= a[r] ? a[l++] : a[r--];
		if (i & 1) ans[n] += v;
	}
	for (int i = 1; i <= n; i++)
		memcpy(sum[i], sum[i - 1], 2 << 3), sum[i][i & 1] += a[i];
}
int ch[MAXN][2], root;
LL query(int l, int r, int o){ return sum[r][o] - sum[l - 1][o]; }
void build()
{
	static int st[MAXN], tp;
	std::vector<int> L[MAXN], R[MAXN];
	st[tp = 0] = 0, a[0] = 0;
	for (int i = 1; i < n; i++)
	{
		while (a[st[tp]] > a[i]) L[i].push_back(st[tp--]);
		L[i].push_back(st[tp]), st[++tp] = i;
	}
	st[tp = 0] = n;
	for (int i = n - 1; i; i--)
	{
		while (a[st[tp]] > a[i]) R[i].push_back(st[tp--]);
		R[i].push_back(st[tp]), st[++tp] = i;
	}
	for (int i = 1; i < n; i++)
	{
		g[i] = a[i] + (n & 1) * a[n]; int c = 1;
		int l = 0, r = 0;
		while (l + 1 < L[i].size() || r + 1 < R[i].size())
			if (a[L[i][l]] > a[R[i][r]])
				g[i] += query(L[i][l + 1] + 1, L[i][l], (L[i][l] ^ c) & 1), c += L[i][l] - L[i][l + 1], l++;
			else g[i] += query(R[i][r], R[i][r + 1] - 1, (R[i][r] ^ c) & 1), c += R[i][r + 1] - R[i][r], r++;
		if (a[L[i].back()] > a[R[i].back()]) ch[L[i].back()][1] = i;
		else if (R[i].back() == n) root = i;
		else ch[R[i].back()][0] = i;
	}
}
void dfs(int x, int l, int r)
{
//	 printf("%d[%d,%d]: %lld %lld\n", x, l, r, g[x], f[x][(r - l + 1) & 1]);
	ans[x] = g[x] + f[x][(r - l + 1) & 1];
	int L = ch[x][0], R = ch[x][1];
	if (L)
	{
		for (int o : {0, 1})
			f[L][o] = query(x, r, (o ^ x) & 1) + f[x][(o ^ (r - x + 1)) & 1];
		dfs(L, l, x - 1);
	}
	if (R)
	{
		for (int o : {0, 1})
			f[R][o] = query(l, x, (o ^ x) & 1) + f[x][(o ^ (x - l + 1)) & 1];
		dfs(R, x + 1, r);
	}
}
int main()
{
//	freopen("1.in", "r", stdin);
	input();
	build();
	dfs(root, 1, n - 1);
//	for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " \n"[i == n]);
	for (int i = 1, x = n + 1 - dlt; i <= n; x = x % n + 1, i++) write(ans[x]);
	return 0;
}