Priority Queue

Lab C++ Intermediate 20 points

Read n integers into a max-heap and a min-heap (priority_queue with greater<int>) and print the order in which each pops them.

Input

Line 1: n. Line 2: n integers.

Output

Two lines.

Example

Input

6
5 1 8 3 9 2

Output

9 8 5 3 2 1
1 2 3 5 8 9

Sample input available Sample output available

Editor

C++

Hints

The default priority_queue is a max-heap.

Solution explanation

Heaps give O(log n) insert and O(1) access to the largest (or smallest) element.

Show solution

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

int main() {
    int n;
    cin >> n;
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        maxHeap.push(x);
        minHeap.push(x);
    }
    for (int i = 0; i < n; i++) {
        cout << maxHeap.top() << (i < n - 1 ? " " : "\n");
        maxHeap.pop();
    }
    for (int i = 0; i < n; i++) {
        cout << minHeap.top() << (i < n - 1 ? " " : "\n");
        minHeap.pop();
    }
    return 0;
}

Output

Answer