책장

20XX년, JOI 군이 사는 나라에서 IOI가 열리게 되었다. 이 소식을 들은 JOI 군은 친구들에게 알리려고 방을 뛰쳐나가려 했다. 그러나 너무 급했던 나머지 방의 책장에 부딪히고 말았고, 책은 책장에서 전부 떨어졌다. 어쨌든 급했던 JOI 군은 떨어진 책을 순서는 전혀 고려하지 않고 모두 책장에 넣고 집을 나섰다. 귀가한 뒤, JOI 군은 엉망으로 꽂힌 책을 원래 순서로 되돌리는 작업이 필요해졌다.

JOI 군의 방에 있는 책장은 너비가 N센티미터이고, 책장에는 너비 1센티미터인 책이 N권 꽂혀 있다. 책에는 1부터 N까지 번호가 붙어 있고, 원래는 책장에 왼쪽부터 1, ..., N의 순서로 책이 꽂혀 있었다. 또 책 i의 무게는 Ai그램이다.

JOI 군은 지쳐서 책을 한꺼번에 많이 들고 싶지 않았기 때문에, 다음과 같은 작업을 하여 책장을 정리하기로 했다.

• 책장에 있는 책을 하나 골라 꺼낸다.
• 다음으로, 책을 꺼내서 생긴 빈 자리에 인접한 책을 옮기는 것을 여러 번 한다.
• 다음으로, 꺼낸 책을 책장의 빈 자리에 되돌린다.

책을 책장에서 동시에 2권 이상 꺼낼 수는 없다.

예를 들어 책이 왼쪽부터 5, 3, 4, 1, 2의 순서로 꽂혀 있을 때, 책 1을 꺼내고 책 4와 책 3을 차례로 오른쪽으로 옮긴 뒤 책 1을 책장에 되돌리면 책장의 책을 왼쪽부터 5, 1, 3, 4, 2의 순서로 만들 수 있다. (아래 그림)

이 작업에서 JOI 군이 무게 w그램인 책을 책장에서 꺼낼 때 JOI 군은 정확히 w칼로리를 소비한다. 또한 JOI 군이 무게 w그램인 책을 책장에 되돌릴 때도 JOI 군은 정확히 w칼로리를 소비한다. 또 책장은 매끄러운 재질로 되어 있어서 JOI 군이 책장 안에서 책을 옮길 때에는 칼로리를 소비하지 않아도 된다.

JOI 군은 지쳐 있었기 때문에 되도록 칼로리를 소비하지 않도록 하면서 책장의 책을 원래 순서로 되돌리기로 했다.

책의 수와 각 책의 무게, 현재 책장에 꽂힌 책의 순서가 주어졌을 때, JOI 군이 책장의 책을 원래 순서로 바꾸기 위해 소비하는 칼로리 합계의 최솟값을 구하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N이 쓰여 있다.
• 이어지는 N개 줄에는 책의 무게 정보가 쓰여 있다. i + 1번째 줄 (1 ≤ i ≤ N)에는 책 i의 무게를 나타내는 정수 Ai가 쓰여 있다.
• 이어지는 N개 줄에는 현재 책장에 꽂힌 책의 순서 정보가 쓰여 있다. j + N + 1번째 줄 (1 ≤ j ≤ N)에는 현재 왼쪽에서 j번째에 있는 책의 번호를 나타내는 정수가 쓰여 있다.

표준 출력에 JOI 군이 소비하는 칼로리 합계의 최솟값을 나타내는 정수를 1줄로 출력하시오.

• 1 ≤ N ≤ 100 000, 책의 수
• 1 ≤ Ai ≤ 1 000 000 000, 책 i의 무게 (그램)

이 입력 예에서는 처음에 책이 왼쪽부터 3, 4, 2, 1의 순서로 꽂혀 있고, 책 1, 2, 3, 4의 무게는 각각 1, 6, 4, 3그램이다.

JOI 군은 먼저 다음 작업을 차례로 한다.

• 책 1을 꺼낸다.
• 책 2, 책 4, 책 3을 차례로 오른쪽으로 옮긴다.
• 책 1을 빈 자리에 되돌린다.

책장의 책은 왼쪽부터 1, 3, 4, 2의 순서가 된다. 책 1의 무게는 1그램이므로 JOI 군은 1 × 2 = 2칼로리를 소비한다.

다음으로 다음 작업을 차례로 한다.

• 책 2를 꺼낸다.
• 책 4, 책 3을 차례로 오른쪽으로 옮긴다.
• 책 2를 빈 자리에 되돌린다.

책장의 책은 왼쪽부터 1, 2, 3, 4의 순서가 된다. 책 2의 무게는 6그램이므로 JOI 군은 6 × 2 = 12칼로리를 소비한다.

따라서 JOI 군은 합계 14칼로리를 소비하여 책을 왼쪽부터 1, 2, 3, 4의 순서로 만들 수 있다. 또한 JOI 군이 소비하는 칼로리를 이보다 적게 하는 것은 불가능하다.