Challenge: One Partition Step

Lab Java Intermediate 20 points

Do one quick sort partition step using the last number as the pivot, exactly like the lesson (a “wall” that starts at the left, swap smaller items to the wall, then swap the pivot to the wall). Print the array after the step and then the pivot's final index.

Input

Line 1: n (n ≥ 1). Line 2: n whole numbers.

Output

Line 1: the array after partitioning. Line 2: pivot at <i>.

Example

Input

7
10 80 30 90 40 50 70

Output

10 30 40 50 70 90 80
pivot at 4

Sample input available Sample output available

Editor

Java

Hints

pivot = a[n - 1]; wall = 0.

For each i before the pivot: if a[i] < pivot, swap a[i] with a[wall] and move the wall.

Solution explanation

One pass, O(n). After it, everything left of the pivot is smaller and everything right is at least as big.

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 pivot = a[n - 1], wall = 0;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] < pivot) {
                int t = a[i]; a[i] = a[wall]; a[wall] = t;
                wall++;
            }
        }
        int t = a[n - 1]; a[n - 1] = a[wall]; a[wall] = t;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
        System.out.println("pivot at " + wall);
    }
}

Output

Answer