Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))
a=0
L.sort(reverse=True)
for i in range(0,N-2,1):
  for j in range(i+1,N-1,1):
    for q in range(j+1,N,1):
        if L[i]<L[j]+L[q] and L[j]<L[i]+L[q] and L[q]<L[i]+L[j]:
          a+=1
        else:
          break
print(a)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))

L.sort()
a=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a+=bisect_left(L,L[i]+L[j])-j-1
print(a)
### BUGGY CODE ###

from fractions import gcd
a, b = map(int, input().split())

def prime_factorize(n):
  border = int(n**(1/2))
  ans = []
  i = 2
  while(i <= n):
    if n % i == 0:
      ans.append(i)
      n = n // i
      i = 2
    else:
      i += 1
  return ans

list_a = list(set(prime_factorize(a)))
list_b = list(set(prime_factorize(b)))

list_ab = set(list_a) & set(list_b)
ans = len(list_ab) + 1
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())

def factorize(n):
  
  arr = []
  temp = n
  
  for i in range(2, int(n**(1/2))+1):
    if temp % i == 0:
      while temp % i == 0:
        temp //= i
        arr.append(i)

  if temp != 1:
    arr.append(temp)

  return arr

set_a = set(factorize(a))
set_b = set(factorize(b))

set_ab = set(set_a) & set(set_b)
ans = len(set_ab) + 1
print(ans)
### BUGGY CODE ###

