Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number.

Use sort and find min and max after output each pair.
Quite slow, 0.14s :)

Greedy approach is fine but why output pairs with maximum number and minimum number ??

I used a max heap in which I hold pairs like, number i (index of the sign) and frequency of that sign. Each time I pop out from that heap the 2 index with maximal frequency, decrement their frequency and update the heap from their indexes.

I was sure that there is a more simplier aproach to that problem(like greedy), without using heap, but I was just 99.9% sure that with heap I will got AC, and so it was. :)

The same here. I'm using heap, but I'm pulling entries one by one, decrementing and not adding them back until next entry is pulled. I was 146% sure this would work when I decided to implement this algo and it not that bad in terms of time: O(n log k). But I wondered if there is a simple straightforward algo that also would work. Turned out there is.

I created an array of pairs (quantity, index) and sorted it. Output the maximum and the next one with a positive quantity, and if there are elements with the same quantity that remains at the maximum, I output them the same way, each step decreasing the number of the output element
Sorry for my English

tests with my answers:
4
8 5 4 3
1 2 1 2 1 2 1 2 1 2 3 1 3 4 1 3 4 1 3 4

5
9 7 4 4 3
1 2 1 2 1 2 1 2 1 2 1 2 4 3 1 2 4 3 5 1 4 3 5 1 4 3 5