题目描述

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}$.

4
1 2 3 4
10
? 2 3 2
? 3 99 99 99
- 1
- 4
? 2 3 3
? 3 4 1 4
+ 64 3
+ 1 2
? 4 1 2 64 3
? 4 1 3 64 2

2
0
1
0
*
1

1
217
1
? 1 314

0