Recently Vasya decided to improve his pistol shooting skills. Today his coach offered him the following exercise. He placed $n$ cans in a row on a table. Cans are numbered from left to right from $1$ to $n$. Vasya has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.

Vasya knows that the durability of the $i$-th can is $a_i$. It means that if Vasya has already knocked $x$ cans down and is now about to start shooting the $i$-th one, he will need $(a_i \cdot x + 1)$ shots to knock it down. You can assume that if Vasya starts shooting the $i$-th can, he will be shooting it until he knocks it down.

Your task is to choose such an order of shooting so that the number of shots required to knock each of the $n$ given cans down exactly once is minimum possible.


-----Input-----

The first line of the input contains one integer $n$ $(2 \le n \le 1\,000)$ — the number of cans.

The second line of the input contains the sequence $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 1\,000)$, where $a_i$ is the durability of the $i$-th can.


-----Output-----

In the first line print the minimum number of shots required to knock each of the $n$ given cans down exactly once.

In the second line print the sequence consisting of $n$ distinct integers from $1$ to $n$ — the order of indices of cans that minimizes the number of shots required. If there are several answers, you can print any of them.


-----Examples-----
Input
3
20 10 20

Output
43
1 3 2 

Input
4
10 10 10 10

Output
64
2 1 4 3 

Input
6
5 4 5 4 4 5

Output
69
6 1 3 5 2 4 

Input
2
1 4

Output
3
2 1 



-----Note-----

In the first example Vasya can start shooting from the first can. He knocks it down with the first shot because he haven't knocked any other cans down before. After that he has to shoot the third can. To knock it down he shoots $20 \cdot 1 + 1 = 21$ times. After that only second can remains. To knock it down Vasya shoots $10 \cdot 2 + 1 = 21$ times. So the total number of shots is $1 + 21 + 21 = 43$.

In the second example the order of shooting does not matter because all cans have the same durability.

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
a = [int(x) for x in input().split()]
b = [(a[i], i + 1) for i in range(n)]
b.sort(reverse=True)
ans = 0
for i in range(n):
    ans += b[i][0] * i + 1
print(ans)
for i in b:
    print(i[1], end=' ')

n = int(input())
l = list(map(int, input().split()))
for i in range(n):
    l[i] = [l[i], i]
res = 0
l.sort()
l = l[::-1]
for i2 in range(n):
    res += i2 * l[i2][0] + 1
print(res)
for i3 in range(n):
    print(l[i3][1] + 1, end=' ')

