Challenge: Smash the Stones

Lab C++ Intermediate 20 points

Each turn, smash the two heaviest stones: equal stones are both destroyed; otherwise the heavier becomes the difference. Print the last stone's weight, or 0. Use a max-heap.

Input

Line 1: n. Line 2: n positive whole numbers.

Output

One number.

Example

Input

6
2 7 4 1 8 1

Output

Sample input available Sample output available

Editor

C++

Hints

priority_queue<int> already gives the biggest first.

Push back a - b if it isn't 0.

Solution explanation

Each turn is O(log n), and there are at most n turns.

Show solution

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        if (a != b) pq.push(a - b);
    }
    cout << (pq.empty() ? 0 : pq.top()) << endl;
    return 0;
}

Output

Answer