PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Alex
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra
DIFFICULTY:
EasyMedium
PREREQUISITES:
None
PROBLEM:
Given an array A consisting of N nonnegative integers.
You need to perform the following operation (N  1) times:

Sort the array A in ascending order.

Let M be the current size of the array A. Replace the array A by [(A_2  A_1), (A_3  A_2), \ldots ,(A_M  A_{M1})]. Note that each time the operation is performed, the size of the array reduces by one.
Find the remaining element after (N1) operations.
QUICK EXPLANATION:
We make an observation that after O(logC) iterations there can be at most O(logC) nonzero elements. Thus we would have an array with majority of the elements as zero. Now instead of creating large arrays with most of elements zero, we can just keep a count of zeroes and only keep the non zero elements in the array and perform operations on that array. This would drastically reduce the time to perform the operation on an array since the size of the array would be really small.
Thus we would perform operations on the array as mentioned in the question but would exclude the zero elements from the array and keep a track of it in a variable. But we would include one zero element in the array(if it exists) so as to process its immediate right neighbour.
EXPLANATION:
First we observe that after O(logC) iterations there can be at most O(logC) nonzero elements. Lets prove it here.
Let’s say after the operation we have m nonzero numbers
a_1 \leq a_2 \leq a_3 \leq ... \leq a_m
then before the operation these were differences in sorted order, so the largest element is no smaller than sum of them, the second largest is no smaller than sum of them except one (the largest) and so on
so before the operation we had m nonzero numbers which are at least
now apply this many k times
Basically we are calculating prefix sums of an array k times
Now it’s easy to see that the last number before k operations should be at least \binom{k+m2}{k1}
for k = m = log_2 C + 1 it is bigger than C
Thus we can just take array and perform the operation as explained above in quick explanation.
TIME COMPLEXITY:
O(NLogC) for each test case, where C \leq 10^{18}