아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

두 개의 케이크

시간 제한4초메모리 제한128 MB

요약
두 케이크를 주어진 두 순열 순서대로 층별로 쌓되, 층 종류마다 전담 제빵사 한 명씩을 쓰며 두 케이크를 병렬로 만들 때 걸리는 최소 시간을 구한다.
난이도

보통10점 중 6점

유형
그리디, 배열, 구현, 누적 합
정답자
아직 제출이 없습니다

문제

바이타자르의 제과점에 케이크를 한 개씩 만들어 달라는 급한 주문이 두 건 들어왔다. 잘 알려진 대로 케이크는 여러 겹의 층으로 이루어진다. 이 제과점은 nn가지 종류의 층을 만들 수 있으며, 만들어지는 케이크 한 개에는 각 종류의 층이 정확히 한 겹씩 들어간다. 주문서에는 층을 쌓아 올리는 순서가 지정되어 있다.

바이타자르는 제과사 nn명을 고용하고 있다. 1≤i≤n1 \le i \le n인 각 ii에 대해, ii번 제과사는 ii번 종류의 층을 만들 수 있다. 제과사 한 명이 층 하나를 만드는 데는 11분이 걸리며, 그 11분 동안에는 케이크 한 개에만 매달릴 수 있다. 하나의 케이크에서는 층을 하나씩 차례대로 쌓아야 한다(바로 아래 층이 완성된 뒤에야 다음 층을 시작할 수 있다). 두 케이크에 대한 작업은 동시에 진행할 수 있다.

주문받은 두 케이크를 모두 완성하는 데 필요한 최소 시간(분)을 구하여라.

입력

첫째 줄에 정수 nn이 주어진다(1≤n≤1061 \le n \le 10^6).

둘째 줄과 셋째 줄에는 각각 첫 번째 주문과 두 번째 주문이 주어진다. 각 줄은 11부터 nn까지의 서로 다른 정수 nn개로 이루어진 수열이며, 해당 케이크의 맨 위 층부터 시작하여 층들의 종류를 차례대로 나열한 것이다.

출력

주문받은 두 케이크를 모두 만드는 데 필요한 최소 시간(분)을 정수 하나로 출력한다.

예제1

  1. 예제 1

    입력
    3
    1 2 3
    3 2 1
    
    예상 출력
    4