Challenge: Sorted Squares

Lab Java Beginner 10 points

Read a sorted list that may contain negative numbers. Print the squares of all numbers in sorted order. Don't square and sort – use two pointers: the biggest square is always at one of the two ends.

Input

Line 1: n. Line 2: n sorted whole numbers (−10⁴ to 10⁴).

Output

The squares in ascending order, separated by spaces.

Example

Input

5
-4 -1 0 3 10

Output

0 1 9 16 100

Sample input available Sample output available

Editor

Java

Hints

The largest square is either a[left]² or a[right]².

Fill the answer array from the last position backwards.

Solution explanation

Each step places one square and moves one pointer: O(n), instead of O(n log n) for sorting.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int[] out = new int[n];
        int left = 0, right = n - 1;
        for (int pos = n - 1; pos >= 0; pos--) {     // fill from the back, biggest first
            int l = a[left] * a[left], r = a[right] * a[right];
            if (l > r) {
                out[pos] = l;
                left++;
            } else {
                out[pos] = r;
                right--;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(out[i]);
        }
        System.out.println(sb);
    }
}

Output

Answer