PriorityQueue

Lab Java Intermediate 20 points

Read n integers into a PriorityQueue and print them in the order they are polled (smallest first), then do the same with a max-heap using Collections.reverseOrder().

Input

n, then n integers.

Output

Two lines.

Example

Input

6
5 1 8 3 9 2

Output

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

Sample input available Sample output available

Editor

Java

Hints

poll() always removes the smallest element (by natural order).

Printing a PriorityQueue directly does NOT show sorted order.

Solution explanation

A priority queue is a heap: only the head is guaranteed to be in order.

Show solution

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static String drain(PriorityQueue<Integer> pq) {
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            sb.append(sb.length() > 0 ? " " : "").append(pq.poll());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> min = new PriorityQueue<Integer>();
        PriorityQueue<Integer> max = new PriorityQueue<Integer>(Collections.<Integer>reverseOrder());
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            min.add(x);
            max.add(x);
        }
        System.out.println(drain(min));
        System.out.println(drain(max));
    }
}

Output

Answer