Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on sequence a:

  * take three integers v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), such that av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk; 
  * remove elements av, av + t, ..., av + t·k from the sequence a, the remaining elements should be reindexed a1, a2, ..., an - k - 1. 
  * permute in some order the remaining elements of sequence a. 



A beauty of a sequence a is the minimum number of operations that is needed to delete all elements from sequence a.

Jeff's written down a sequence of m integers b1, b2, ..., bm. Now he wants to ask q questions. Each question can be described with two integers li, ri. The answer to the question is the beauty of sequence bli, bli + 1, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions.

Input

The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 105). 

The third line contains integer q (1 ≤ q ≤ 105) — the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ m) — the description of i-th question.

Output

In q lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.

Examples

Input

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


Output

2
1
1
2
2


Input

10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1


Output

2
3
3
1
3
2
2
3
2
1
import java.io.*;
import java.util.*;
import java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import java.util.Collections.*;

// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display
//<editor-fold defaultstate="collapsed" desc="Main">
public class Solution {

    private void run() {
//        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }

        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.sc = sc;
        s.out = out;
        s.solve();
        if (!oj) {
            err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
            err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
        }
        out.flush();
    }

    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }

    public static void exit() {
        err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
        out.flush();
        out.close();
        System.exit(0);
    }

    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }

    public static void main(String[] args) {
        new Solution().run();
    }

    static long timeBegin = System.currentTimeMillis();
    static FastScanner sc;
    static PrintWriter out;
    static PrintStream err = System.err;
}
//</editor-fold>

//<editor-fold defaultstate="collapsed" desc="FastScanner">
class FastScanner {

    BufferedReader br;
    StringTokenizer st;

    FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
        st = new StringTokenizer("");
    }

    String next() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException ex) {
                Solution.MLE();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}
//</editor-fold>

class Pair{
    int delta, cnt;

    public Pair(int delta) {
        this.delta = delta;
        cnt = 1;
    }
    
}

class Item{
    ArrayDeque<Pair> delta;
    ArrayDeque<Integer> arr;
    
    Item(){
        delta = new ArrayDeque<>(2);
        arr = new ArrayDeque<>(2);
    }
    
    boolean isEmpty(){
        return arr.isEmpty();
    }
    
    boolean isProg(){
        return delta.size() <= 1;
    }
    
    void clear() {
        delta.clear();
        arr.clear();
    }
    
    void addFirst( int val ){
        if( arr.isEmpty() ){
            arr.addFirst(val);
        }
        else if( arr.size() == 1 ){
            arr.addFirst(val);
            delta.addFirst(new Pair(arr.getLast() - arr.getFirst()));
        }
        else{
            int curDelta = arr.getFirst() - val;
            if( curDelta == delta.getFirst().delta )
                delta.getFirst().cnt++;
            else
                delta.addFirst(new Pair(curDelta));
            arr.addFirst(val);
        }
    }
    
    void addLast( int val ){
        if( arr.isEmpty() ){
            arr.addLast(val);
        }
        else if( arr.size() == 1 ){
            arr.addLast(val);
            delta.addFirst(new Pair(arr.getLast() - arr.getFirst()));
        }
        else{
            int curDelta = val - arr.getLast();
            if( curDelta == delta.getLast().delta )
                delta.getLast().cnt++;
            else
                delta.addLast(new Pair(curDelta));
            arr.addLast(val);
        }
    }
    
    void removeFirst(){
        if( 2 <= arr.size() ){
            --delta.getFirst().cnt;
            if( delta.getFirst().cnt == 0 )
                delta.removeFirst();
        }
        arr.removeFirst();
    }


}


class Quest{
    int id, l, r;

    public Quest(int id, int l, int r) {
        this.id = id;
        this.l = l;
        this.r = r;
    }
    
}

class MySet{
    final static int BUBEN = (int)1e5 + 5;
    int cntProg, size;
    private Item[] items;

    public MySet() {
        items = new Item[BUBEN];
        for( int i = 0; i < items.length; ++i )
            items[i] = new Item();
    }
    
    void clear(){
        cntProg = 0;
        size = 0;
        for( int i = 0; i < items.length; ++i )
            items[i].clear();
    }

    int size(){
        return size;
    }
    
    void addFirst( int val, int pos ){
        Item it = items[val];
        if( !it.isEmpty() ){
            it = items[val];
            boolean a = it.isProg();
            it.addFirst(pos);
            boolean b = it.isProg();
            if(  a && !b ) --cntProg;
            if( !a &&  b ) ++cntProg;
        }
        else{
            items[val].addFirst(pos);
            ++cntProg;
            ++size;
        }
    }
    
    void addLast( int val, int pos ){
        Item it = items[val];
        if( !it.isEmpty() ){
            boolean a = it.isProg();
            it.addLast(pos);
            boolean b = it.isProg();
            if(  a && !b ) --cntProg;
            if( !a &&  b ) ++cntProg;
        }
        else{
            items[val].addLast(pos);
            ++cntProg;
            ++size;
        }
    }
    
    void removeFirst( int val ){
        Item it = items[val];
        boolean a = it.isProg();
        it.removeFirst();
        boolean b = it.isProg();
        
        if( it.isEmpty() ){
            --cntProg;
            --size;
        }
        else{
            if( !a && b ) ++cntProg;
        }
    }

}

class Solver {

    FastScanner sc;
    PrintWriter out;
    static PrintStream err = System.err;

    int n, sqrtN;
    int[] arr;
    int cntQ;
    HashMap<Integer,ArrayList<Quest>> q;
    int[] ans;
    
    void solve() {
        //test();
        
        n = sc.nextInt();
        
        sqrtN = 1;
        while( sqrtN * sqrtN < n ) ++sqrtN;
        
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        cntQ = sc.nextInt();
        q = new HashMap<>();
        for (int i = 0; i < cntQ; i++) {
            Quest quest = new Quest(i, sc.nextInt()-1, sc.nextInt()-1);
            int b = quest.l / sqrtN;
            if( !q.containsKey(b) )
                q.put(b, new ArrayList<Quest>());
            q.get(b).add(quest);
        }

        ans = new int[cntQ];
        MySet mySet = new MySet();
        for (ArrayList<Quest> arrayQuest : q.values()) {
            Collections.sort(arrayQuest, new Comparator<Quest>() {
                @Override
                public int compare(Quest a, Quest b) {
                    return Integer.compare(a.r, b.r);
                }
            });
            mySet.clear();
            int prevL = -1, prevR = -1;
            for (Quest quest : arrayQuest) {
                if( prevL == -1 ){
                    for (int i = quest.l; i <= quest.r; i++)
                        mySet.addLast(arr[i], i);
                }
                else{
                    for( int i = prevR + 1; i <= quest.r; ++i ) mySet.addLast(arr[i],i);
                    for( int i = prevL ; i < quest.l; ++i ) mySet.removeFirst(arr[i]);
                    for( int i = prevL - 1; quest.l <= i; --i ) mySet.addFirst(arr[i],i);
                }
                
                int curAns = mySet.size() + 1;
                if( 1 <= mySet.cntProg ) --curAns;
                ans[quest.id] = curAns;
                
                //
                prevL = quest.l;
                prevR = quest.r;
            }
            //err.println("=================");
        }
        
        for( int v : ans ) out.println(v);
    }

    private void test() {
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < 1e5; i++) hm.put(i, i);
        for (int i = 0; i < 1e5 * 316; i++){
            Integer sdget = hm.get(i);
        }
        Solution.exit();
    }
}