On the Chariot training grounds, there is a line of numbered grass. You must manoeuvre a Chariot across several points on the line.
To train one's handling, if the Chariot is on number $c$, it can only jump to the next closest grass of the same number $c$.
You will be given $Q$ trials. In each trial, there will be a starting and an ending position. The Chariot must be controlled to travel from the start to the end, following the above rule. It is guaranteed that the corresponding grass of both positions has the same number. Your task is to determine the total number of points the Chariot will step on.

Input

The first line consists of the integer $N$, the number of points on the line of grass.
The second line consists of $N$ integers $a_i$, the number of point $i$ on the line.
The third line consists of the integer $Q$.
Then, $Q$ lines follow. Each line consists of two integers, $s_i$ and $e_i$. They represent the starting and ending positions of each trial.

Output

Output the total number of points the Chariot will step on as an integer.

Constraints

For all testcases: $1 \le N, Q \le 10^6$, $1 \le u_i, v_i, a_i \le N$
Subtask 1 (10%): $N, Q \le 1000$
Subtask 2 (90%): No other constraints