굉장한 학생

시간 제한2초메모리 제한192 MB

요약
세 시험의 순위가 순열로 주어질 때, 세 시험 모두에서 순위가 앞서는 다른 학생이 없는 학생 수를 구합니다.
난이도

보통10점 중 6점

유형
정렬, 분할 정복, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

N명의 학생이 세 번의 시험을 보았다. 모든 학생은 세 시험에 모두 응시했고, 각 시험의 등수는 1등부터 N등까지 모두 서로 다르다.

학생 A가 학생 B보다 세 시험에서 모두 더 높은 등수라면, A는 B보다 '대단하다'고 한다. 어떤 학생 C보다 '대단한' 학생이 한 명도 없다면 C를 '굉장하다'고 한다.

세 시험의 등수 정보가 주어질 때, '굉장한' 학생이 몇 명인지 구하시오.

입력

첫째 줄에 학생 수 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 줄에는 각 시험에서 1등부터 N등까지의 학생 번호가 순서대로 주어진다. 학생 번호는 1부터 N까지이다.

출력

첫째 줄에 '굉장한' 학생의 수를 출력한다.

예제1

  1. 예제 1

    입력
    10
2 5 3 8 10 7 1 6 9 4
1 2 3 4 5 6 7 8 9 10
3 8 7 10 5 4 1 2 6 9
    예상 출력
    4