from itertools import permutations
from random import randint, seed, shuffle, sample
seed(47)

MAXN = 500000

def shuffled(seq):
    sc = seq[:]
    shuffle(sc)
    return sc

def randomset(sz,gen):
    answer = set()
    while len(answer) < sz: answer.add( gen() )
    return sorted([x for x in answer])

def fewpivots(pc):
    data = randomset( MAXN, lambda:randint(0,10**9) )
    pivots = randomset( pc, lambda:randint(0,MAXN-1) )
    pivots = [-1] + pivots
    answer = []
    for i in range(1,pc+1):
        answer += shuffled( data[ pivots[i-1]+1 : pivots[i] ] )
        answer.append( data[ pivots[i] ] )
    answer += shuffled( data[ pivots[pc]+1 : ] )
    return answer

def manypivots(sc):
    data = randomset( MAXN, lambda:randint(0,10**9) )
    for i in range(sc):
        x = randint(0,MAXN-101)
        y = x + randint(1,100)
        data[x], data[y] = data[y], data[x]
    return data

def save(tid,seq):
    f = open(tid,'w')
    f.write('{}\n{}\n'.format(len(seq),' '.join(str(x) for x in seq)))
    f.close()
    print('Saved {} (len {} sum {}) into {}'.format(seq[:5],len(seq),sum(seq),tid))

save('00.sample.a.in',[20,10,30,50,40,60])
save('00.sample.b.in',[300,200,100])

tid = 0
tid += 1 ; save('{:02d}.in'.format(tid),[47])
tid += 1 ; save('{:02d}.in'.format(tid),[42,47])
tid += 1 ; save('{:02d}.in'.format(tid),[47,42])

for perm in permutations([42,47,147]):
    tid += 1 ; save('{:02d}.in'.format(tid),perm)

for perm in permutations([42,47,147,174]):
    tid += 1 ; save('{:02d}.in'.format(tid),perm)

for i in range(10):
    tid += 1 ; save('{:02d}.in'.format(tid),shuffled([x for x in range(10*(i+1))]))

tid += 1 ; save('{:02d}.in'.format(tid),range(MAXN))

for pc in range(1,6):
    for n in range(3):
        tid += 1 ; save('{:02d}.in'.format(tid),fewpivots(pc))

for n in range(10):
    tid += 1 ; save('{:02d}.in'.format(tid),manypivots(10*(n+1)))

tid += 1 ; save('{:02d}.in'.format(tid), [1,2,499998] + [x for x in range(4,499998)] + [3,499999,500000] )