시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 224 66 60 49.180%

문제

인셉션이란 한 사람의 꿈에 들어가 무의식에 특정 개념이나 생각을 주입하여 꿈에서 깨어난 후 그 개념이나 생각을 자기 스스로 가졌다고 믿게 만드는 일이다. 하지만 생각을 주입하려고 하는 표적이 꿈이 현실이라고 믿게 하기 매우 힘들기 때문에 불가능하다고 여겨져 왔다.

그러던 중 꿈 속의 표적의 정보를 추출하여 정보를 훔쳐왔던 PurpleNoon 팀은 꿈 속의 꿈을 통해 표적의 꿈과 현실의 경계를 모호하게 하여 인셉션이 가능하다고 생각하였다. 꿈속의 꿈은 매우 불안정 하기 때문에 약을 사용해야 한다. 그러나 약을 사용할 쉽사리 잠을 못 깨는 경우가 있기 때문에 킥을 사용하기로 하였다. 킥이란 꿈꾸는 사람을 넘어뜨려 낙하하는 감각으로 꿈을 깨우는 것이다. 이것은 꿈 속과 현실에서 모두 동일한 원리로 작용하여 잠든 사람을 깨어나게 할 수 있다. 

PurpleNoon 팀은 꿈 속의 꿈 혹은 꿈 속의 꿈 속의 꿈 등을 계획하고 있다. 즉, 상황에 따라서 더 깊은 꿈 속에 들어갈 수 있다. 그렇기 때문에 모든 꿈에서 각각 킥을 동시에 해야 하고 킥 타이밍을 맞추기 위해서 현실에서 음악으로 미리 신호를 주어, 음악이 끝나고 난 직후 킥을 하여 모든 꿈에서 한 번에 현실로 돌아오려고 한다. 하지만 몇 번의 꿈 속의 꿈에 들어왔는지 파악하기란 쉬운 일이 아니다. 그렇기 때문에 만일을 대비하여 현재 들리는 소리를 통해 가능한 최대 꿈의 깊이와 최소 꿈의 깊이를 계산하려고 한다.

몇 번의 꿈 속의 꿈에 들어갔는지는 음악의 빠르기로 예측 할 수 있는데 한 번 꿈속의 꿈에 들어갈 때 음과 음 사이의 차이가 정확히 1 만큼 증가하여 음악이 느리게 들린다. 예를 들어 현실에서 1 2 3의 음으로 음악이 들린다고 했을 때 한 번 꿈에 들어갈 경우 … 1 x 2 x 3 … 이 들리게 되며 한 번 더 꿈에 들어가게 되면 … 1 x x 2 x x 3 …이 들리게 된다. 이 때 x에는 어떤 음이 들리든 상관 없으며, 서로 다른 음일 수 있다. 현실에서 들리는 음이 주어지고, 현재 꿈에서 들리는 음이 주어졌을 때 몇 번의 꿈 속의 꿈으로 들어갔는지 확인하는 프로그램을 짜보자. 단, 꿈 속에서 들리는 소리에는 현실에서 들리는 음 이외의 음도 포함될 수 있다.

입력

첫 번째 줄에 현실에서 들리는 음의 갯수인 정수 n (2 ≤ n ≤ m)이 입력으로 주어진다. 그 다음 두 번째 줄에 n개의 음이 정수로 주어진다. 세 번째 줄에 꿈에서 들리는 음의 개수 m (2 ≤ m ≤ 1,000)이 주어진다. 네 번째 줄에 꿈 속에서 들리는 m개의 음이 주어진다. 여기에는 현실에서 들리는 음도 포함 될 수 있으며, 각 음의 범위는 109보다 작거나 같은 자연수이다.

출력

몇 번의 꿈속에 꿈에 들어왔는지 출력한다. 가능한 경우 중 가장 얕은 꿈의 단계와 가장 깊은 꿈의 단계를 출력하라. 현실일 경우 0을 출력하면 된다. 만약 꿈의 몇 단계에 왔는지 전혀 파악이 불가능 할 경우 -1을 출력하라.

예제 입력

3
1 2 3
6
4 1 2 3 5 10

예제 출력

0 0

예제 입력 2

3
1 2 3
10 
1 4 3 2 2 1 3 1 2 3

예제 출력 2

0 2

예제 입력 3

3
1 2 3
4
5 4 2 3

예제 출력 3

-1

힌트