双向取卡

核心观察

记 $q=\min(k-1,n-k+1)$。将原序列两端的元素配成 $q$ 对：第 $i$ 对是 $(a_{i},a_{n-i+1})$，其中 $1\le i\le q$。每一对最终恰好取走一个元素，而且每对取走哪一个都可以自由选择。

若 $2(k-1)\le n$，原位置 $k$ 至 $n-k+1$ 的中间元素会全部被取走；否则，两端配对以外的中间元素都无法被取走。

正确性证明

先考虑 $n\ge2k-1$。在中间区间未清空前，两端各 $k-1$ 个元素的位置保护使它们无法被取走，合法操作只会从中间区间的两端取走元素。因此中间元素全部被取走，并留下长度为 $2k-2$ 的两端序列。

此时，若还有未处理的最内侧一对，其左右元素正好分别处在当前从右数第 $k$ 个和从左数第 $k$ 个位置。取走其中一个后，另一个进入中间保护区域；两个可取位置随之移向下一对。已保留的元素位于两个可取位置之间，以后不会再被取走。归纳可知，各对由内到外处理，每对恰好取走一个，且选择互不限制。

若初始 $n<2k-1$，令 $q=n-k+1$。初始最内侧一对位于原位置 $q$ 与 $k$，恰好就是两个可取位置。中间的 $2k-n-2$ 个元素处在两个可取位置之间，始终受保护。沿用上述归纳，每次在当前最内侧的一对中任选一个取走，剩下一个受保护，然后处理下一对，直到全部 $q$ 对处理完。此时剩余恰好 $k-1$ 个元素。

因此，对每一对选择较大值，都能实际实现，且任何方案在该对的收益都不能超过它。加上必须取走的中间元素（若有），即得到最优答案。$k=1$ 时没有配对，全部元素都被取走，同样满足公式。

算法与复杂度

累加前 $q$ 对的较大值。若 $2(k-1)\le n$，再累加下标 $k$ 至 $n-k+1$ 的中间元素。时间复杂度为 $O(n)$，使用数组的空间复杂度为 $O(n)$。答案可能达到 $10^{14}$，实现应使用 64 位整数。