25386번 - 라즈베리 파이

한별이는 $3$년 만에 오프라인으로 개최되는 UCPC 본선을 맞아 특별한 이벤트를 계획했다. 바로 참가자들과 라즈베리 파이를 나눠 먹는 것이다! 한별이는 원기둥 모양의 파이를 모든 조각이 밑면이 부채꼴인 기둥 모양이 되도록 $M$등분하고, 각 조각 위에 라즈베리를 하나씩 놓았다. 그리고 각 조각에 시계 방향 순서대로 $1$번에서 $M$번까지 번호를 붙였다.

한별이는 대회에 총 $N$($N\leq M$)명의 참가자가 참가한다는 말을 듣고, 각 참가자에게 몇 번째 조각을 나눠줄지 미리 정해 두었다. 마침내 모든 참가자가 대회장에 도착하고 한별이가 계획대로 파이 조각을 나눠주려는 순간, 한 참가자가 파이 위에 올려진 한 라즈베리를 가리키며 “나에게 저 라즈베리를 주지 않는다면 문제를 $10$분 만에 다 풀어버리겠다!”라고 선언했다. 그러자 다른 참가자들도 하나둘씩 본인이 원하는 라즈베리를 말하기 시작했고, 결국 모든 참가자가 본인이 먹고 싶은 라즈베리를 하나씩 말하고 돌아갔다.

한별이는 참가자들의 요구를 들어주기 위해 파이에 장식된 라즈베리들의 위치를 조정하려 한다. 그러나 이 라즈베리는 환경 변화에 민감해서 다음과 같은 방법으로 옮기지 않으면 금방 상해 버리고 만다.

• 조각 하나를 선택하여, 그 조각에 있는 모든 라즈베리를 바로 다음 조각으로 옮긴다.

여기서 $1$번 조각의 바로 다음 조각은 $2$번 조각, $2$번 조각의 바로 다음 조각은 $3$번 조각, $\cdots$, $M-1$번 조각의 바로 다음 조각은 $M$번 조각, $M$번 조각의 바로 다음 조각은 $1$번 조각이다.

라즈베리는 상하면 다른 라즈베리에도 나쁜 영향을 주므로, 한별이는 어떤 라즈베리도 상하지 않도록 하면서 라즈베리를 최소한으로 옮겨서 모든 참가자의 요구를 들어주려고 한다. 대회가 $10$분 만에 끝나 버리는 참사를 막기 위해 한별이를 도와주자.

단, 참가자들은 자신이 원하는 라즈베리와 다른 라즈베리를 같이 먹게 되는 것은 신경 쓰지 않으며, 라즈베리를 옮길 때 라즈베리 여러 개가 있는 조각을 선택하더라도 이동 횟수는 한 번으로 친다.

첫 번째 줄에는 파이의 조각 수 $M$과 대회 참가자의 수 $N$이 공백으로 구분되어 주어진다. $(1\leq N\leq M\leq 300\, 000)$

두 번째 줄에는 $N$개의 정수 $a_1,\cdots ,a_N$이 공백으로 구분되어 주어진다. $(1\leq a_i\leq M)$ $a_i$는 $i$번째 참가자에게 배정한 파이 조각의 번호를 의미하며, 모든 $a_i$는 서로 다르다.

세 번째 줄에는 $N$개의 정수 $b_1,\cdots ,b_N$이 공백으로 구분되어 주어진다. $(1\leq b_i\leq M)$ $b_i$는 $i$번째 참가자가 원하는 라즈베리가 위치한 파이 조각의 번호를 의미한다.

라즈베리를 상하지 않게 하면서 모든 참가자의 요구를 들어줄 수 있으면 라즈베리의 이동 횟수의 최솟값을 출력한다. 그렇지 않은 경우 $-1$을 출력한다.