def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append([s - x, 1, x])  # 通行止め追加
        events.append([t - x, -1, x])  # 通行止め削除

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    for q in range(Q):
        d = int(input())
        while d >= events[i][0]:
            time, event, x = events[i]
            if event == 1:
                closing.add(x)
                heapq.heappush(hq, x)

            elif event == -1:
                closing.remove(x)

            i += 1

        while hq and (hq[0] not in closing):
            heapq.heappop(hq)

        if hq:
            print(hq[0])
        else:
            print(-1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append((s - x, 1, x))  # 通行止め追加
        events.append((t - x, -1, x))  # 通行止め削除

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

            if hq:
                print(hq[0])
            else:
                print(-1)

        i += 1


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for _ in range(operations):
        dists_new = [0] * number
        for i, d in enumerate(dists):
            start = max(0, i - d)
            end = min(i + d, number - 1)
            for j in range(start, end + 1):
                dists_new[j] += 1
        dists = dists_new
        if min(dists) == number:
            # すべての光が両端まで届く，変化しなくなる。
            break

    print(*dists)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import permutations

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

Flag = False

perm = list(permutations(range(n)))

for item in perm:
    flag = True
    for i in range(n):
        if line[item[i]] != line[item[(i-1)%n]] ^ line[item[(i+1)%n]]:
            flag = False
    if flag:
        Flag = True

if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
line = list(map(int,input().split( )))
s = list(set(line))

if n%3==0 and 0 in line and line.count(0)==n//3 and len(s)<=2:
    print('Yes')
elif  n%3==0 and len(s)==3 and s[0]^s[1]==s[2] and s[1]^s[2]==s[0] and line.count(s[0])==n//3 and line.count(s[1])==n//3:
    print('Yes')
elif s == [0]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a,v = list(map(int,input().split()))
b,w = list(map(int,input().split()))
t = int(input())

output = "NO"

for i in range(t):
  if a > b:
    a -= v
    b -= w
  elif a < b:
    a += v
    b += w
  
  if a == b:
    output="YES"
    break

print(output)

### FIXED CODE ###

a,v = list(map(int,input().split()))
b,w = list(map(int,input().split()))
t = int(input())

import sys
dis = abs(a-b)
tume = v-w 
if v <= w:
  print("NO")
  sys.exit()

if dis%tume == 0 and dis//tume <= t:
  print("YES")
elif dis <= (t-1)*tume:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

s = input()
K = int(input())

S = []
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        if not(s[i:j] in S):
            S.append(s[i:j])
        # print(s[i:j])

S.sort()
print(S[K-1])


### FIXED CODE ###

s = input()
k = int(input())



# S = []
# for i in range(len(s)+1):
#     for j in range(i+1,len(s)+1):
#         if not(s[i:j] in S):
#             S.append(s[i:j])
#         # print(s[i:j])

S = set()

for i in range(1, k+1):
    for j in range(len(s)-i+1):
            S.add(s[j:j+i])

T = sorted([x for x in S])

print(T[k-1])
### BUGGY CODE ###

INF = float('inf')

def read_key():
  a, _ = map(int, input().split())
  m = 0
  for c in map(int, input().split()):
    m |= 1 << (c - 1)
  return (a, m)

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [[INF] * (1 << N) for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
  a, m = keys[i]
  for j in range(1 << N):
    if dp[i][j] == INF:
      continue
    dp[i + 1][j | m] = min(dp[i + 1][j | m], dp[i][j] + a)
    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
if dp[M][(1 << N) - 1] == INF:
  print(-1)
else:
  print(dp[M][(1 << N) - 1])

### FIXED CODE ###

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

    N, M = map(int, input().split())
    keys = [read_key() for _ in range(M)]

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

    if dp[M][(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[M][(1 << N) - 1])


main()
### BUGGY CODE ###

n = int(input())
a = [int(s) for s in input().split()]
b = a.copy()
max_index = a.index(max(a))
last_index = len(a)
while(last_index > 0):
    for i in range(max_index,last_index):
        b[i] = b[max_index]
    last_index = max_index
    if last_index == 0:
        break
    max_index = b.index(max(a[:last_index]))

count = 0
for i in range(len(a)):
    count += b[i] - a[i]
print(count)

### FIXED CODE ###

n = int(input())
a = [int(s) for s in input().split()]
count = 0
max = a[0]
for i in range(1, len(a)):
    if max >  a[i]:
        if a[i - 1] > max:
            max = a[i - 1]
        count += max - a[i]
    else:
        max = a[i]
print(count)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

graph = defaultdict(set)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

arr = [0] * (n + 1)

for i in range(q):
    p, x = map(int, input().split())
    arr[p] += x


def solve(graph, arr):
    curr, root = 1, -1
    visited = [True] * 2 + [False] * (n - 1)

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if visited[leaf]:
                continue
            arr[leaf] += arr[curr]
            visited[leaf] = True
            dfs(leaf, curr)

        return arr

    return dfs(curr, root)


ans = solve(graph, arr)

print(*ans[1:])

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

graph = defaultdict(set)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

arr = [0] * (n + 1)

for i in range(q):
    p, x = map(int, input().split())
    arr[p] += x


def solve():
    stack = [1]
    visited = [True] * 2 + [False] * (n - 1)

    while stack:
        curr = stack.pop()
        for leaf in graph[curr]:
            if visited[leaf]:
                continue
            stack.append(leaf)
            visited[leaf] = True
            arr[leaf] += arr[curr]

    return arr


arr = solve()

print(*arr[1:])
### BUGGY CODE ###

from collections import Counter
N, K, Q = map(int, input().strip().split())
ansl = [int(input().strip()) for _ in range(Q)]
countl = Counter(ansl)
for i in range(N):
    pid = i+1
    if sum([v for k,v in countl.items() if k != pid]) < K:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

from collections import Counter
N, K, Q = map(int, input().strip().split())
ansl = [int(input().strip()) for _ in range(Q)]
countl = Counter(ansl)
sumcountl = sum(countl.values())
for i in range(N):
    print('Yes') if sumcountl-countl[i+1] < K else print('No')
### BUGGY CODE ###

def is_triangle(a, b, c):
    return a < b + c and b < c + a and c < a + b


def main():
    N = int(input())
    L = list(map(int, input().split(' ')))
    L.sort()
    cnt = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if not is_triangle(L[j + 1], L[i], L[j]):
                # cannot construct with L[k] for all k > j
                continue
            if is_triangle(L[N - 1], L[i], L[j]):
                # can construct with L[k] for all k > j
                cnt += N - 1 - j
                continue
            # binary search
            ok = j + 1
            ng = N - 1
            while abs(ok - ng) > 1:
                mid = (ok + ng) // 2
                if is_triangle(L[mid], L[i], L[j]):
                    ok = mid
                else:
                    ng = mid
            cnt += ok - j
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect


def main():
    N = int(input())
    L = list(map(int, input().split(' ')))
    L.sort()
    cnt = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            index = bisect.bisect_left(L, L[i] + L[j])
            cnt += max([0, index - j - 1])
    print(cnt)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np

n, k, q = map(int, input().split())
point = np.array([k]*n)
for i in range(q):
    A = np.array([1]*n)
    number = int(input())-1
    A[number] = 0
    point -= A

for i in range(n):
    if point[i] > 0:
        print('Yes')
    else:
        print("No")


### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
point = np.array([k]*n)
minus = np.array([-q]*n)
for i in range(q):
    A = int(input())
    minus[A-1] +=1
point = point + minus

for i in range(n):
    if point[i] > 0:
        print('Yes')
    else:
        print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-



S = list("Z"+str(input()))
idx = 1
l = len(S)

ans = 0
while(idx <= l-3):
  if S[idx]=="A" and S[idx+1]=="B" and S[idx+2] == "C":
    ans += 1
    S[idx],S[idx+1],S[idx+2] = ["B","C","A"]
    idx -= 1
  else:
    idx += 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-


S = str(input()).replace("BC","D")

ans,stk = 0,0
for c in S:
  if c == "A":
    stk += 1
  elif c == "D":
    ans += stk
  else:
    stk = 0
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())

m = [['X'] * (W+2)]
for i in range(H):
  row = [c for c in input()]
  row.insert(0, 'X')
  row.append('X')
  m.append(row)
m.append(['X'] * (W+2))

q = deque([deque([(i, j) for j in range(1, 1+W) for i in range(1, 1+H) if m[i][j] == '#'])])

cnt = 0
while(True):
  if not q:
    break
  tt = q.popleft()
  nn = deque([])
  for t in tt:
    # left, right, up, down
    for n in ((t[0]-1, t[1]), (t[0]+1, t[1]), (t[0], t[1]-1), (t[0], t[1]+1)):
      if m[n[0]][n[1]] == '.':
        nn.append(n)
        m[n[0]][n[1]] = '#'
  if nn:
    q.append(nn)
  cnt += 1

print(cnt-1)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

m = [['X'] * (W+2)]
for i in range(H):
  row = [c for c in input()]
  row.insert(0, 'X')
  row.append('X')
  m.append(row)
m.append(['X'] * (W+2))

q = deque([deque([(i, j) for j in range(1, 1+W) for i in range(1, 1+H) if m[i][j] == '#'])])

cnt = 0
while(True):
  if not q:
    break
  tt = q.popleft()
  nn = deque([])
  for t in tt:
    # left, right, up, down
    for n in ((t[0]-1, t[1]), (t[0]+1, t[1]), (t[0], t[1]-1), (t[0], t[1]+1)):
      if m[n[0]][n[1]] == '.':
        nn.append(n)
        m[n[0]][n[1]] = '#'
  if nn:
    q.append(nn)
  cnt += 1

print(cnt-1)
### BUGGY CODE ###

#TLE
n = int(input())
a = input().split()
dic = {}
ans = 0
for i in range(n):
    if not a[i] in dic:
        num = a.count(a[i]) - 1
        ans += num * (num+1)
        dic[a[i]] = num
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]]))

### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

A,B,K = map(int,input().split())

s = [i for i in range(A,B+1)]

l = []

if 2 * K >= len(s):
    for j in range(len(s)):
        print(s[j])

    exit()


for t in range(0,K):
    print(s[t])

# s.reverse()

for h in range(len(s) - K,len(s)):
    print(s[h])



### FIXED CODE ###

A,B,K = map(int,input().split())

#s = [i for i in range(A,B+1)]


if 2 * K >= B - A + 1:
    for j in range(A,B+1):
        print(j)

    exit()

#l = [s[i] for i in range(0,K)]
#k = [s[h] for h in range(len(s) - K, len(s))]

for a in range(A,A+K):
    print(a)
for b in range(B-K+1,B+1):
    print(b)

#for t in range(0,K):
#    print(s[t])

# s.reverse()

#for h in range(len(s) - K,len(s)):
#    print(s[h])
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W):                
        if(S[i][W-j-1]=="."):
            if(j == 0):
                right[i][W-j-1]=1
            else:
                right[i][W-j-1]=right[i][W-j]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H):
    for j in range(W):     
        if(S[H-i-1][j]=="."):
            if(i == 0):
                down[H-i-1][j]=1
            else:
                down[H-i-1][j]=down[H-i][j]+1
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,left[i][j]+right[i][j]+up[i][j]+down[i][j]-3)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for _ in range(H)]
left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            if(j == 0):
                left[i][j] = 1
            else:
                left[i][j]=left[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):                
        if(S[i][j]=="."):
            if(j == W-1):
                right[i][j]=1
            else:
                right[i][j]=right[i][j+1]+1
