The constraints are low enough for a brute force, single array approach.

For an O(1) per method approach, use 2 double-ended queues: one for the first half and one for the second half.