A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is r_{i}.

The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.

One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five (but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so r_{i} = 0 doesn't change after losing.

The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).

The friends want to make their ratings equal but as high as possible.

Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.

The second line contains n non-negative integers r_1, r_2, ..., r_{n} (0 ≤ r_{i} ≤ 100), where r_{i} is the initial rating of the i-th friend.


-----Output-----

In the first line, print a single integer R — the final rating of each of the friends.

In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain n characters '0' or '1', where the j-th character of the i-th line is equal to:

  '0', if friend j should not play in match i,  '1', if friend j should play in match i. 

Each line should contain between two and five characters '1', inclusive.

The value t should not exceed 10^4, it is guaranteed that such solution exists. 

Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.


-----Examples-----
Input
5
4 5 1 7 4

Output
1
8
01010
00011
01010
10010
00011
11000
00011
11000

Input
2
1 2

Output
0
2
11
11

Input
3
1 1 1

Output
1
0

Difficulty: competition

Starter code:

Solutions:
n = int(input())
L = list(map(int, input().split()))
ans = 0
M = []
while max(L) != min(L):
    ans += 1
    k = max(L)
    if L.count(k) == 3:
        s = ''
        for i in range(len(L)):
            if L[i] == k:
                s += '1'
                L[i] -= 1
            else:
                s += '0'
        M.append(s)    
    else:      
        max_1 = 0
        max_2 = 1
        if L[max_1] < L[max_2]:
            max_1, max_2 = max_2, max_1
        for i in range(2, n):
            if L[i] > L[max_1]:
                max_2, max_1 = max_1, i
            elif L[i] > L[max_2]:
                max_2 = i
        s = ''
        for i in range(n):
            if i == max_1 or i == max_2:
                s += '1'
            else:
                s += '0'
        M.append(s)
        L[max_1] -= 1
        if L[max_1] < 0:
            L[max_1] = 0
        L[max_2] -= 1
        if L[max_2] < 0:
            L[max_2] = 0
print(max(L))
print(ans)
for i in M:
    print(i)

import collections


def temp(list1):
    list2 = list(list1)
    list3=[]
    cnt = collections.Counter()
    for i in range(len(list1)):
        cnt[list1[i]]+=1
    tep = max(list1)
    if cnt[tep] != 1:
        if cnt[tep] <= 5:
            for i in range(5):
                if tep in list2:
                    list3.append(list2.index(tep))
                    list2[list2.index(tep)] = -1
                else:
                    break
        else:
            for i in range(4):
                if tep in list2:
                    list3.append(list2.index(tep))
                    list2[list2.index(tep)] = -1
                else:
                    break
    else:
        list3.append(list1.index(tep))
        list2.remove(tep)
        list3.append(list1.index(max(list2)))
    return list3




n = int(input())
intgrade = list(map(int, input().split()))
bitlists=[]

if len(set(intgrade)) == 1:
    print(intgrade[0])
    print(0)

else:
    while len(set(intgrade)) != 1:
        listA = temp(intgrade)
        bitlist=''

        for i in range(len(listA)):
            if intgrade[listA[i]] > 0:
                intgrade[listA[i]]-=1

        for i in range(n):
            if i in listA:
                bitlist+="1"
            else:
                bitlist+="0"
        bitlists.append(bitlist)
    print(intgrade[0])
    print(len(bitlists))
    for i in range(len(bitlists)):
        print(bitlists[i])


n = int(input())
d = list(map(int, input().split()))
answer = []
while not all(i == d[0] for i in d):
	i = max(range(n), key = lambda x: d[x])
	max1 = d[i]
	d[i] = -1
	j = max(range(n), key = lambda x: d[x])
	max2 = d[j]
	d[j] = -1
	z = max(range(n), key = lambda x: d[x])
	if max1 == max2 and max1 == d[z]:
		for t in range(n):
			if t != i and t != j and t != z:
				break
		if all(d[v] == d[t] for v in range(n) if v != i and v != j and v != z) and d[t] < max1:
			d[i] = max1 -1
			d[j] = max2 - 1
			d[z] -= 1
			answer.append(''.join('1' if k == i or k == j or k ==z else '0' for k in range(n)))
			continue
	#print(i, j, max1, max2)
	d[i] = max(max1 - 1, 0)
	d[j] = max(max2 - 1, 0)
	answer.append(''.join('1' if k == i or k == j else '0' for k in range(n)))
print(d[0])
print(len(answer))
for i in answer:
	print(i)

