루미 알고리즘

#1537다이아Plants

PO 2022 훈련 캠프코딩출제 Abdullah Zaghmout, Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Along a road that is N meters long, there are N plants. Plant i is of species A_i and is exactly one meter away from plant A_{i-1}. A botanist wants to walk along the road to collect plants. Since he has spent all his time in his lab, he is not in good shape, and therefore he asks you Q questions of the form: if I want to collect all plants of the species between 0 and Q_i, what is the minimum number of plants I need to pass by? He can start and end anywhere and can pass by a plant without collecting it.

Input

The first line contains two integers N (1 ≤ N ≤ 2 · 10^5) and Q (1 ≤ Q ≤ 2 · 10^5).

The second line contains N integers, where the i-th integer A_i (0 ≤ A_i ≤ 10^9) is the species of plant i.

Then follow Q lines, each containing an integer Q_i (0 ≤ Q_i ≤ 10^9) representing the i-th question the botanist asks you.

Output

Print Q lines where the i-th line contains the answer to the i-th question. If it is impossible to collect plants between 0 and Q_i, print -1.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
15N, Q, A_i, Q_i ≤ 200
27N ≤ 200
39Q=1, Q_i=1
412All integers A_i are different.
516N ≤ 2000
618Q = 1
733No additional constraints.

예제

예제 1

입력
5 5
0 0 1 3 2
2
3
4
1
0
출력
4
4
-1
2
1

예제 2

입력
7 4
3 1 0 15 1 2 1
1
2
15
1000000000
출력
2
4
-1
-1

출처 표기

출처: Programmeringsolympiaden 2022년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.