for i in range(H):
    for j in range(W):                   
        if(S[i][j]=="."):
            if(i == 0):
                up[i][j] = 1
            else:
                up[i][j]=up[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W):     
        if(S[i][j]=="."):
            if(i == H-1):
                down[i][j]=1
            else:
                down[i][j]=down[i+1][j]+1
ans = 0
X = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j] = left[i][j]+right[i][j]+up[i][j]+down[i][j]-3
    ans = max(ans,max(X[i]))
print(ans)
### BUGGY CODE ###

N = input()
ans = 0
N1 = N[::-1]
b = ""
l = 0
for i in range(len(N)):
  if int(N1[i])+l==5 and i<len(N)-1 and int(N1[i+1])>=5:
    b+="0"
    l=1
    continue
  if int(N1[i])+l>10-(int(N1[i])+l):
    if i==len(N)-1:
      b+="01"
      continue
    b+="0"
    l=1
  else:
    b+=str(int(N1[i])+l)
    l=0
#print(b[::-1])
b1 = int(b[::-1])
b2 = b1-int(N)
ans+=sum(list(map(int, str(b1))))
ans+=sum(list(map(int, str(b2))))
print(ans)

### FIXED CODE ###

N = input()
ans = 0
N1 = N[::-1]

l = 0
for i in range(len(N)):
  if int(N1[i])+l==5 and i<len(N)-1 and int(N1[i+1])>=5:
    ans +=5
    l=1
    continue
  if int(N1[i])+l>10-(int(N1[i])+l):
    if i==len(N)-1:
      ans+=10-(int(N1[i])+l)+1
      continue
    ans+=10-(int(N1[i])+l)
    l=1
  else:
    ans+=int(N1[i])+l
    l=0
#print(b[::-1])
print(ans)
### BUGGY CODE ###

import re
N,Q = map(int,input().split(' '))
S = input()

lr = []
for _ in range(Q):
    lr.append(list(map(int,input().split(' '))))

pattern = '(AC)'

for l,r in lr:
    match = re.findall(pattern, S[l-1:r])
    print(len(match))


### FIXED CODE ###

N,Q = map(int,input().split(' '))
S = input()

lr = []
for _ in range(Q):
    lr.append(list(map(int,input().split(' '))))

#index_list = []
index_list = [0] * N
start = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        index_list[i] = index_list[i-1] + 1
    else:
        index_list[i] = index_list[i-1]

for l,r in lr:
    print(index_list[r-1] - index_list[l-1])