n = (int(input()))
R = list(map(int,input().split()))
Time = 0;
check = False
Output = []
while (check == False):
    pos_max = [];     pos_sec = [];    Max_sec = -1;
    Max_num = 0;    Max = -1;
    Min = 999999999;     Time += 1;
    string = ''
    for i in range(len(R)-1,-1,-1):
        if (R[i] < Min):
            Min = R[i]
        if (R[i] > Max):
            Max_sec = Max;      Max = R[i];
            pos_sec = pos_max;   pos_max = [];
            pos_max.append(i);
            Max_num = 1
        elif (R[i] == Max):
            Max_num += 1;
            pos_max.append(i)
        elif (R[i] > Max_sec):
            Max_sec = R[i]
            pos_sec = []
            pos_sec.append(i)
#    print(Max,' ',Max_sec,' ',pos_max,' ',pos_sec,' ',R)
    if (Max == Min):
        check = True
        break
    if (Max_num > 1):
        if (Max_num % 2 == 1):
            j = 0;  some = []
            for k in range(n-1,-1,-1):
                if (pos_max[j] == k):
                    if (R[k] != 0): R[k] -= 1;
                    some.append(k)
                    j += 1;
                    if (j > 2):  j = 0;
            j = len(some)-1
            for k in range(n):
                if (some[j] == k):
                    string += '1'
                    j -= 1
                    if (j < 0): j = 0;
                else : string += '0';
        else :
            j = 0;      some = [];
            for k in range(n-1,-1,-1):
                if (pos_max[j] == k):
                    if (R[k] != 0): R[k] -= 1;
                    some.append(k);
                  #  print('1', end='')
                    j += 1;
                    if (j > 1):  j = 1;
            j = len(some)-1
            for k in range(n):
                if (some[j] == k):
                    string += '1'
                    j -= 1
                    if (j < 0): j = 0;
                else : string += '0';
    else :
        for k in range(n):
         ##   print('k is ',k)
            if (pos_max[0] == k):
                if (R[k] != 0): R[k] -= 1;
                string += '1'
                #print('1', end='')
                continue
            if (pos_sec[0] == k):
                if (R[k] != 0): R[k] -= 1;
                string += '1'
                #print('1', end='')
                continue
            string += '0'
            #print('0', end='');
     #   print('\n')
    Output.append(string)

print(Max)
print(Time-1)
for i in range(len(Output)):
    print(Output[i])

# -*- coding: utf-8 -*-
"""
Created on Thu Nov  2 13:36:10 2017

@author: savit
"""
def sum1(b):
    sum1=0
    for i in range(len(b)):
        sum1+=b[i][0]


    return sum1



n=int(input())
a=list(map(int,input().split()))
if(n!=2):
    do=True
    b=[]
    min2=min(a)
    for i in range(n):
        a[i]-=min2
        b.append([a[i],i])
    prin=[]
    b.sort()
    prinx=-1
    if(sum(a)==1 and min2!=0):
        min2-=1
        for i in range(n):
            b[i][0]+=1
    if(sum1(b)%2):
        if(b[-3][0]==0):
            if(min2==0):
                
                do=False
            else:
                min2-=1
                for i in range(n):
                    b[i][0]+=1
                        
        if(do):   
            b[-1][0]-=1
            b[-2][0]-=1
            b[-3][0]-=1
            prinx=(b[-1][1],b[-2][1],b[-3][1])
            b.sort()
    while(b[-1][0]!=0 and do):
        
        if(b[-2][0]==0):
            if(min2==0):
                do=False
            else:
                min2-=1
                for i in range(n):
                    b[i][0]+=1
                if(sum1(b)%2):
                    if(prinx==-1):
                        b[-1][0]-=1
                        b[-2][0]-=1
                        b[-3][0]-=1
                        prinx=(b[-1][1],b[-2][1],b[-3][1])
                        b.sort()                        
                    else:
                        prin.append([prinx[0],prinx[1]])
                        prin.append([prinx[2],b[-1][1]])
                        b[-1][0]-=1
                        prinx=-1
            
                
                
            
            
        b[-1][0]-=1
        b[-2][0]-=1
        prin.append([b[-1][1],b[-2][1]])
        b.sort()
    if(not do):
        while(b[-1][0]>0):
            b[-1][0]-=1
            prin.append([b[-1][1],b[-2][1]])
        
    
    
    
    x=[0 for i in range(n)]
    print(min2)
    
    if(prinx!=-1):
        print(len(prin)+1)
        x[prinx[0]]=1
        x[prinx[1]]=1
        x[prinx[2]]=1
        print(*x,sep='')
        x[prinx[0]]=0
        x[prinx[1]]=0
        x[prinx[2]]=0
    else:
        print(len(prin))

    
    
    
    for i in prin:
        x[i[0]]=1
        x[i[1]]=1
        print(*x,sep='')
        x[i[0]]=0
        x[i[1]]=0
        
