First, assume \(N\) is even.

If we drop the adjacency requirement and may remove any two elements each time, the maximum possible total score is the sum of the larger \(\frac{N}{2}\) elements of \(A\) minus the sum of the smaller \(\frac{N}{2}\) elements.

This theoretical upper bound can still be achieved even with the adjacency constraint.

Replace the larger \(\frac{N}{2}\) elements of \(A\) by the symbol + and the smaller \(\frac{N}{2}\) elements by -, obtaining a string \(S\). For example, for \(A=(3,1,4,1,5,9)\), \(S\) is --+-++. Any string containing at least one - and one + has at least one position where - and + are adjacent, so we can repeatedly delete an adjacent -/+ pair \(\frac{N}{2}\) times.

Now, consider odd \(N\).

Fix which one element will remain to the end. Because the two parts on either side of this element must both have even length, the survivor must be one of \(A_1, A_3, A_5,\dots,A_N\). For each candidate survivor, we need to compute, for the left and right even‑length subsequences, the sum of larger half minus the sum of smaller half. This can be done efficiently with a data structure that supports insertion into a multiset and maintenance of its median. For example, you can use two priority queues or a BIT.

The overall complexity is \(O(N\log N)\).