34740번 - Infinite Arrays 다국어

문제

A subarray of an array $B$ is a contiguous sequence of elements taken from $B$. For example, if $B = [3, 1, 4, 1, 5],ドル then $[3, 1, 4],ドル $[4, 1],ドル the empty array $[ ]$ and the whole array $B$ are subarrays of $B$ (among others), while $[3, 4, 5]$ and $[1, 3]$ are not subarrays of $B$.

We also define $C^m$ as the array obtained by the concatenation of $m$ copies of the array $C$. For example, if $C = [3, 2]$ then $C^1 = [3, 2],ドル $C^2 = [3, 2, 3, 2]$ and $C^∞ = [ \dots , 3, 2, 3, 2, 3, 2, \dots]$.

In this problem you are given an array $P$ containing no repeated numbers, and you have to process a sequence of events that occur in order. The events can be of three types:

• Delete: a number present in $P$ must be deleted. For example, if $P = [2, 3, 4]$ and the number 3ドル$ has to be deleted, once the event is processed $P$ will become $[2, 4]$.
• Insert: a number not present in $P$ must be inserted into $P$ before some other number present in $P$. For example, if $P = [4, 3, 2, 1$] and the number 9ドル$ must be inserted before the number 1ドル,ドル once the event is processed $P$ will become $[4, 3, 2, 9, 1]$.
• Query: the length of the longest common subarray between $P^∞$ and $A^∞$ must be computed, where $A$ is an array given in the query. For example, if $P = [1, 2, 3, 4]$ and $A = [3, 2],ドル then the longest common subarray between $P^∞$ and $A^∞$ is $[2, 3],ドル so the answer to the query is 2ドル$.

Are you ready for this challenge?

입력

The first line contains an integer $N$ (1ドル ≤ N ≤ 5 \cdot 10^5 $) indicating the initial length of $P$.

The second line contains $N$ different integers $P_1, P_2, \dots , P_N$ (1ドル ≤ P_i ≤ 10^6$ for $i = 1, 2, \dots , N$).

The third line contains an integer $E$ (1ドル ≤ E ≤ 5 \cdot 10^5$) representing the number of events that need to be processed.

Each of the next $E$ lines describes an event, in the order they must be processed. The content of the line depends on the event, as follows:

• Delete: the line contains the character “-” (minus sign) and an integer $X$ (1ドル ≤ X ≤ 10^6,ドル and $X \in P$), denoting that $X$ must be deleted from $P$. It is guaranteed that after the removal $P$ does not become empty.
• Insert: the line contains the character “+” (plus sign) and two integers $Y$ and $Z$ (1ドル ≤ Y, Z ≤ 10^6,ドル $Y \not\in P,ドル and $Z \in P$), denoting that $Y$ must be inserted into $P$ immediately to the left of $Z$.
• Query: the line contains the character “?” (question mark), a positive integer $K,ドル and $K$ integers $A_1, A_2, \dots , A_K$ (1ドル ≤ A_i ≤ 10^6$ for $i = 1, 2, \dots , K$), indicating that the length of the longest common subarray between $P^∞$ and $A^∞$ must be computed. It is guaranteed that the input contains at least one query, and the sum of $K$ across all the queries is at most 10ドル^6$.

출력

Output a line for each query, with an integer indicating the length of the longest common subarray between $P^∞$ and $A^∞,ドル or the character “*” (asterisk) if the length of the longest common subarray is larger than 10ドル^{18}$.

제한

노트