环上问题比较麻烦，考虑断环成链。
一个观察：如果起始位置不是最小值，那么最小值一定最后一个被取走。起始位置为最小值可以直接 \(\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\) 较大的那个。