Card Queue Removal Game

Alice (named Xiao Yang in the original statement) wants to play a card game called "Card Queue Removal". In this game, each card has a number \(v\). The game is played by taking a given sequence of cards and placing them one by one at the end of a queue. When placing a card, if there is already a card in the queue with the same number, then all cards from that earlier card up to the new card (including both cards) are removed from the queue.

You are given a sequence of \(n\) cards \(A\) where the \(i\)th card has a number \(A_i\) for \(1 \le i \le n\). There are \(q\) queries. In the \(i\)th query, you are given two integers \(l_i\) and \(r_i\). You need to simulate the game using only the cards from indices \(l_i\) to \(r_i\) in the given order, and report the number of cards left in the queue at the end.

Note: When a card \(v\) is about to be placed, if there is any card with the value \(v\) already in the current queue, then the segment of cards from the occurrence of that card (choosing the one closest to the end) and the new card are both removed. Equivalently, you can simulate the process by using a stack: for each card, if it is not already in the stack, push it; otherwise, pop cards from the stack until the card with the same value is removed (and do not push the new card). This process yields a unique final queue.

Constraints (implicit): The values of \(n\) and \(q\) as well as the numbers on the cards are such that a simple simulation will run within the time limits.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

The second line contains \(n\) integers \(A_1, A_2, \dots, A_n\) representing the card values.

Each of the next \(q\) lines contains two integers \(l_i\) and \(r_i\) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of cards remaining in the queue after playing the game with the cards from index \(l_i\) to \(r_i\) in order.

sample

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

2
3
3