else:
    if(a[1]==a[0]):
        print(a[0])
        print(0)
    else:
        print(0)
        print(max(a))
        for i in range(max(a)):
            print('11')
            
    


n = int(input())

L = list(map(int, input().split()))

ans = 0

M = []

while max(L) != min(L):

    ans += 1

    k = max(L)

    if L.count(k) == 3:

        s = ''

        for i in range(len(L)):

            if L[i] == k:

                s += '1'

                L[i] -= 1

            else:

                s += '0'

        M.append(s)    

    else:      

        max_1 = 0

        max_2 = 1

        if L[max_1] < L[max_2]:

            max_1, max_2 = max_2, max_1

        for i in range(2, n):

            if L[i] > L[max_1]:

                max_2, max_1 = max_1, i

            elif L[i] > L[max_2]:

                max_2 = i

        s = ''

        for i in range(n):

            if i == max_1 or i == max_2:

                s += '1'

            else:

                s += '0'

        M.append(s)

        L[max_1] -= 1

        if L[max_1] < 0:

            L[max_1] = 0

        L[max_2] -= 1

        if L[max_2] < 0:

            L[max_2] = 0

print(max(L))

print(ans)

for i in M:

    print(i)



# Made By Mostafa_Khaled


# coding=utf-8
"""Codeforces 730a solution."""

from operator import itemgetter


class CodeforcesTask730ASolution:
    def __init__(self):
        self.result = ''
        self.players = 0
        self.rating = []

    def read_input(self):
        self.players = int(input())
        self.rating = [int(x) for x in input().split(" ")]

    def process_task(self):

        if self.players > 2:
            moves = []
            players = [[x + 1, self.rating[x]] for x in range(self.players)]
            players.sort(key=itemgetter(1), reverse=True)
            while players[1][1] != players[-1][1]:
                players[0][1] = max(0, players[0][1] - 1)
                players[1][1] = max(0, players[1][1] - 1)
                moves.append([players[0][0], players[1][0]])
                players.sort(key=itemgetter(1), reverse=True)
            if players[0][1] != players[-1][1]:
                added = False
                for m in moves:
                    if not players[0][0] in m:
                        m.append(players[0][0])
                        players[0][1] = max(0, players[0][1] - 1)
                        added = True
                        break
                if not added:
                    #print("edge case 1")
                    #print(players)
                    moves.append([players[-1][0], players[0][0]])
                    players[0][1] = max(0, players[0][1] - 1)
                    players[-1][1] = max(0, players[-1][1] - 1)
                    players.sort(key=itemgetter(1), reverse=True)
                    while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
                        #print(players)
                        players[0][1] = max(0, players[0][1] - 1)
                        players[1][1] = max(0, players[1][1] - 1)
                        moves.append([players[0][0], players[1][0]])
                        players.sort(key=itemgetter(1), reverse=True)
                    if players[0][1] != players[-1][1]:
                        added = False
                        for m in moves:
                            if not players[0][0] in m:
                                m.append(players[0][0])
                                players[0][1] = max(0, players[0][1] - 1)
                                added = True
                                break
                        if not added:
                            #print(players)
                            #print("edge case 2")
                            moves.append([players[-1][0], players[0][0]])
                            players[0][1] = max(0, players[0][1] - 1)
                            players[-1][1] = max(0, players[-1][1] - 1)
                            players.sort(key=itemgetter(1), reverse=True)
                            while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
                                # print(players)
                                players[0][1] = max(0, players[0][1] - 1)
                                players[1][1] = max(0, players[1][1] - 1)
                                moves.append([players[0][0], players[1][0]])
                                players.sort(key=itemgetter(1), reverse=True)
                            if players[0][1] != players[-1][1]:
                                added = False
                                for m in moves:
                                    if not players[0][0] in m:
                                        m.append(players[0][0])
                                        players[0][1] = max(0, players[0][1] - 1)
                                        added = True
                                        break
                                if not added:
                                    # print(players)
                                    #print("edge case 3")
                                    moves.append([players[-1][0], players[0][0]])
                                    players[0][1] = max(0, players[0][1] - 1)
                                    players[-1][1] = max(0, players[-1][1] - 1)
                                    players.sort(key=itemgetter(1), reverse=True)
                                    while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
                                        # print(players)
                                        players[0][1] = max(0, players[0][1] - 1)
                                        players[1][1] = max(0, players[1][1] - 1)
                                        moves.append([players[0][0], players[1][0]])
                                        players.sort(key=itemgetter(1), reverse=True)
                                    if players[0][1] != players[-1][1]:
                                        added = False
                                        for m in moves:
                                            if not players[0][0] in m:
                                                m.append(players[0][0])
                                                players[0][1] = max(0, players[0][1] - 1)
                                                added = True
                                                break
                                        if not added:
                                            # print(players)
                                            #print("edge case 4")
                                            moves.append([players[-1][0], players[0][0]])
                                            players[0][1] = max(0, players[0][1] - 1)
                                            players[-1][1] = max(0, players[-1][1] - 1)
                                            players.sort(key=itemgetter(1), reverse=True)
                                            while players[0][1] != players[-1][1] and players[1][1] != players[-1][1]:
                                                # print(players)
                                                players[0][1] = max(0, players[0][1] - 1)
                                                players[1][1] = max(0, players[1][1] - 1)
                                                moves.append([players[0][0], players[1][0]])
                                                players.sort(key=itemgetter(1), reverse=True)
                                            if players[0][1] != players[-1][1]:
                                                added = False
                                                for m in moves:
                                                    if not players[0][0] in m:
                                                        m.append(players[0][0])
                                                        players[0][1] = max(0, players[0][1] - 1)
                                                        added = True
                                                        break
                                                if not added:
                                                    # print(players)
                                                    print("edge case 5")


            players.sort(key=itemgetter(1), reverse=True)
            print(players[-1][1])
            print(len(moves))
            for m in moves:
                print("".join(["1" if x + 1 in m else "0" for x in range(self.players)]))
        else:
            if self.rating[0] == self.rating[1]:
                print(self.rating[0])
                print("0")
            else:
                print("0")
                print(max(self.rating))
                for x in range(max(self.rating)):
                    print("11")

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask730ASolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()

