
# Vo všetkých vstupoch platí $1\leq n\leq 200\,000$ a $\forall i: 1\leq h_i\leq 10^9$.
# Rôzne sady majú rôznu maximálnu hodnotu $n$: 20, 20, 5000, 5000, 200000, 200000
# Navyše v sadách 1, 3 a 5 platí, že všetky hodnoty $h_i$ vo vstupe sú navzájom rôzne.

from itertools import zip_longest as zipl
from random import randint, seed, shuffle, sample, choice
from string import ascii_lowercase as abc
seed(47)

SAMPLES = [ [47,42,47,42,47,47,42], [47,42,47,43,48,48,42], [47,43,47,42,48,48,42], [1955,1840,1937,1837,2004,2024,1232,1660,1190,1946] ]
MAXN = [ None, 20, 20, 5000, 5000, 200000, 200000 ]

def save(fname,data):
    f = open(fname,'w')
    print(len(data), file=f)
    print(*data, file=f)
    f.close()

for sample, letter in zip(SAMPLES, abc):
    save(f'00.sample.{letter}.in', sample)

def increasing(N):
    data = set()
    while len(data) < N: data.add( randint(1,10**9) )
    return list(sorted(data))

def decreasing(N):
    return list(reversed(increasing(N)))

def toothy(N):
    data = set()
    while len(data) < N: data.add( randint(1,10**9) )
    data = list(sorted(data))
    small, large = data[:N//2], data[N//2:]
    answer = []
    for pair in zipl(large,small):
        for x in pair:
            if x is not None:
                answer.append(x)
    return answer

def random(N, minval=1, maxval=10**9):
    return [ randint(minval,maxval) for _ in range(N) ]

def random_distinct(N, minval=1, maxval=10**9):
    data = set()
    while len(data) < N: data.add( randint(minval,maxval) )
    data = list(data)
    shuffle(data)
    return data

def bigsides(N):
    blocks = (N-2)//2
    answer = []
    currh = 47
    for n in range(blocks):
        answer.append(currh)
        currh += 3
        answer.append(currh)
        currh -= 1
    answer = [ 47000000 ] + answer + [ 42000000 ]
    return answer

def himalayas(N):
    answer = []
    lo, hi = 20, 42
    while len(answer)+2 <= N: answer += [lo,hi]
    if len(answer)+1 == N: answer += [lo]
    answer[N//2] = 47
    return answer

def himalayas2(N):
    answer = []
    while len(answer)+2 <= N:
        answer.append(randint(1,10**7))
        answer.append(42000000)
    if len(answer)+1 == N:
        answer.append(randint(1,10**7))
    answer[N//2] = 47000000
    return answer

def plateau(N):
    assert N >= 10
    answer = [1,2] + [47]*(N-4) + [2,1]
    for i in range(20):
        answer[randint(2,N-3)] = 42
    return answer

def plateauplus(N):
    answer = plateau(N)
    answer[randint(2,N-3)] = 48
    return answer

def updown(N):
    answer = []
    for n in range(N-1):
        if n%2 == 0:
            x = 3*N - n
        else:
            x = n
        answer.append(randint(100*x,100*x+99))
    answer.append(10**9)
    return answer

TESTS = [ [] for _ in range(7) ]

TESTS[1].append([47])
TESTS[1].append([47,42])
TESTS[1].append([42,47])
TESTS[1].append([42,47,43])
TESTS[1].append([48,42,47])

TESTS[2].append([47])
TESTS[2].append([47,47])
TESTS[2].append([47,47,42,42])
TESTS[2].append([42,42,47,47])
TESTS[2].append([47,47,1,42,42])
TESTS[2].append([42,42,1,47,47])
TESTS[2].append([42,2,42,3,47,2,47])
TESTS[2].append(random(17,1,5))
TESTS[2].append(random(20,1,10))
TESTS[2].append(random(20,100,150))

TESTS[4].append(random(5000,42,47))
TESTS[4].append(random(5000,420,470))
TESTS[4].append(random(5000,4200,4700))

TESTS[6].append(random(200000,42,47))
TESTS[6].append(random(200000,420,470))
TESTS[6].append(random(200000,4200,4700))
TESTS[6].append(random(200000,42000,47000))

for batch in [1,3,5]:
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(increasing(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(decreasing(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(toothy(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(random_distinct(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(random_distinct(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(bigsides(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(updown(N))

for batch in [2,4,6]:
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(himalayas(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(himalayas2(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(plateau(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(plateauplus(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(random(N))
    N = randint( MAXN[batch]-3, MAXN[batch] )
    TESTS[batch].append(bigsides(N))

for batch in [1,3,5]:
    for i, test in enumerate(TESTS[batch]):
        # print(batch, i, abc[i])
        assert len(test) == len(set(test))

for batch in range(1,7):
    for i, test in enumerate(TESTS[batch]):
        # print(batch, i, abc[i])
        assert len(test) > 0 and len(test) <= MAXN[batch]
        assert min(test) >= 1 and max(test) <= 10**9
        save(f'{batch:02d}{abc[i]}.in', test)

