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 PYTHON3):

Solution:
import collections
import itertools
from functools import reduce

mod = (10 ** 9) + 7


def permutationbysum():
    for _ in range(int(input())):
        num, l, r, achieve = map(int, input().split())
        k = r - l + 1
        if (k * (k + 1)) // 2 <= achieve <= (k * (num * 2 + 1 - k)) // 2:
            outpos = (r) % num
            inpos = l - 1
            ans = [0] * num
            for i in range(num, 0, -1):
                if achieve - i > 0 or (achieve - i == 0 and inpos == r - 1):
                    achieve -= i
                    ans[inpos] = i
                    inpos += 1
                else:
                    ans[outpos] = i
                    outpos += 1
                    outpos %= num
            print(*ans)
        else:
            print(-1)


# permutationbysum()

def peaks():
    for _ in range(int(input())):
        num, peak = map(int, input().split())
        pos = 1
        rpos = num
        ans = []
        now = 0
        if num == 1:
            if not peak:
                print(1)
            else:
                print(-1)
            continue
        if num == 2:
            if peak:
                print(-1)
            else:
                print(1, 2)
            continue
        added = 0
        while rpos + 1 != pos:
            if not peak:
                while pos <= rpos:
                    ans.append(pos)
                    pos += 1
                break
            if not now:
                ans.append(pos)
                pos += 1
            else:
                ans.append(rpos)
                rpos -= 1
                if num - added != 1:
                    peak -= 1
            added += 1
            now = 1 - now
        if peak:
            print(-1)
            continue
        print(*ans)


# peaks()
import sys

input = sys.stdin.readline


def addone():
    for _ in range(int(input())):
        num, changes = input().split()
        l = collections.deque(sorted([int(i) for i in num]))
        perm = collections.deque()
        changes = int(changes)
        cd = 0
        ans = len(num)
        while True:
            nextnum = l.pop()
            while perm and perm[-1] == nextnum:
                l.append(perm.pop())
            c = (10 - nextnum) - cd
            changes -= c
            cd += c
            if changes >= 0:
                if not c:
                    perm.appendleft(1 - cd)
                    l.appendleft(-cd)
                else:
                    l.appendleft(1 - cd)
                    l.appendleft(-cd)
                ans += 1
            else:
                break
        print(ans % 1000000007)


# addone()

import math


def andsequences():
    def mapping(num):
        nonlocal mnum
        nonlocal c
        num = int(num)
        if num < mnum:
            mnum = num
            c = 1
        elif num == mnum:
            c += 1
        return num

    mod = 1000000007
    for _ in range(int(input())):
        mnum = float('inf')
        c = 0
        num = int(input())
        l = list(map(mapping, input().split()))
        for i in l:
            if mnum & i != mnum:
                print(0)
                break
        else:
            if c == 1:
                print(0)
            else:
                print((math.factorial(num - 2) * (c - 1) * c) % mod)


# andsequences()

def numberdigit():
    n = ((10 ** 5) * 2)
    l = [0] * 11
    mod = 10 ** 9 + 7
    l[0] = l[1] = l[2] = l[3] = l[4] = l[5] = l[6] = l[7] = l[8] = 2
    l[9] = 3
    l[10] = 4
    for i in range(11, n):
        l.append((l[i - 10] + l[i - 9]) % mod)
    for _ in range(int(input())):
        num, c = input().split()
        c = int(c)
        ans = 0
        for i in num:
            i = int(i)
            if 10 - i > c:
                ans += 1
            else:
                ans += l[c - (10 - i)]
        print(ans % mod)


# numberdigit()

def mushroom():
    people, t1, t2, percent = map(int, input().split())
    l = []
    percent = 1 - percent * 0.01
    for i in range(1, people + 1):
        s, s1 = map(int, input().split())
        l.append([i, max(s * t1 * percent + s1 * t2, s1 * t1 * percent + s * t2)])
    l.sort(key=lambda x: (x[1]), reverse=True)
    for i in l:
        i[1] = "{:.2f}".format(i[1])
        print(*i)


