import sys
input = sys.stdin.readline
N = int(input())
M = []
D = [[-1 for j in range(N+1)] for i in range(N+1)]

M.append((0,0))

for i in range(N):
    x, y = map(int, input().split())
    M.append((x, y))
    
def execute(s, e):
    result = sys.maxsize
    if D[s][e] != -1:
        return D[s][e]
    if s==e:
        return 0
    if s+1==e:
        return M[s][0] * M[s][1] * M[e][1]
    for i in range(s, e):
        result = min(result, M[s][0]*M[i][1]*M[e][1] + execute(s, i) + execute(i+1, e))
    D[s][e] = result
    return D[s][e]

print(execute(1, N))

import sys
input = sys.stdin.readline
N = int(input())
W = []

for i in range(N):
    W.append([])
    W[i] = list(map(int, input().split()))

D = [[0 for j in range(1<<16)] for i in range(16)]

def tsp(c, v):
    if v == (1<<N) - 1:
        if W[c][0] == 0:
            return float('inf')
        else:
            return W[c][0]
    if D[c][v] != 0:
        return D[c][v]
    min_val = float('inf')
    for i in range(0, N):
        if (v& (1<<i)) ==0 and W[c][i] != 0:
            min_val = min(min_val, tsp(i, (v|(1<<i))) + W[c][i])
    D[c][v] = min_val
    return D[c][v]

print(tsp(0, 1))

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

index = 0
maxLength = 1
B = [0] * 1000001
D = [0] * 1000001
ans = [0] * 1000001
B[maxLength] = A[1]
D[1] = 1

def binarysearch(l, r, now):
    while l<r:
        mid = (l+r) // 2
        if B[mid] < now:
            l = mid + 1
        else:
            r = mid
    return l

for i in range(2, N+1):
    if B[maxLength] < A[i]:
        maxLength += 1
        B[maxLength] = A[i]
        D[i] = maxLength
    else:
        index = binarysearch(1, maxLength, A[i])
        B[index] = A[i]
        D[i] = index

print(maxLength)
index = maxLength
x = B[maxLength] + 1

for i in range(N, 0, -1):
    if D[i] == index:
        ans[index] = A[i]
        index -= 1

for i in range(1, maxLength+1):
    print(ans[i], end=' ')