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.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.util.ArrayDeque;
import java.io.PrintWriter;
import java.util.Deque;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.util.Collection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD_JeffAndPeriod solver = new TaskD_JeffAndPeriod();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD_JeffAndPeriod {
    public static final int BUBEN = 300;
    public static final int MAXM = 100004;

    int[] a;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        a = Utils.readIntArray(in, n);
        int countQ = in.nextInt();
        deques = new Deque[MAXM];
        diffs = new HashMap[MAXM];
        for (int i = 0; i < MAXM; ++i) {
            deques[i] = new ArrayDeque<Integer>();
            diffs[i] = new HashMap<Integer, Integer>();
        }
        am = new int[MAXM];

        final int BUCKETS = (n + BUBEN - 1) / BUBEN + 2;
        List<Query>[] qs = new List[BUCKETS];
        for (int i = 0; i < BUCKETS; ++i) {
            qs[i] = new ArrayList<Query>();
        }
        for (int i = 0; i < countQ; ++i) {
            int l = in.nextInt()-1;
            int r = in.nextInt()-1;
            qs[l / BUBEN].add(new Query(l, r, i));
        }

        for (int i = 0; i < BUCKETS; ++i) {
            Collections.sort(qs[i]);
        }

        int[] result = new int[countQ];
        for (int i = 0; i < BUCKETS; ++i) {
            if (qs[i].isEmpty()) continue;
            int le = qs[i].get(0).left;
            int ri = qs[i].get(0).right;

            calcTrivial(le, ri);
            result[qs[i].get(0).id] = getAns();
            for (int j = 1; j < qs[i].size(); ++j) {
                int nLe = qs[i].get(j).left;
                int nRi = qs[i].get(j).right;
                int id = qs[i].get(j).id;

                while (ri < nRi) {
                    addRight(ri+1);
                    ++ri;
                }
                while (le > nLe) {
                    addLeft(le-1);
                    --le;
                }
                while (le < nLe) {
                    removeLeft(le);
                    ++le;
                }
                while (ri > nRi) {
                    removeRight(ri);
                    --ri;
                }
                result[id] = getAns();
            }
        }
        for (int i = 0; i < countQ; ++i) {
            out.println(result[i]);
        }
    }

    Deque<Integer>[] deques;
    int[] am;
    int amDiff = 0;
    int amProgs = 0;
    HashMap<Integer, Integer>[] diffs;

    void calcTrivial(int left, int right) {
        amDiff = 0;
        amProgs = 0;
        for (int i = 0; i < MAXM; ++i) {
            deques[i].clear();
            am[i] = 0;
            diffs[i].clear();
        }
        for (int i = left; i <= right; ++i) {
            addRight(i);
        }
    }

    void addRight(int id) {
        int el = a[id];
        if (am[el] == 0) {
            ++amDiff;
        }
        ++am[el];

        if (!deques[el].isEmpty()) {
            int last = deques[el].getLast();
            int wasSize = diffs[el].size();
            addToMap(diffs[el], id - last);
            int newSize = diffs[el].size();
            if (wasSize == 1 && newSize == 2) {
                --amProgs;
            }
        } else {
            ++amProgs;
        }
        deques[el].addLast(id);
    }

    void addLeft(int id) {
        int el = a[id];
        if (am[el] == 0) {
            ++amDiff;
        }
        ++am[el];

        if (!deques[el].isEmpty()) {
            int last = deques[el].getFirst();
            int wasSize = diffs[el].size();
            addToMap(diffs[el], last - id);
            int newSize = diffs[el].size();
            if (wasSize == 1 && newSize == 2) {
                --amProgs;
            }
        } else {
            ++amProgs;
        }
        deques[el].addFirst(id);
    }

    void removeLeft(int id) {
        int el = a[id];
        if (am[el] == 1) {
            --amDiff;
        }
        --am[el];

        if (deques[el].size() == 1) {
            deques[el].removeFirst();
            --amProgs;
        } else {
            int it = deques[el].removeFirst();
            int wasSize = diffs[el].size();
            removeFromMap(diffs[el], deques[el].getFirst() - it);
            int newSize = diffs[el].size();
            if (wasSize > 1 && newSize == 1) {
                ++amProgs;
            }
        }
    }

    void removeRight(int id) {
        int el = a[id];
        if (am[el] == 1) {
            --amDiff;
        }
        --am[el];

        if (deques[el].size() == 1) {
            deques[el].removeLast();
            --amProgs;
        } else {
            int it = deques[el].removeLast();
            int wasSize = diffs[el].size();
            removeFromMap(diffs[el], it - deques[el].getLast());
            int newSize = diffs[el].size();
            if (wasSize > 1 && newSize == 1) {
                ++amProgs;
            }
        }
    }

    public int getAns() {
        if (amProgs != 0) {
            return amDiff;
        } else {
            return amDiff + 1;
        }
    }

    class Query implements Comparable<Query> {
        int left, right;
        int id;

        public Query(int left, int right, int id) {
            this.left = left;
            this.right = right;
            this.id = id;
        }

        public int compareTo(Query o) {
            return right - o.right;
        }
    }

    void removeFromMap(HashMap<Integer, Integer> map, int el) {
        if (map.get(el) == 1) {
            map.remove(el);
        } else {
            map.put(el, map.get(el) - 1);
        }
    }

    void addToMap(HashMap<Integer, Integer> map, int el) {
        if (map.containsKey(el)) {
            map.put(el, map.get(el) + 1);
        } else {
            map.put(el, 1);
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Utils {
    public static int[] readIntArray(InputReader in, int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        return a;
    }

}

