$n\le10^6$

小A找到了一款游戏。

摆放在小A面前的是一串由 $n$ 个磁铁块组成的磁铁串，其中 $n$ 是奇数。每次小A可以从磁铁串中挑选任意两个连续的磁铁并拿走，直到只剩下一个磁铁。在小A拿走两个磁铁块后，由于磁铁的引力作用，剩下的两串磁铁会自动合并成一串。每个磁铁块都有一个权值 $a_i$，我们称答案为最后剩下的那块磁铁块的权值。

可怜的小A是精神分裂症患者。在第奇数次操作时，他想让最后的答案尽量大；而在第偶数次操作时，他想让最后的答案尽量小。请问小A经过如此操作若干次，最后的答案是多少？