Gahui's Sequence Mod Play (Large)
Time limit1sMemory limit256 MB
Maintain a stack under push and pop, and after each type 3 query report the shortest suffix whose remainders mod m cover every residue from 0 to m-1, printing -1 if impossible.
- Level
Hard9 of 10
- Topics
- Stack, Two pointers, Hash map, Implementation
- Solved
- No attempts yet
Problem
chogahui is playing a remainder game with the sequence arr. chogahui can perform the following operations on the sequence.
- Append num to the end of the sequence arr.
- Remove the element at the end of the sequence arr.
The question chogahui asks is the following.
- What is the minimum number of numbers we must select starting from the end of the sequence arr so that, when divided by mod, the remainders 0, ..., mod-1 each appear at least once?
Answer chogahui's questions.
Input
The first line gives the number of queries Q and the divisor mod, separated by a space. (1 ≤ Q ≤ 10^6, 1 ≤ mod ≤ 2×10^9)
Each of the next Q lines contains one of the following three kinds of queries, distinguished by the first integer (1, 2, or 3).
- 1 num : Append num to the end of the sequence arr. (1 ≤ num ≤ 2^31-1)
- 2 : Remove the element at the end of the sequence arr. If arr is empty, ignore this.
- 3 : Compute the value for the query chogahui asks.
Initially the sequence arr is empty.
Output
Print the value for chogahui's query every time a type 3 query appears. There is at least one type 3 query in the input. If no answer exists for a type 3 query, print -1.