레이팅 미적용어느 학교의 전자 출석부에는 서로 다른 학번 \(N\)개가 오름차순으로 저장되어 있었다. 그런데 시스템 오류로 명단이 어떤 위치에서 '회전'되어 버렸다. 즉, 원래 명단의 뒤쪽 일부가 통째로 앞으로 이동하여, 현재 명단은 오름차순 수열을 몇 칸 회전시킨 형태이다. 회전량은 \(0\)일 수도 있다(그대로인 경우).
선생님이 학번 \(Q\)개를 차례로 조회한다. 각 학번이 현재 명단의 몇 번째 칸에 있는지(앞에서부터 \(1\)번부터 센다) 출력하고, 명단에 없으면 \(-1\)을 출력하여라.
- \(1 \le N, Q \le 100\,000\)
- \(1 \le\) 학번 \(\le 10^9\), 명단의 학번은 모두 서로 다르다
- 현재 명단은 어떤 오름차순 수열을 \(0\)칸 이상 회전시킨 것이다
첫째 줄에 명단의 크기 \(N\)과 조회 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 현재(회전된) 명단이 순서대로 주어진다. 모든 학번은 서로 다르다.
다음 \(Q\)개의 줄에 걸쳐 조회할 학번이 한 줄에 하나씩 주어진다.
각 조회에 대해 해당 학번의 위치(\(1\)부터), 없으면 \(-1\)을 한 줄에 하나씩 출력한다.
5 2
13 18 2 5 9
5
7
4
-1
학번 \(5\)는 명단의 \(4\)번째 칸에 있다. 학번 \(7\)은 명단에 없으므로 \(-1\)을 출력한다.
3 3
1 3 6
1
6
3
1
3
2
이 명단은 회전량이 \(0\), 즉 원래 순서 그대로이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original