Problem: Fillomino is a classic logic puzzle. (You do not need to know Fillomino in order to solve this problem.) In one classroom in Yunqi town, some volunteers are playing a board game variant of it:

Consider an n by n chessboard. Its rows are numbered from 1 to n from the top to the bottom. Its columns are numbered from 1 to n from the left to the right. A cell on an intersection of x-th row and y-th column is denoted (x, y). The main diagonal of the chessboard is cells (x, x) for all 1 ≤ x ≤ n.

A permutation of \{1, 2, 3, ..., n\} is written on the main diagonal of the chessboard. There is exactly one number written on each of the cells. The problem is to partition the cells under and on the main diagonal (there are exactly 1+2+ … +n such cells) into n connected regions satisfying the following constraints:

  1. Every region should be connected. That means that we can move from any cell of a region to any other cell of the same region visiting only cells of the same region and moving from a cell to an adjacent cell. 
  2. The x-th region should contain cell on the main diagonal with number x for all 1≤ x≤ n. 
  3. The number of cells that belong to the x-th region should be equal to x for all 1≤ x≤ n. 
  4. Each cell under and on the main diagonal should belong to exactly one region. 

Input

The first line contains a single integer n (1≤ n ≤ 500) denoting the size of the chessboard.

The second line contains n integers p_1, p_2, ..., p_n. p_i is the number written on cell (i, i). It is guaranteed that each integer from \{1, …, n\} appears exactly once in p_1, ..., p_n.

Output

If no solution exists, output -1.

Otherwise, output n lines. The i-th line should contain i numbers. The j-th number on the i-th line should be x if cell (i, j) belongs to the the region with x cells.

Examples

Input


3
2 3 1


Output


2
2 3
3 3 1


Input


5
1 2 3 4 5


Output


1
2 2
3 3 3
4 4 4 4
5 5 5 5 5

Note

The solutions to the examples are illustrated in the following pictures: <image> <image>

Solution (in JAVA):

Solution:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.function.BiConsumer;

import java.io.IOException;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;


public class S {
	
	static private long ans;
	static private long count1;
	static private long count2;
	static private long tmp;
	
	private static int[][] arr;
	private static int n;
	
	private static long[] larr;
	private static int r1,r2,r3;
	private static int c1,c2,c3;
	private static int p1,p2,p3;
	private static long r;
	private static long min;
	private static long max;
	private static int d;
	private static boolean check;
	
	static class Reader {
		
		static BufferedReader reader;
		static StringTokenizer tokenizer;
		
		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}
		
		static String next() throws IOException {
			while(!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		
		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		
	}
	
	static class Runner {
		public int min;
		public int[] route;
		
		public Runner(int l, int val) {
			// TODO Auto-generated constructor stub
			min = val;
			route  = new int[l];
			route[0] = val;
		}
	}

	static int[] merge(int[] a, int[] b) {
		int m = a.length;
		int n = b.length;
		int [] c = new int[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[] Msort(int[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[] Msorted = new int[l];
			int[] m1 = new int[l/2];
			int[] m2 = new int[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}
	
	static Runner[] merge(Runner[] a, Runner[] b) {
		int m = a.length;
		int n = b.length;
		Runner[] c = new Runner[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j].min<b[k].min) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j].min==b[k].min) {
					if(a[j].min<b[k].min) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static Runner[] Msort(Runner[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			Runner[] Msorted = new Runner[l];
			Runner[] m1 = new Runner[l/2];
			Runner[] m2 = new Runner[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}

	
	static long[] merge(long[] a, long[] b) {
		int m = a.length;
		int n = b.length;
		long [] c = new long[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static long[] Msort(long[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			long[] Msorted = new long[l];
			long[] m1 = new long[l/2];
			long[] m2 = new long[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}

	static int[][] merge_x(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][0]==b[k][0]) {
					if(a[j][1]<b[k][1]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_x(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_x(Msort_x(m1), Msort_x(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_y(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][1]==b[k][1]) {
					if(a[j][0]<b[k][0]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_y(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_y(Msort_y(m1), Msort_y(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_3(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][3];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				c[j+k][2] = b[k][2];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				c[j+k][2] = a[j][2];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else if(a[j][0]==b[k][0] && a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					c[j+k][2] = b[k][2];
					k++;
				}
			}
		}
		return c;
	}
	
	
	
	static int[][] Msort_3(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][3];
			int[][] m1 = new int[l/2][3];
			int[][] m2 = new int[l-(l/2)][3];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
					m1[i][2] = unsorted[i][2];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
					m2[i-(l/2)][2] = unsorted[i][2];
				}
			}
			
			Msorted = merge_3(Msort_3(m1), Msort_3(m2));
			
			return Msorted;
		}
		
	}

	public static void print2dArray(int [][] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i][0]+" "+arr[i][1]+" ");
		}
	}
	
	public static void printArray(long [] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i]+" ");
		}
	}
		
	public static void printArray(int [] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	
    static boolean binarySearch(int arr[], int x, int y) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else if(arr[m] > y)
                r = m - 1; 
            
            else {
            	return true;
            }
        } 
  
        // if we reach here, then element was 
        // not present 
        return false; 
    } 
    
    static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    }

    static long gcd(long a, long b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    }

    
    static long gcd_arr(long[] arr) {
    	long gcd_a = gcd(arr[0], arr[1]);
    	
    	for(int i=2; i<arr.length && gcd_a!=1; i++) {
    		gcd_a = gcd(gcd_a ,arr[i]);
    	}
    	
    	return gcd_a;
    }
      
	public static void main(String[] args) throws IOException {
		
		tmp = 0;
		count1 = 0;
		count2 = 0;
		
		ans = 0;
		
		Reader.init(System.in);
		
		OutputStream out = new BufferedOutputStream(System.out);
		
		int t=1;
	//	t = Reader.nextInt();
		
		main_loop:
		for(int tn=0; tn<t; tn++) {
			
			ans=0;
			
			int n = Reader.nextInt();
			
			int[][] mtx = new int[n+1][n+1];
			
			for(int i=1; i<n+1; i++) {
				mtx[i][i] = Reader.nextInt();
			}
			
			for(int i=n; i>0; i--) {
				int x = mtx[i][i];
				int r=i;
				int c=i;
				
				for(int j=0; j<x; j++) {
					mtx[r][c] = x;
					if((r+1<=n)  && (mtx[r+1][c]==0)) {
						r++;
					}
					else {
						c--;
					}
				}
			}
			
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=i; j++) {
					out.write((mtx[i][j]+" ").getBytes());
				}
				out.write(("\n").getBytes());
			}

			
		//	out.write((ans+"\n").getBytes());
		}
		
		out.flush();
		out.close();
		
	}
	
}