Unique Rock Types Insertion

You are given an array of N integers representing the types of rocks in an initial collection. You are also given Q queries. Each query contains two integers X and P, where X is the type of a new rock that is inserted at the P-th position (1-indexed) of the original collection. Your task is to determine the number of unique rock types in the collection after each insertion. Note that for each query, the insertion is performed on the initial collection, not on a cumulatively updated array.

Formally, if the initial array is \(A\), then for a query \((X, P)\), a new array \(B\) is formed as follows:

\( B = (A[0], A[1], \ldots, A[P-2], X, A[P-1], \ldots, A[N-1]) \)

The answer for the query is given by:

\( f(B) = |\{ x : x \text{ is in } B \}| \),

which represents the number of distinct rock types in \(B\).

inputFormat

The first line contains an integer N - the number of rocks in the initial collection.

The second line contains N space-separated integers representing the initial rock types.

The third line contains an integer Q - the number of queries.

Each of the next Q lines contains two integers X and P where X is the rock type to insert and P is the 1-indexed position at which to insert the rock.

outputFormat

For each query, output a single line containing the number of unique rock types after performing the insertion.

## sample

5
1 2 3 4 5
3
6 3
2 1
7 6

6
5
6

</p>