### BUGGY CODE ###

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    alph = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

    pos = np.zeros((26, N), dtype=int)
    for i, c in enumerate(input().strip()):
        p = alph.index(c)
        pos[p][i] = 1

    cur = np.ones(N, dtype=int)
    for _ in range(Q):
        t, d = map(str, input().split())
        p = alph.index(t)
        m = pos[p]
        golem = cur * m

        if d == 'L':
            moved_golem = np.append(golem[1:], 0)
        else:
            moved_golem = np.insert(golem[:N-1], 0, 0)

        cur = cur + moved_golem - golem

    print(np.sum(cur))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(str, input().strip()))
    order = [tuple(map(str, input().split())) for _ in range(Q)]
    order = order[::-1]

    left, right = 0, N-1
    for a in order:
        t, d = a[0], a[1]

        if d == 'L':
            if S[left] == t:
                left += 1
                if left > N - 1:
                    return 0

            if right < N - 1 and S[right + 1] == t:
                right = min(N - 1, right + 1)

        else:
            if left > 0 and S[left - 1] == t:
                left = max(0, left - 1)

            if S[right] == t:
                right -= 1
                if right < 0:
                    return 0

    return right - left + 1


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
n = int(input())

edges=[[] for i in range(n+1)]
d=[-1 for i in range(n+1)]
for i in range(1,n):
	a, b=[int(i) for i in input().split()]
	edges[a].append([b,1])
	edges[b].append([a,1])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)

d[1]=0
kyori(1)

D = list(map(int, input().split()))
D.sort(reverse=True)

ans_lst = [0] * n
ans = sum(D[1:])

ans_lst[0] = D[0]
now_kyori = 1
idx = 1
m = 1
while m < n:
    for i in range(2, n+1):
        if d[i] == now_kyori:
            ans_lst[i-1] = D[idx]
            idx += 1
            m += 1
    now_kyori += 1


ans_lst = list(map(str, ans_lst))
mojiretu = ' '.join(ans_lst)
print(ans)
print(mojiretu)

### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(100000)
n = int(input())

edges=[[] for i in range(n+1)]
d=[-1 for i in range(n+1)]
for i in range(1,n):
	a, b=[int(i) for i in input().split()]
	edges[a].append([b,1])
	edges[b].append([a,1])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)

d[1]=0
kyori(1)

D = list(map(int, input().split()))
D.sort(reverse=True)

ans_lst = [0] * n
ans = sum(D[1:])

ans_lst[0] = D[0]
now_kyori = 1
idx = 1
m = 1
idx_lst = [i for i in range(n)]

d.pop(0)

lst = np.array([d, idx_lst]).T.tolist()
lst.sort()
d = np.array(lst).T.tolist()[0]
idx_lst = np.array(lst).T.tolist()[1]

for i in range(n):
    ans_lst[idx_lst[i]] = D[i]

ans_lst = list(map(str, ans_lst))
mojiretu = ' '.join(ans_lst)
print(ans)
print(mojiretu)
### BUGGY CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
N=int(input())
P=list(map(int,input().split()))
for i in range(N):
    P[i]-=1
A=[30000*i for i in range(1,N+1)]
B=list(reversed(A))


lst=set(P[1:])
for i in range(1,N):
    for m in range(N):
        if not m in lst:
            B[m]-=1
    lst.remove(P[i])

print(" ".join([str(i) for i in A]))
print(" ".join([str(i) for i in B]))


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
N=int(input())
P=list(map(int,input().split()))
for i in range(N):
    P[i]-=1
A=[30000*i for i in range(1,N+1)]
B=list(reversed(A))
ruiA=[]
ruiB=[]


#lst=set(P[1:])
count=1
for i in range(0,N)[::-1]:
    B[P[i]]-=count
    """for m in lst:
        B[m]-=1
    lst.add(P[i])"""
    count+=1

print(" ".join([str(i) for i in A]))
print(" ".join([str(i) for i in B]))