P15103 [ICPC 2025 LAC] 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^\infty = [\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^\infty$ and $A^\infty$ 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^\infty$ and $A^\infty$ 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 \le N \le 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 \le P_i \le 10^6$ for $i = 1, 2, \dots, N$). The third line contains an integer $E$ ($1 \le E \le 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 \le X \le 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 \le Y, Z \le 10^6$, $Y \notin 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 \le A_i \le 10^6$ for $i = 1, 2, \dots, K$), indicating that the length of the longest common subarray between $P^\infty$ and $A^\infty$ 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^\infty$ and $A^\infty$, or the character “*” (asterisk) if the length of the longest common subarray is larger than $10^{18}$.