# https://codeforces.com/problemset/problem/730/A
# 
 
import heapq

def solve_for_0(d, max_, ans):
    pos_M = list(d[max_])[0]
    pos_m = list(d[0])[0]
    
    for _ in range(max_):
        ans.append([pos_M, pos_m])   

def solve_one_seg(d, max_, min_, ans):
    seg = list(d[max_])
    n = len(seg)
    
    if n <= 5:
        for _ in range(max_ - min_):
            ans.append(seg)
    else:
        ori = []
        for i in range(0, n, 2):
            if i == n-1:
                ori[-1].append(seg[i])
            else:
                ori.append([seg[i], seg[i+1]])
        
        for _ in range(max_ - min_):
            ans.extend(ori)    
    
    
def push(d, x, val, i):
    if x not in d:
        d[x] = set()
        
    if val == 1:    
        d[x].add(i)
    else:
        d[x].remove(i)
        
    if len(d[x]) == 0:
        del d[x]
    
def check(d):
    if len(d) != 2:
        return 'none', None
    
    max_ = max(list(d.keys()))
    min_ = min(list(d.keys()))
    
    if len(d[max_]) >= 2:
        return 'seg', [max_, min_]
    
    elif min_ == 0:
        return '0', [max_]
    
    return 'none', None

def pr(ans, n):
    print(len(ans))
    arr = [[0]*n for _ in range(len(ans))]
    
    for i, val in enumerate(ans):
        for ind in val:
            arr[i][ind] = 1
    S = ''        
    for s in arr:
        S += ''.join([str(x) for x in s]) 
        S += '\n'
    print(S)    
    
#5
#4 5 1 7 4
n   = int(input())#len(arr) 
arr = list(map(int, input().split()))#[1,3,1,3,2,3,2,3,2,3,2,3,2,3]
ans = []
Q   = []
d   = {}

for i, x in enumerate(arr):
    push(d, x, 1, i)
    heapq.heappush(Q, (-x, x, i))
    
if len(d) == 1:
    print(list(d.keys())[0])
    print(0)
else:
    while True: 
        type_, arg = check(d)  
        if  type_ == 'none':
            val1, num1, i1 = heapq.heappop(Q)
            val2, num2, i2 = heapq.heappop(Q)
            push(d, num1, -1, i1)
            push(d, num2, -1, i2)
            ans.append([i1, i2])
    
            new1 = max(0, num1-1)
            new2 = max(0, num2-1)
            heapq.heappush(Q, (-new1, new1, i1))
            heapq.heappush(Q, (-new2, new2, i2))
            push(d, new1, 1, i1)
            push(d, new2, 1, i2)
        
        elif type_ == 'seg':
            max_, min_ = arg[0], arg[1]
            solve_one_seg(d, max_, min_, ans)
            
            print(min_)
            pr(ans, n)
            break
        else:
            max_ = arg[0]
            solve_for_0(d, max_, ans)
            
            print(0)
            pr(ans, n)
            break