Challenge: Squeeze Into Line

Lab Java Beginner 10 points

Read a line of n numbers, then a position p and a value v. Insert v so that it ends up at index p, shifting the others right – using a plain array and a loop (no ArrayList). Print the new line.

Input

Line 1: n. Line 2: n numbers. Line 3: p v (0 ≤ p ≤ n).

Output

The n + 1 numbers, separated by spaces.

Example

Input

4
10 20 30 40
1 15

Output

10 15 20 30 40

Sample input available Sample output available

Editor

Java

Hints

Make the array one slot bigger than n.

Shift from the back (i = n down to p + 1) so you don't overwrite numbers you still need.

Solution explanation

This is exactly what ArrayList.add(index, value) does inside, and why it is O(n).

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 + 1];               // one spare slot
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int p = sc.nextInt(), v = sc.nextInt();
        for (int i = n; i > p; i--) {           // shift right, starting from the back
            a[i] = a[i - 1];
        }
        a[p] = v;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(a[i]);
        }
        System.out.println(sb);
    }
}

Output

Answer