벽돌깨기

넥슨에서 새로 개발하고 있는 벽돌깨기 게임은 다음과 같은 규칙으로 이루어져 있다.

• 직사각형 모양의 벽돌들이 $N$줄로 놓여져 있다. 한 줄에는 최소 $0$개, 최대 $10$억개의 벽돌이 쌓여 있을 수 있다.
• 입력으로 각 줄에 놓인 벽돌의 숫자들, 그리고 1부터 N까지의 정수가 각각 정확하게 한번씩 나온 순열 하나가 주어진다.
• 여러분의 임무는 각 줄에 놓인 벽돌의 수의 순서가 주어진 정수의 순열의 순서와 일치하게 벽돌을 깨서 부수는 것이다. 즉, 순열의 첫번째 수를 $P(1)$, 두번째 수를 $P(2)$, $\cdots$, $i$번째 수를 $P(i)$라고 한다면, $i$번째 줄에 놓인 벽돌의 수보다 벽돌이 적게 쌓인 줄은 정확하게 $P(i)-1$개 있어야 한다. 다르게 설명하면, 순열에서 주어진 순서대로 벽돌이 놓인 줄을 방문하고 이 줄에 놓인 벽돌의 수를 세면, 점점 커지는 오름차순이 되어야 한다.
• 입력에는 둘 이상의 줄에 같은 수의 벽돌이 주어질 수 있지만, 최종 결과에서는 각각의 줄에 다른 수의 벽돌이 놓여야 한다.
• 이를 위해서, 가장 적은 수의 벽돌을 부수어야 최고 점수를 받을 수 있다.

아래 그림의 예를 고려해보자. $N=5$줄로 벽돌들이 쌓여 있고, 입력받은 순열은 $(1, 3, 2, 5, 4)$라고 하자.

$1$번 줄에 있는 벽돌 $2$개를 깨고, $2$번 줄에 있는 벽돌 $2$개를 깬 결과는 다음과 같다. 이 결과가 조건을 만족하며, 많은 방법 중에서 가장 벽돌을 깨는 횟수가 적은 답이 된다.

반면, 같은 입력에 대해서 순열이 $(1, 2, 4, 5, 3)$으로 주어진다면 이 경우에 대해서는 답이 존재하지 않는데, 벽돌을 없애는 것만으로는 $3$번째 줄이 전체에서 $4$번째로 돌이 많게 할 수는 없기 때문이다.

벽돌의 줄 수, 각 줄에 쌓인 벽돌의 수, 입력 순열이 주어졌을 때 주어진 순열과 각 열에 쌓인 벽돌의 수의 순서가 일치하게 하도록 벽돌을 깨는 횟수의 최소값을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 벽돌의 줄 수를 나타내는 자연수 $N$ ($1$ 이상 $200\,000$ 이하)이 주어진다.

다음 줄에는 $N$개의 자연수가 주어지는데, 각각 왼쪽부터 오른쪽으로 차례로 각 줄을 보았을 때 이 줄에 쌓여있는 벽돌 수를 나타낸다. 한 줄에 올 수 있는 벽돌의 수는 $0$ 이상 $1\,000\,000\,000$ 이하이다.

그 다음 줄에는 $1$부터 $N$ 사이의 숫자가 정확하게 한번씩 포함된 $N$개의 숫자로 이루어진 순열이 주어진다.

출력 형식

한 줄로 결과를 출력한다. 여기에는 주어진 조건을 만족하게 하도록 벽돌을 깨는 횟수의 최소값을 출력한다. 만약 벽돌을 깨는 것으로 조건을 만족할 수 없다면, -1을 출력한다. 아무 벽돌을 깨지 않더라도 조건을 만족한다면 $0$을 출력한다.

예제 1

5
3 5 2 6 4
1 3 2 5 4

4

예제 2

5
3 5 2 6 4
1 2 4 5 3

-1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설