Minimum Remaining Stone After Pairwise Smashing

You are given n stones with positive integer weights. The stones are smashed together in pairs following the process below:

• In each step, choose the two largest stones.
• Smash them together. Let their weights be a and b (assume a ≥ b). The new stone's weight is given by \( |a - b| \). If it is nonzero, it is added back into the collection. Otherwise, both stones are completely destroyed.

This process continues until there is at most one stone left. Your task is to compute the weight of the last remaining stone (or return 0 if no stone remains).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains a single integer n (1 ≤ n ≤ 105), the number of stones.
The second line contains n space-separated positive integers, where each integer represents the weight of a stone.

outputFormat

Output a single integer to standard output (stdout) — the minimum possible weight of the remaining stone after performing all the smashes.

3
2 4 1

1