레스토랑

면접 대비

시간 제한1초메모리 제한1024 MB

요약

세 사람의 선호 순위가 주어질 때, 다른 모든 식당보다 두 명 이상이 더 선호하는 식당의 번호를 구합니다. 그런 식당이 없으면 -1을 출력합니다.

난이도: 보통10점 중 4점
유형: 배열, 구현
정답자: 아직 제출이 없습니다

문제

토르, 로켓, 그루트가 쇼핑몰을 돌아다니며 저녁 먹을 식당을 고르고 있습니다. 토르는 스테이크 메뉴가 다양한 식당을, 로켓은 버거 가게를, 그루트는 피자 가게를 좋아합니다. 세 사람은 1번부터 $n$ 번까지 모든 식당을 각자의 선호 순서대로 나열했습니다.

어떤 식당에 가려고 할 때, 맞은편 카페를 로켓과 그루트가 둘 다 더 좋아한다면 곤란할 것입니다. 그런데 그 카페는 토르와 로켓에게 다른 가게보다 못할 수도 있습니다. 그래서 그들은 다른 어떤 식당에도 밀리지 않는 식당을 고르기로 했습니다.

좀 더 정확히 말하면, 다른 식당마다 그 식당보다 선호도가 낮은 사람이 두 명 이상 있어야 합니다. 이런 식당을 찾아 주거나, 그런 식당이 없다는 것을 알려 주세요.

입력

첫 줄에 식당의 수 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ). 둘째 줄에는 토르의 선호 순서대로 나열한 1부터 $n$ 까지의 숫자 순열이 주어진다. 앞에 있을수록 더 선호하는 식당이다. 셋째 줄에는 로켓의 선호 순서가, 넷째 줄에는 그루트의 선호 순서가 같은 형식으로 주어진다.

출력

가장 좋은 식당의 번호를 출력한다. 그런 식당이 없으면 $-1$ 을 출력한다.

예제2

예제 1
입력
```
3
1 2 3
2 3 1
3 1 2
```
예상 출력
```
-1
```
예제 2
입력
```
4
2 1 3 4
3 1 4 2
4 1 2 3
```
예상 출력
```
1
```