가희의 수열놀이 (Small)
면접 대비시간 제한1초메모리 제한256 MB
수열에 뒤에서 원소를 넣고 빼는 연산을 처리하면서, 3번 질의마다 0부터 mod-1까지 모든 나머지가 적어도 한 번 나오는 가장 짧은 접미사의 길이를 출력한다. 불가능하면 -1을 출력한다.
문제
chogahui는 수열 arr을 이용해 나머지 놀이를 하고 있습니다. chogahui는 수열에 다음과 같은 연산을 할 수 있습니다.
- 수열 arr의 맨 뒤에 num을 추가한다.
- 수열 arr의 맨 뒤에 있는 원소를 제거한다.
chogahui가 물어보는 질문은 다음과 같습니다.
- 수열 arr의 맨 뒤에서부터 최소 몇 개의 수를 선택해야, 이들을 mod로 나누었을 때 나머지가 0, ..., mod-1인 경우가 최소 한 번 이상 나타나는가?
chogahui의 질문에 답하세요.
입력
첫 번째 줄에는 쿼리의 수 Q와 나누는 정수 mod가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 2×10^5, 1 ≤ mod ≤ 10^2)
이후 Q개의 줄에 걸쳐서 다음 세 종류의 쿼리 중 하나가 주어집니다. 이는 맨 앞에 오는 정수의 값 (1, 2, 3)에 따라 구분됩니다.
- 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 2^31-1)
- 2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 만약 arr이 비어 있으면 무시한다.
- 3 : chogahui가 요구하는 쿼리에 대한 값을 계산한다.
처음에 수열 arr은 비어 있습니다.
출력
chogahui가 요구한 쿼리에 대한 값을 3번 쿼리가 들어올 때마다 출력합니다. 3번 쿼리는 입력에 1개 이상 존재합니다. 3번 쿼리에 대한 답이 존재하지 않는 경우에는 -1을 출력합니다.
힌트
첫 번째 3번 쿼리가 들어왔을 때, 수열 arr은 다음과 같습니다.
3을 4로 나눈 나머지는 3, 2를 4로 나눈 나머지는 2입니다. 수열의 모든 원소를 선택해도 4로 나눈 나머지가 0인 경우, 1인 경우는 존재하지 않으므로 -1을 출력합니다.
2번째 3번 쿼리가 들어온 경우입니다. 위에서부터 4개를 선택했을 때, 4를 4로 나눈 나머지는 0, 1을 4로 나눈 나머지는 1, 3을 4로 나눈 나머지는 3, 2를 4로 나눈 나머지는 2입니다. 나머지가 0, 1, 2, 3인 경우가 최소 하나 이상 존재합니다. 그리고 이 값이 chogahui가 요구하는 값임을 알 수 있습니다. 따라서 4를 출력합니다.