'''input
6
5 4 5 4 4 5



'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from  heapq import heappush as hpush
from heapq import heappop as hpop
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

n  =ri(1)
a = ri()

b  = sorted(a,reverse=True)
c = [i+1 for i in range(n)]

c.sort(key = lambda x: a[x-1])

c = c[::-1]


ans=0
x=0

for i in range(n):
	ans += (b[i]*(x)+1)
	x+=1

print(ans)
print(*c)

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
ls = list(map(int, input().split()))
ls = [(i, ls[i-1]) for i in range(1, n+1)]
ls.sort(key=lambda x: x[1])
ls.reverse()
cnt = 0
for i in range(n):
    cnt+=i*ls[i][1]+1
print(cnt)
for i in range(n):
    print(ls[i][0], end=' ')
print()


from sys import stdin, stdout  



n = int(input())

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

for i in range(n):
    D[i] = [D[i], i]
D.sort(reverse=True)
ans = 0

for i, d in enumerate(D):
    ans += d[0]*i + 1
    
print(ans)

for d in D:
    print(d[1] + 1, end= ' ')


n = int(input())
l = list(map(int,input().split()))
ans = []
yo = 0
count = 0
for i in range(n):
    ans.append([l[i],i+1])



final = []
ans.sort(reverse=True)
for a,b in ans:
    count+=yo*a + 1
    final.append(b)
    yo+=1
print(count)
print(*final)



from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**6+1
MOD = 10**9+7
spf = [i for i in range(MAXN)]
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i

def mhd(a,b):
    return abs(a[0]-b[0])+abs(b[1]-a[1])

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def eld(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5

def lgcd(a):
    g = a[0]
    for i in range(1,len(a)):
        g = math.gcd(g,a[i])
    return g

def ms(a):
    msf = -MAX
    meh = 0
    st = en = be = 0
    for i in range(len(a)):
        meh+=a[i]
        if msf<meh:
            msf = meh
            st = be
            en = i
        if meh<0:
            meh = 0
            be = i+1
    return msf,st,en

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD



def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
n = int(input())
a = arrIN()
x = [[i,a[i]] for i in range(n)]
x.sort(key = lambda x:x[1],reverse=True)
ans = 0
temp = []
for i in range(n):
    ans+=x[i][1]*i+1
    temp.append(x[i][0]+1)
print(ans)
print(*temp)

import sys
input = sys.stdin.readline

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

B=[[a,i] for i,a in enumerate(A)]

B.sort(reverse=True)

ANS=0
ind=0

for b,i in B:
    ANS+=b*ind+1
    ind+=1

print(ANS)
print(*[B[i][1]+1 for i in range(n)])
    
    


n = int(input())
l = list( map( int, input().split() ) )
l = [ (v, i) for i, v in enumerate( l ) ]
l.sort()
l.reverse()
s, x = 0, 0
for v, i in l:
    s += v * x + 1
    x += 1

print( s )
for v, i in l:
    print( i + 1 )


n = int(input())
s = list(map(lambda x: (int(x[1]),x[0]),enumerate(input().split())))
s.sort(reverse=True)
ans = 0
for i in range(n):
    ans+=(s[i][0]*i+1)
print(ans)
print(*map(lambda x: x[1]+1,s))

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

li = sorted(zip(li, list(range(len(li)))))[::-1]
ans = 0

for i in range(n):
    ans += li[i][0] * i + 1
print(ans)
ans_li = []
for i in range(n):
    ans_li.append(li[i][1] + 1)
print(*ans_li)



#Starting 8 minutes late !
def fun(x):
    return x[0]
n=int(input())
a=list(map(int,input().strip().split()))
for i in range(n):
    a[i]=[a[i],i+1]
a.sort(key=fun,reverse=True)
op=0
op2=""
for i in range(n):
    op2+=str(a[i][1])+" "
    op+=a[i][0]*i+1
print(op)
print(op2)

from operator import itemgetter

N = int(input())
A = list(map(int, input().split()))

B = []
for i, a in enumerate(A):
    B.append((i, a))

B.sort(reverse=True, key = itemgetter(1))

score = 0
for n, (i, b) in enumerate(B):
    score += b*n+1

print(score)
for i, _ in B:
    print(i+1, end=' ')
print()

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append([a[i], i])
b.sort(key=lambda x: x[0], reverse=True)
cnt = 0
s = 0
res = []
for i in range(n):
    s += cnt * b[i][0] + 1
    cnt += 1
    res.append(str(b[i][1] + 1))
print(s)
print(' '.join(res))


from collections import defaultdict
n = int(input())
rec = defaultdict(list)
origi = list(map(int, input().split()))
for i in range(n):
    rec[origi[i]].append(i + 1)
a = sorted(origi, reverse=True)
l = 0
ans = []
# x = 0
for i in range(n):
    l += a[i] * i + 1
    # x += 1
    ans.append(rec[a[i]].pop())
print(l)
for i in ans:
    print(i, end=' ')
print('')

import collections, heapq, bisect, math

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

def solve(A):
    A = [(a,i) for i, a in enumerate(A)]
    A.sort(reverse=True)

    out = 0
    for i in range(len(A)):
        out += (i*A[i][0] + 1)
    
    print(out)
    print(' '.join(str(i+1) for _, i in A))





q = 1#input()
tests = []
for test in range(1):
    n = input()
    tests.append([int(p) for p in input().split(' ')])
for test in tests: solve(test)
#print(solve(n,b))


n = int(input())
A = list(map(int, input().split()))
for i in range(n):
  A[i] = [-A[i], i]
A.sort()
ans = 0
for i in range(n):
  ans += i * (-A[i][0]) + 1
print(ans)
for x in A:
  print(x[1] + 1, end=' ')

#!/usr/bin/env python3

n = int(input())
a = [int(i) for i in input().split()]
a = [(a[i], i) for i in range(len(a))]
a.sort(reverse=True)

s = 0
order = []
for i in range(len(a)):
    s += a[i][0] * i + 1
    order.append(a[i][1])
print(s)
print(' '.join([str(i + 1) for i in order]))


n = int(input())
l = list(map(int,input().split()))
l1 = [i for i in range(1,n + 1)]
for i in range(n):
    min1 = i
    for j in range(i + 1,n):
        if l[j] > l[min1]:
            min1 = j
    l[i],l[min1] = l[min1],l[i]
    l1[i],l1[min1] = l1[min1],l1[i]
count = 0
for i in range(n):
    count += l[i] * i + 1
print(count)
print(*l1)


n=int(input())
li=list(map(int,input().split()))
d={}
b=[]
for i in range(1,n+1):
    k=li[i-1]
    try:
        d[k].append(i)
    except KeyError:
        d[k]=[i]
        b.append(k)
b.sort(reverse=True)
ans1=[]
ans=0
l=0
for i in b:
    for j in d[i]:
        ans1.append(j)
        ans+=l*i+1
        l+=1
print(ans)
print(*ans1)
    


n = int(input())
a = [(int(el), i + 1) for i, el in enumerate(input().split())]
a = sorted(a, reverse=True)
shots = 0
for i, (el, _) in enumerate(a):
    shots += i * el + 1
print(shots)
print(*(i for _, i in a))


'''input
6
5 4 5 4 4 5
'''
from sys import stdin


def check_valid(string):
	stack = []
	for i in string:
		if i in ['(',  '[']:
			stack.append(i)
		elif i == ')':
			if len(stack) > 0:
				if stack[-1] == '(':
					stack.pop()
					continue
			return False
		elif i == ']':
			if len(stack) > 0:
				if stack[-1] == '[':
					stack.pop()
					continue
			return False

	return len(stack) == 0

def merge(index):
	aux = []
	if len(index) > 0:
		aux = [index[0]]
		for i in range(1, len(index)):
			if index[i][0] == aux[-1][1] + 1:
				aux[-1][1] = index[i][1]
			else:
				if check_valid(string[aux[-1][1] + 1: index[i][0]]):
					aux[-1][1] = index[i][1]
				else:
					aux.append(index[i])
	return aux


# main starts
n = int(stdin.readline().strip())
arr = []
arr = list(map(int, stdin.readline().split()))
for i in range(n):
	arr[i] = [i, arr[i]]

arr.sort(key = lambda x: x[1], reverse  = True)
count = 0 
ans = []
total = 0
for i in range(n):
	index, a = arr[i]
	ans.append(index + 1)
	total += count * a + 1

	count += 1

print(total)
print(*ans)


from collections import defaultdict as df
n=int(input())
d=df(list)
a=list(map(int,input().rstrip().split()))
for i in range(n):
    d[a[i]].append(i+1)
a.sort(reverse=True)
a=list(set(a))
a.sort(reverse=True)
sum1=0
ans=[]
counter=0
for i in range(len(a)):
    for j in d[a[i]]:
        sum1+=(a[i]*counter) + 1
        counter+=1
        ans.append(j)
print(sum1)
print(*ans)