# mushroom()

def escape():
    prins = int(input())
    dra = int(input())
    start = int(input())
    pack = int(input())
    c = int(input())
    speeddiff = dra - prins
    if speeddiff <= 0:
        return 0
    pd = start * prins
    ans = 0
    while pd < c:
        hs = pd / speeddiff
        pd += prins * hs
        if pd >= c:
            break
        time = pd / dra
        time += pack
        pd += prins * time
        ans += 1
    return ans


# print(escape())

def perm():
    def high(n, k):
        return k * (2 * n - k + 1) // 2

    def low(k):
        return k * (k + 1) // 2

    for _ in range(int(input())):
        num, lef, rig, s = map(int, input().split())
        k = rig - lef + 1
        rig, lef = rig - 1, lef - 1
        if not high(num, k) >= s >= low(k):
            print(-1)
            continue
        l = [0] * num
        lp = lef
        rp = lef - 1
        for i in range(num, 0, -1):
            if high(i, k) >= s and s - i >= low(k - 1) and k:
                l[lp] = i
                lp += 1
                s -= i
                k -= 1
            else:
                l[rp] = i
                rp -= 1
        if k:
            print(-1)
        else:
            print(*l)


# perm()


def newcom():
    for _ in range(int(input())):
        days, price = map(int, input().split())
        dl = input().split()
        worth = input().split()
        worth.append(0)
        ans = float('inf')
        req = 0
        left = 0
        for i in range(days):
            a = int(dl[i])
            w = int(worth[i])
            ans = min(ans, req + max(0, price - left + a - 1) // a)
            ns = max(0, w - left + a - 1) // a
            req += ns + 1
            left += a * ns - w
        print(ans)


# newcom()


def perfectsq():
    for _ in range(int(input())):
        n = input()
        for i in input().split():
            sq = math.sqrt(int(i))
            if sq != int(sq):
                print("YES")
                break
        else:
            print("NO")


# perfectsq()

def and0big():
    for _ in range(int(input())):
        l, k = map(int, input().split())
        print(l ** k % mod)


# and0big()

import math


def mod1p():
    n = int(input())
    ans = dict()
    p = 1
    for i in range(1, n):
        if math.gcd(i, n) == 1:
            ans[str(i)] = True
            p = (p * i) % n
    if p == 1:
        print(len(ans))
        print(' '.join(ans.keys()))
    else:
        ans.pop(str(p))
        print(len(ans))
        print(' '.join(ans.keys()))


# mod1p()

def shorttask():
    num = 10000100
    l = [-1] * (num + 2)
    s = [-1] * (num + 2)
    l[1] = 1
    for i in range(2, int(math.sqrt(num + 1)) + 2):
        if l[i] == -1:
            l[i] = i
            for x in range(i * i, num + 1, i):
                if l[x] == -1:
                    l[x] = i
    s[1] = 1
    for i in range(2, num + 1):
        if l[i] == -1:
            l[i] = i
            s[i] = i + 1
        else:
            i1 = i
            s[i] = 1
            while i1 % l[i] == 0:
                i1 //= l[i]
                s[i] = s[i] * l[i] + 1
            s[i] *= s[i1]
    ans = [-1] * (num + 1)
    for i in range(num, 0, -1):
        if s[i] < num:
            ans[s[i]] = i
    for _ in range(int(input())):
        print(ans[int(input())])


# shorttask()

def review():
    for _ in range(int(input())):
        n = int(input())
        ans = 0
        for i in input().split():
            i = int(i)
            if i == 1 or i == 3:
                ans += 1
        print(ans)


# review()

def GCDleng():
    po10 = [0] * 11
    po10[1] = 1
    for i in range(2, 11):
        po10[i] = po10[i - 1] * 10
    for _ in range(int(input())):
        n, n1, res = map(int, input().split())
        print(po10[n], po10[n1] + po10[res])


# GCDleng()


def anothercarddeck():
    n, q = map(int, input().split())
    l = input().split()
    d = {l[i]: i for i in range(n - 1, -1, -1)}
    ans = []
    for i in input().split():
        now = d[i]
        ans.append(now + 1)
        for key in d:
            if d[key] < now:
                d[key] += 1
        d[i] = 0
    print(*ans)


# anothercarddeck()

def mincoststring():
    n, letters = map(int, input().split())
    l = [chr(i + 97) for i in range(letters)]
    ans = []
    real = letters - 1
    if not n:
        print(*ans, sep='')
        return
    if n == 1:
        print(*ans, sep='', end='')
        print(l[1 % (real + 1)])
        return
    while n:
        for i in range(len(l)):
            for i1 in range(i, len(l)):
                if i1 != real:
                    ans.append(l[i1])
                    ans.append(l[i])
                    n -= 2
                else:
                    ans.append(l[i1])
                    n -= 1
                if not n:
                    print(*ans, sep='')
                    return
                if n == 1:
                    print(*ans, sep='', end='')
                    print(l[(i1 + 1) % (real + 1)])
                    return
    print(*ans)


# mincoststring()


def mincost2():
    n, letters = map(int, input().split())
    l = [chr(i + 97) for i in range(letters)]
    comb = []
    if letters == 1 or n == 1:
        print('a' * n)
        return
    for i in range(letters):
        for i1 in range(i, letters):
            comb.append(l[i1] + l[i])
    lc = len(comb)
    while True:
        for i in range(lc):
            if ord(comb[i][0]) - 97 == letters - 1:
                n -= 1
                print(comb[i][0], end='')
            else:
                n -= 2
                print(comb[i], end='')
            if n == 1:
                pos = ord(comb[i][0]) - 97 + 1
                print(l[pos % letters])
                return
            if not n:
                return


# mincost2()
def Tittat():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        l = list(map(int, input().split()))
        for i in range(n):
            if not k:
                break
            while k and l[i]:
                l[i] -= 1
                l[-1] += 1
                k -= 1
        print(*l)


# Tittat()

def xorq2():
    for _ in range(int(input())):
        n = int(input())
        s = 0
        num = -1
        nc = 0
        c = 0
        for i in input().split():
            i = int(i)
            s ^= i
            c += 1
            if num == -1 and s == i:
                num = s
                s = 0
                nc += c
                c = 0
            if num != -1 and (s == num or not s):
                s = 0
                nc += c
                c = 0
        print(['NO', 'YES'][nc == n])


# xorq2()


def xorq2re():
    n = int(input())
    s = input().split()
    xor = 0
    for i in range(n):
        s[i] = int(s[i])
        xor ^= s[i]
    if not xor:
        print("YES")
    else:
        new = 0
        ans = 0
        for i in s:
            new ^= i
            if new == xor:
                new = 0
                ans += 1
        print(["NO", "YES"][ans > 1])


import sys

sys.setrecursionlimit(2300)


def q3partition():
    def partition():
        if tol % 2:
            return 0
        up = tol
        rec = [[False] * (up + 2) for _ in range(n + 1)]
        rec[0][0] = True
        for i in range(1, n + 1):
            v = l[i - 1]
            for j in range(up + 1):
                if rec[i - 1][j]:
                    if v + j <= up:
                        rec[i][j + v] = True
                    rec[i][j] = True

        return rec[n][tol // 2]

    def ints(x):
        nonlocal tol
        nonlocal gcf
        x = int(x)
        tol += x
        gcf = math.gcd(gcf, x) if gcf != float('inf') else x
        return x

    n = int(input())
    tol = 0
    gcf = float('inf')
    l = list(map(ints, input().split()))
    if partition():
        pos = 1
        for i in l:
            if i // gcf % 2:
                print(1)
                print(pos)
                return
            pos += 1
    else:
        print(0)


def permu(n, r):
    return math.factorial(n) // math.factorial(n - r)


def comb(n, r):
    return math.factorial(n) // math.factorial(r) * math.factorial(n - r)


def calc():
    n = int(input())
    ans = permu(n, n)
    for i in range(1, n + 1):
        ans -= comb(n, i)
    print(ans)


# calc()


def order():
    for _ in range(int(input())):
        n = int(input())
        odd = []
        even = []
        for i in input().split():
            i = int(i)
            if i % 2:
                odd.append(i)
            else:
                even.append(i)
        print(*odd + even)


# order()


def TMTdoc():
    n = int(input())
    l = input().rstrip()
    tts = 0
    tms = 0
    for i in l:
        if i == 'T':
            tts += 1
        else:
            tms += 1
    if tms * 2 == tts:
        nowts = 0
        nowms = 0
        for i in l:
            if i == 'T':
                nowts += 1
            else:
                nowms += 1
                if nowts >= nowms and tms - nowms + 1 <= tts - nowts:
                    continue
                return "NO"
    else:
        return "NO"
    return 'YES'


def relayrace():
    def solve(n):
        if n:
            s = -1
        else:
            s = 1
        nowmax = -float('inf')
        nowmin = -nowmax
        ans = 0
        for i, v in sorted(l, key=lambda x: (x[1], s * int(x[0])), reverse=True):
            i = int(i)
            if i > nowmax:
                nowmax = i
            if i < nowmin:
                nowmin = i
            ans += v * (nowmax - nowmin)
        return ans

    n = int(input())
    # l = list(collections.Counter(input().split()).items())
    l = -1
    ans = 0
    for i in sorted(input().split(), key=lambda x: int(x)):
        if l == -1:
            l = int(i)
        else:
            ans += int(i) - l
    return ans


def relayraces():
    n = int(input())
    l = sorted(map(int, input().split()))
    minv = float("INF")
    minpos = 0
    for i in range(len(l)):
        if i > 0 and 0 <= l[i] - l[i - 1] <= minv:
            minv = l[i] - l[i - 1]
            minpos = i
        if i < n - 1 and l[i + 1] - l[i] <= minv:
            minv = l[i + 1] - l[i]
            minpos = i
    lpos = minpos - 1
    rpos = minpos + 1
    ans = 0
    while lpos >= 0 and rpos < n:
        diffl = -(l[lpos] - l[minpos])
        diffr = l[rpos] - l[minpos]
        if diffl < diffr:
            minpos = lpos
            lpos -= 1
            ans += diffl
        else:
            minpos = rpos
            rpos += 1
            ans += diffr
    if lpos < 0:
        m = l[0]
        for i in range(rpos, n):
            ans += l[i] - m
    else:
        h = l[-1]
        for i in range(minpos, -1, -1):
            ans += h - l[i]
    return ans


# sys.setrecursionlimit(2004)


def relayracess():
    def recur(l, r):
        if l == r:
            return 0
        if d[(l, r)] != -1:
            return d[(l, r)]
        ans = nums[r] - nums[l] + min(recur(l + 1, r), recur(l, r - 1))
        d[(l, r)] = ans
        return ans

    d = collections.defaultdict(lambda: -1)
    n = int(input())
    nums = sorted(map(int, input().split()))
    return recur(0, n - 1)


def relayracesss():
    # def recur(l,r):
    #     if l == r:
    #         d[l][r] = 0
    #         return 0
    #     if d[l][r] != -1:
    #         return d[l][r]
    #     ans = nums[r]-nums[l] + min(recur(l+1,r),recur(l,r-1))
    #     d[l][r] = ans
    #     return ans
    # n = int(input())
    # m = n + 20
    # d = [[-1]*m for _ in range(m)]
    n = int(input())
    l = sorted(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        for i1 in range(i + 1, n):
            dp[i][i1] = l[i1] - l[i] + min(dp[i + 1][i1], dp[i][i1 - 1])
    return dp[0][n - 1]


def relayracessss():
    n = int(input())
    l = sorted(map(int, input().split()))
    dp = [0] * n
    for le in range(n - 2, -1, -1):
        for ri in range(le + 1, n):
            dp[ri] = l[ri] - l[le] + min(dp[ri], dp[ri - 1])
    return dp[-1]


def binli():
    n = int(input())
    n2 = n * 2
    s = input().rstrip()
    s1 = input().rstrip()
    s2 = input().rstrip()
    posl = [0, 0, 0]
    ans = ''
    while max(posl) < n2:
        l = [[], []]
        l[int(s[posl[0]])].append(0)
        l[int(s1[posl[1]])].append(1)
        l[int(s2[posl[2]])].append(2)
        if len(l[0]) >= 2:
            for i in l[0]:
                posl[i] += 1
            ans += '0'
        else:
            for i in l[1]:
                posl[i] += 1
            ans += '1'
    if posl[0] == n2:
        if posl[1] >= posl[2]:
            ans += s1[posl[1]:]
        else:
            ans += s2[posl[2]:]
    elif posl[1] == n2:
        if posl[0] >= posl[2]:
            ans += s[posl[0]:]
        else:
            ans += s2[posl[2]:]
    else:
        if posl[0] >= posl[1]:
            ans += s[posl[0]:]
        else:
            ans += s1[posl[1]:]
    print(ans)


def almostsort():
    n, k = map(int, input().split())
    ul = 2 ** (n - 1)
    if k > ul:
        return [-1]
    permen = []
    bi = bin(k - 1)[2:]
    if bi == '0':
        return range(1, n + 1)
    pos = n - len(bi)
    ans = list(range(1, pos))
    for i in bi:
        permen.append(pos)
        if not int(i):
            ans += permen[::-1]
            permen = []
        pos += 1
    permen.append(n)
    ans += permen[::-1]
    return ans


def q1_2050():
    for i in range(int(input())):
        s = int(input())
        if s % 2050:
            print(-1)
        else:
            ab = 2050
            while ab <= s:
                ab *= 10
            ab //= 10
            c = 0
            while s and s != 1:
                c += s // ab
                s = s % ab
                while s != 1 and s and s < ab:
                    ab //= 10
            print(c)


def q2jog():
    n, m = map(int, input().split())
    sortbyval = []
    rowsv = [collections.defaultdict(int) for _ in range(n)]
    for row in range(n):
        for i in input().split():
            i = int(i)
            sortbyval.append([i, row])
            rowsv[row][i] += 1
    sortbyval.sort(key=lambda x: x[0])
    larl = []
    for i in range(0, n * m, m):
        larl.append(sortbyval[i:i + m])
    ans = [[0] * m for _ in range(n)]
    person = 0
    for i in larl:
        for v, pos in i:
            ans[pos][person] = v
            rowsv[pos][v] -= 1
            person += 1
            if person == m:
                break
        else:
            continue
        break
    for r in range(n):
        for c in range(m):
            if not ans[r][c]:
                for key in list(rowsv[r].keys()):
                    if not rowsv[r][key]:
                        rowsv[r].pop(key)
                        continue
                    rowsv[r][key] -= 1
                    ans[r][c] = key
                    break
    for i in ans:
        print(*i)


def q3fillomino(n, inp):
    def gorow():
        nonlocal nowp
        nonlocal col
        nonlocal totake
        t = 0
        if nowp and col < n and totake and not l[col][nowp - 1]:
            for back in range(nowp, -1, -1):
                if l[col][back]:
                    nowp += 1
                    col += 1
                    return t
                if not totake:
                    return t
                l[col][back] = i
                totake -= 1
                nowp -= 1
                t = 1
            nowp += 1
            col += 1
        return t
    l = [[0] * i for i in range(1, n + 1)]
    p = 0
    for i in inp:
        totake = int(i)
        nowp = p
        col = p
        while col < n:
            if not totake:
                break
            for _ in range(n-p):
                if not gorow():
                    break
            if not totake or col == n or nowp == n:
                break
            l[col][nowp] = i
            totake -= 1
            col += 1
        p += 1
    for i in l:
        print(*i)


def main():
    # for _ in range(int(input())):
    # for i in range(10, 15):

    q3fillomino(int(input()), input().split())


main()