There are $n$ people in a row. The height of the $i$-th person is $a_i$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $1$. For example, let heights of chosen people be $[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$, where $k$ is the number of people you choose. Then the condition $|a_{i_j} - a_{i_{j + 1}}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|a_{i_1} - a_{i_k}| \le 1$ should be also satisfied. $|x|$ means the absolute value of $x$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of people.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the height of the $i$-th person.


-----Output-----

In the first line of the output print $k$ — the number of people in the maximum balanced circle.

In the second line print $k$ integers $res_1, res_2, \dots, res_k$, where $res_j$ is the height of the $j$-th person in the maximum balanced circle. The condition $|res_{j} - res_{j + 1}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|res_{1} - res_{k}| \le 1$ should be also satisfied.


-----Examples-----
Input
7
4 3 5 1 2 2 1

Output
5
2 1 1 2 3

Input
5
3 7 5 1 5

Output
2
5 5 

Input
3
5 1 4

Output
2
4 5 

Input
7
2 2 3 2 1 2 2

Output
7
1 2 2 2 2 3 2

Difficulty: introductory

Starter code:

Solutions:
# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = self.next_line()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_line(self, _map=str):
        return list(map(_map, sys.stdin.readline().split()))

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        x = sorted([self.next_int() for _ in range(0, n)])
        ml = -1
        _i = 0
        _j = 0
        j = 0
        for i in range(0, n):
            j = max(j, i)
            while j + 1 < n and x[j + 1] == x[i]:
                j += 1
            while j + 2 < n and x[j + 2] == x[j] + 1:
                j += 2
                while j + 1 < n and x[j + 1] == x[j]:
                    j += 1
            jj = j
            if j + 1 < n and x[j + 1] == x[j] + 1:
                jj += 1
            if jj - i > ml:
                ml = jj - i
                _i = i
                _j = jj
        a = []
        b = []
        i = _i
        while i <= _j:
            a.append(x[i])
            i += 1
            while i <= _j and x[i] == a[-1]:
                b.append(x[i])
                i += 1
        print(ml + 1)
        print(' '.join([str(x) for x in (a + b[::-1])]))


def __starting_point():
    Main().solve()

__starting_point()

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #555 (Div. 3)

Problem F. Maximum Balanced Circle

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '0.1'
__date__ = '2019-04-26'

import sys


def solve(n, a):
    max_a = max(a)
    counter = [0 for i in range(max_a+1)]
    for ai in a:
        counter[ai] += 1
    best_group = []
    best_total = 0
    curr = 1
    while curr <= max_a:
        if counter[curr] > 0:
            curr_group = [curr]
            curr_total = counter[curr]
            curr += 1
            if curr > max_a:
                break
            while counter[curr] > 1:
                curr_group.append(curr)
                curr_total += counter[curr]
                curr += 1
                if curr > max_a:
                    break
            if curr > max_a:
                break
            if counter[curr] > 0:
                curr_group.append(curr)
                curr_total += counter[curr]
            if curr_total > best_total:
                best_group = curr_group
                best_total = curr_total
        else:
            curr += 1
    if curr_total > best_total:
        best_group = curr_group
        best_total = curr_total

    seq = best_group
    for i in best_group[::-1]:
        seq += [i] * (counter[i] - 1)
    return (best_total, seq)

def main(argv=None):
    n = int(input())
    a = list(map(int, input().split()))
    total, seq = solve(n, a)
    print(total)
    print(' '.join(map(str, seq)))
    return 0

def __starting_point():
    STATUS = main()
    return(STATUS)


__starting_point()

rint = lambda: int(input())
rmint = lambda: map(int, input().split())
rlist = lambda: list(rmint())

n = rint()
a = [0, 0] * (10 ** 5 + 1)
for c in rlist(): a[c] += 1
pr = 0; t = 0; ans = 0; g = 0
for i in range(1, 2 * 10 ** 5 + 1):
    if a[i] < 2:
        t = 0
        pr = a[i]
    else:
        t += a[i]
    nx = a[i+1]
    if pr + t + nx > ans:
        ans = pr + t + nx
        g = i
r = g+1; l = g+1
while a[l-1] > 1: l -= 1
while a[r] > 1: r += 1
print(ans)
# print(l,r)
def out(x,y=1):
    while y:
        print(x,end=' ')
        y -= 1
for i in range(l,r): out(i)
out(r,a[r])
for i in range(r-1,l-1,-1): out(i,a[i]-1)
out(l-1,a[l-1])


kk=lambda:map(int,input().split())
# k2=lambda:map(lambda x:int(x)-1, input().split())
ll=lambda:list(kk())
n = int(input())
d = {}
for v in kk():
	if v not in d: d[v] = 0
	d[v]+=1
k = list(d.keys())
k.sort()
i = 0
m = 0
while i < len(k):
	start =x= k[i]
	total = d[start]
	while i+1 < len(k) and k[i]+1 == k[i+1]:
		i+=1
		total+=d[k[i]]
		if d[k[i]] == 1:
			if total > m: m,mi = total,(start, k[i])
			break
	else: 
		i+=1
		if total > m: m,mi = total,(start, k[i-1])
print(m)
tbp = []
for i in range(mi[0], mi[1]+1):
	tbp.extend([i]*(d[i]-1))
print()
for i in range(mi[1], mi[0]-1, -1):
	tbp.append(i)
print(*tbp)

kk=lambda:map(int,input().split())
ll=lambda:list(kk())
n = int(input())
d = {}
for v in kk():
	if v not in d: d[v] = 0
	d[v]+=1
k = list(d.keys())
k.sort()
i = 0
m = 0
while i < len(k):
	start =x= k[i]
	total = d[start]
	while i+1 < len(k) and k[i]+1 == k[i+1]:
		i+=1
		total+=d[k[i]]
		if d[k[i]] == 1:
			if total > m: m,mi = total,(start, k[i])
			break
	else: 
		i+=1
		if total > m: m,mi = total,(start, k[i-1])
print(m)
tbp = []
for i in range(mi[0], mi[1]+1):
	tbp.extend([i]*(d[i]-1))
print()
for i in range(mi[1], mi[0]-1, -1):
	tbp.append(i)
print(*tbp)

n=int(input())
a=list(map(int,input().split()))
cnt=[0]*(200005)
for i in range(0,n):
    cnt[a[i]]+=1
ans=0
ansl=0
ansr=0
l=1
N=200001
while (l<=N):
    if cnt[l]==0:
        l+=1
    else:
        r=l
        now=0
        while (r<=N):
            if cnt[r]==0:
                r-=1
                break
            elif cnt[r]==1 and l!=r:
                now+=cnt[r]
                break
            else:
                now+=cnt[r]
                r+=1
        if now>ans:
            ansl=l
            ansr=r
            ans=now
        #print(l,r,now)
        if l==r:
            l=r+1
        else:
            l=r
seq=[]
for i in range(ansl,ansr+1):
    seq.append(i)
    cnt[i]-=1
for i in range(ansr,ansl-1,-1):
    while cnt[i]>0:
        seq.append(i)
        cnt[i]-=1
print(len(seq))
for i in seq:
    print(i,end=" ")
            


import sys
from collections import Counter
input = sys.stdin.readline

n=int(input())
A=Counter(list(map(int,input().split())))
M=max(A)

DP0=[0]*(M+1)
DP1=[0]*(M+1)

for i in range(M+1):
    if A[i]>=2 and A[i-1]>=2:
        DP0[i]=DP0[i-1]+A[i]

    elif A[i]>=2 and A[i-1]==1:
        DP0[i]=1+A[i]

    elif A[i]>=2 and A[i-1]==0:
        DP0[i]=A[i]

    elif A[i]==1:
        DP0[i]=1

    if A[i]>=2:
        DP1[i]=DP0[i]
    elif A[i]==1:
        DP1[i]=DP0[i-1]+1

ANS=max(DP1)
print(ANS)

BIG=DP1.index(ANS)
for i in range(BIG-1,-1,-1):
    if A[i]==1:
        SMALL=i
        break
    if A[i]==0:
        SMALL=i+1
        break

ANSLIST=list(range(SMALL,BIG+1))

for i in range(BIG,SMALL-1,-1):
    for k in range(A[i]-1):
        ANSLIST.append(i)

print(*ANSLIST)


n=int(input())
a=list(map(int,input().split()))
cnt=[0]*(200005)
for i in range(0,n):
    cnt[a[i]]+=1
ans=0
ansl=0
ansr=0
l=1
N=200001
while (l<=N):
    if cnt[l]==0:
        l+=1
    else:
        r=l
        now=0
        while (r<=N):
            if cnt[r]==0:
                r-=1
                break
            elif cnt[r]==1 and l!=r:
                now+=cnt[r]
                break
            else:
                now+=cnt[r]
                r+=1
        if now>ans:
            ansl=l
            ansr=r
            ans=now
        #print(l,r,now)
        if l==r:
            l=r+1
        else:
            l=r
seq=[]
for i in range(ansl,ansr+1):
    seq.append(i)
    cnt[i]-=1
for i in range(ansr,ansl-1,-1):
    while cnt[i]>0:
        seq.append(i)
        cnt[i]-=1
print(len(seq))
for i in seq:
    print(i,end=" ")
            


n = int(input())

a = [int(x) for x in input().split()]

if n == 1:
    print(1)
    print(a[0])
    return

a.sort()

b = [a[0]]
cnt = [0]*(200*1000+1)

cnt[a[0]]+=1
for i in range(1,n):
    cnt[a[i]]+=1
    if a[i-1] != a[i]:
        b.append(a[i])

l=0
r=1
ans = cnt[a[0]]

i=0
while i < len(b):
    j=i+1
    su = cnt[b[i]]
    while j<len(b) and b[j]-b[j-1]==1 and cnt[b[j]]>=2:
        su+=cnt[b[j]]
        j+=1
    tmp = j
    if j<len(b) and b[j]-b[j-1] == 1:
        su+=cnt[b[j]]
        j+=1
    if ans<su:
        ans = su
        l = i
        r = j
    i=tmp


print(ans)
for i in range(l,r):
    print(b[i],end = ' ')
for i in range(r-1,l-1,-1):
    for j in range(0,cnt[b[i]]-1):
        print(b[i],end = ' ')


n = int(input())
a = [int(x) for x in input().split()]
c =[0]*2*100007
s =[0]*2*100007
result=0
dis=0
result_list=[]
for i in a:
    c[i]+=1
for i in range(len(c)):
    if c[i]>0:
        s[i]=c[i]
        result=c[i]
        dis=i
        break
for i in range(dis+1,len(c)):
    if c[i]>1:
        s[i]=max(s[i-1]+c[i],c[i-1]+c[i])
    else:
        s[i]=0
for i in range(1,len(s)):
    if c[i]+s[i-1]>result:
        result=c[i]+s[i-1]
        dis=i
    if c[i]+c[i-1]>result:
        result=c[i]+c[i-1]
        dis=i
for i in range(dis-1,-1,-1):
    if c[i]==1:
        pos=i
        break
    if c[i]==0:
        pos=i+1
        break
print(result)
for i in range(pos,dis+1):
    print(i,end=" ")
for i in range(dis,pos-1,-1):
    for j in range(1,c[i]):
        print(i,end=" ")
    

import io
import os
from collections import defaultdict
from sys import stdin, stdout
#input = stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = sorted(set(a))

    d = {}
    for val in s:
        d[val] = 0

    for val in a:
        d[val] += 1

    max_len = 1
    res = [a[0]]

    # len 2
    for j in range(len(s)-1):
        if d[s[j]] == 1 and d[s[j+1]] == 1 and s[j+1]-s[j]==1:
            max_len = 2
            res = [s[j], s[j+1]]
            break

    # len > 2
    start = 0
    while start < len(s) and d[s[start]] == 1:
        start += 1

    while start < len(s):
        if start < len(s):
            l = start
            r = start
            while l > 0 and d[s[l-1]] > 1 and s[l]-s[l-1]==1:
                l -= 1
            while r < len(s)-1 and d[s[r+1]] > 1 and s[r+1]-s[r]==1:
                r += 1

            if l > 0 and s[l]-s[l-1] == 1:
                l -= 1
            if r < len(s)-1 and s[r+1]-s[r] == 1:
                r += 1

            total = 0
            for j in range(l, r+1):
                total += d[s[j]]

            if total > max_len:
                max_len = total
                res = []
                for j in range(l, r+1):
                    res.append(s[j])
                    d[s[j]] -= 1
                for j in range(r, l-1, -1):
                    while d[s[j]] > 0:
                        res.append(s[j])
                        d[s[j]] -= 1
            start = r+1
            while start < len(s) and d[s[start]] == 1:
                start += 1

    print(len(res))
    print(*res)

def __starting_point():
    main()

__starting_point()

def unique(a):
    if len(a) == 0:
        return a

    i = 1
    j = 1
    last = a[0]
    while j < len(a):
        if a[j] > last:
            last = a[j]
            a[i], a[j] = a[j], a[i]
            i += 1
        j += 1

    return a[:i]

def expand(cir):
    e = []
    for i in range(len(cir)):
        e.append(cir[i][0])
    for i in range(-1, -len(cir) - 1, -1):
        for _ in range(cir[i][1] - 1):
            e.append(cir[i][0])

    return e


n = int(input())
a = list(map(int, input().split(' ')))

c = dict()
for x in a:
    if x in c:
        c[x] += 1
    else:
        c[x] = 1

a.sort()
a = unique(a)
n = len(a)

cir = []
cirsize = 0

i = 0
while i < n:
    j = i + 1
    while j < n and a[j] == a[j - 1] + 1 and c[a[j]] > 1:
        j += 1
    if j < n and a[j] == a[j - 1] + 1:
        j += 1
    
    sz = 0
    for p in range(i, j):
        sz += c[a[p]]
    if sz > cirsize:
        cir.clear()
        for p in range(i, j):
            cir.append((a[p], c[a[p]]))
        cirsize = sz
    
    if c[a[j - 1]] == 1 and i != j - 1:
        i = j - 1
    else:
        i = j

print(cirsize)
print(*expand(cir))


rint = lambda: int(input())
rmint = lambda: map(int,input().split())
rlist = lambda: list(rmint())

n = rint()
lst = rlist()

cnt = {}
for nb in lst:
    if nb not in cnt :
        cnt[nb] = 1
    else:
        cnt[nb] +=1 
arr = sorted(list(cnt.keys()))
N = len(arr)


# print(N,arr, cnt)
left, right, k = 0, 0, cnt[arr[0]]
left_best, right_best, k_best = 0, 0, cnt[arr[0]]

while right < N:
    while right + 1 < N and arr[right+1] == arr[right] +1 and cnt[arr[right]] >=2:
        right = right +1
        k += cnt[arr[right]]

    if k_best  < k:
        left_best, right_best, k_best = left, right, k

    if right +1 >= N:
        break
    elif arr[right+1] != arr[right] + 1 :
        left = right+1
        right = right +1
        k = cnt[arr[left]]
    else:
        left = right
        right = right+1
        k = cnt[arr[left]] +  cnt[arr[right]]

# print(left_best, right_best, k_best,"___________")
print(k_best)
for idx in range(left_best, right_best+1):
    print((str(arr[idx]) + " ") * (cnt[arr[idx]]-1), end = "")

for idx in range(right_best, left_best-1,-1):
    print((str(arr[idx]))+" ", end= "")
print("")


def create(s, e, cnt):
    arr = []
    for i in range(s, e+1):
        arr.extend([i for _ in range(cnt[i]-1)])
    arr.extend(list(range(e, s-1,-1)))
    return arr

n = int(input())
a = list(map(int, input().split()))

def solve(a):
    cnt = [0] * 200001
    for x in a:
        cnt[x]+=1
    
    block = [] 
    max_  = 0 
    i = 0
    s, e = None, None

    while i<len(cnt):
        if cnt[i]>1:
            s=i
            while i+1<len(cnt) and cnt[i+1]>1:
                i+=1
        
            e=i
            if s>=1 and cnt[s-1]>0:
                s-=1
            if e+1<len(cnt) and cnt[e+1]>0:
                e+=1
            
            block.append([s, e])
            i=e+1
        else:
            i+=1
            
    pos=-1
    for i, [s, e] in enumerate(block):
        sum_ = 0
        for j in range(s, e+1):
            sum_+=cnt[j]
        
        if max_ < sum_:
            max_ = sum_
            pos  = i
            
    if max_ >= 2:
        arr = create(block[pos][0], block[pos][1], cnt)
        return len(arr), ' '.join([str(x) for x in arr])
    else:
        for i in range(1, 200000):
            if cnt[i] == 1 and cnt[i+1] == 1:
                return 2, str(i)+' '+str(i+1)
        return 1, str(a[0])
    
length, arr = solve(a)

print(length)
print(arr)

def solve():
    n = int(input())
    a = sorted(map(int, input().split()))
    ans = (1, 0)
    cur = [a[0]]
    for i in range(1, n):
        if a[i] - a[i - 1] > 1:
            ans = max(ans, (len(cur), i - 1))
            cur.clear()
        elif a[i - 1] < a[i] and (i == n - 1 or a[i] < a[i + 1]):
            cur.append(a[i])
            ans = max(ans, (len(cur), i))
            cur.clear()
        cur.append(a[i])
    ans = max(ans, (len(cur), n - 1))
    print(ans[0])
    ans1 = []
    ans2 = []
    for i in a[ans[1]-ans[0]+1:ans[1]+1]:
        if not ans1 or ans1[-1] != i:
            ans1.append(i)
        else:
            ans2.append(i)
    print(*(ans1 + ans2[::-1]))


for _ in range(1):
    solve()


import sys
from collections import namedtuple
from itertools import groupby
input = sys.stdin.readline

def main():
    Data = namedtuple('Data', ['arr', 'l', 'r'])

    _ = int(input())
    a = list(map(int, input().split()))

    f = [ [0, 0] for i in range(max(a) + 2) ]

    for x in a:
        f[x][0] = x
        f[x][1] += 1

    best = 0
    opt = None

    for k, v in groupby(f, key = lambda x: 1 if x[1] else 0):
        if not k:
            continue

        v = list(v)
        i = lst = len(v) - 1
        t = [0] * (len(v) + 1)

        while i >= 0:
            t[i] = t[i + 1] + v[i][1]

            if t[i] - t[lst + 1] > best:
                best = t[i] - t[lst + 1]
                opt = Data(v, i, lst)

            if v[i][1] == 1:
                lst = i

            i -= 1

    ans = []

    for i in range(opt.l, opt.r + 1):
        ans.append(opt.arr[i][0])
        opt.arr[i][1] -= 1

    for i in range(opt.r, opt.l - 1, -1):
        while opt.arr[i][1]:
            ans.append(opt.arr[i][0])
            opt.arr[i][1] -= 1

    print(len(ans))
    print(" ".join(map(str, ans)))

main()