# Algorithm for maximizing the number of pairs removed from a sorted sequence under a dubling condition

Given a non-decreasing sequence of $$n$$ positive integers $$a_1 \leq a_2 \leq \dots \leq a_n$$, we are allowed to modify this sequence by performing the following operation: we select two elements $$a_i, a_j$$ satisfying $$2a_i \leq a_j$$ and remove both of them from the sequence. The goal is to find an algorithm that calculates the maximum number of elements that can be removed from the sequence using this operation.

I believe that an effective algorithm for this problem might be one that compares elements from the beginning of the sequence with elements from the middle, but I am struggling to prove its optimality. If anyone has any suggestions on how to approach a proof for this strategy or can provide guidance on whether this intuition is correct, I would greatly appreciate it.

• Assume there was a pick leading to more removals and try to show a contradiction. Commented Aug 9 at 15:54