Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1148.

Problem Description

Student Xiao Yang wants to play a card game called “Connecting Bamboo Poles”.

The rules are as follows: each card has a value $v$. The given cards are placed one by one at the end of a queue of cards. If, before placing a card, there is already a card in the queue with the same value as this card, then Xiao Yang will remove from the queue all cards between these two cards (including the two cards themselves).

Xiao Yang now has a card sequence $A$ of length $n$, where the value of each card is $A_i$ ($1\le i\le n$). Xiao Yang has $q$ queries. In the $i$-th query ($1\le i\le q$), Xiao Yang gives $l_i,r_i$. Xiao Yang wants to know: if we play “Connecting Bamboo Poles” using all cards with indices in $[l_i,r_i]$ in increasing index order, how many cards remain in the queue at the end.

Input Format

One line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains a positive integer $n$, the length of the card sequence $A$.

The second line contains $n$ positive integers $A_1,A_2,\dots,A_n$, the values of the cards in $A$.

The third line contains a positive integer $q$, the number of queries.

The next $q$ lines each contain two positive integers $l_i,r_i$, describing a query.

Output Format

For each test case, output $q$ lines. The $i$-th line ($1\le i\le q$) outputs a non-negative integer, which is the answer to the $i$-th query.

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

1
1
0
2

Hint

Sample Explanation

For the first query, Xiao Yang places the cards in the order $1,2,2$. When placing the last card, the two cards with value $2$ are removed, so only one card with value $1$ remains in the queue.

For the second query, the queue changes as follows:

$\{\}\to\{1\}\to\{1,2\}\to\{1,2,2\}\to\{1\}\to\{1,3\}\to\{1,3,1\}\to\{\}\to\{3\}$. Therefore, in the end only one card with value $3$ remains in the queue.

Constraints

For all testdata, it is guaranteed that $1\le T\le 5$, $1\le n\le 1.5\times 10^4$, $1\le q\le 1.5\times 10^4$, and $1\le A_i\le 13$.

Translated by ChatGPT 5