DQUERY Java

import java.io.*;
import java.util.*;

class Pair<T, U, V>
{
	T f;
	U s;
	V i;
	public Pair(T Integer1, U Integer2, V i)
	{
		f=Integer1; s=Integer2;this.i=i;
	}
	T first()
	{
		return f;
	}
	U second()
	{
		return s;
	}
	V geti()
	{
		return i;
	}
}

class Main
{
	static int[] a, counter, ans;
	static long[][] dpS, dpN, dp;
	static int n, count;
	static int BLOCK;

	static void add(int index)
	{
		if(counter[a[index]] == 0)
			count++;
	}

	static void remove(int index)
	{
		if(counter[a[index]] == 1)
			count--;
	}

	public static void main(String[] args) throws Exception
	{
		Scanner sc= new Scanner(System.in);

			int n= sc.nextInt();
			Main.n =n;
			BLOCK=(int)Math.sqrt(n);
			a= new int[n+2];
			for(int i=1; i<=n; i++)
			{
				a[i]= sc.nextInt();
			}
			int q= sc.nextInt();
			ans= new int[q];

			List<Pair<Integer, Integer, Integer>> list= new ArrayList<Pair<Integer, Integer, Integer>>();
			for(int k=0; k<q; k++)
			{
				list.add(new Pair<Integer, Integer, Integer>(sc.nextInt(), sc.nextInt(),k));
			}

			list.sort(new Comparator<Pair<Integer, Integer, Integer>>() {
				@Override
				public int compare(Pair<Integer, Integer, Integer> o1, Pair<Integer, Integer, Integer> o2) {
					if (o1.first()/BLOCK > o2.first()/BLOCK)
					{
						return 1;
					}
					else if ((o1.first()/BLOCK) == (o2.first()/BLOCK))
					{
						if(o1.second() > o2.second())
							return 1;
						else
							return -1;
					}
					else
					{
						return -1;
					}
				}
			});

			counter= new int[3000000];
			int currentL=1, currentR=1;
			for(int m=0;m<q;m++)
			{
				while(currentL < list.get(m).first())
				{
					remove(currentL);
					counter[a[currentL]]--;
					currentL++;
				}
				while(currentL >= list.get(m).first())
				{
					add(currentL);
					counter[a[currentL]]++;
					currentL--;
				}
				while(currentR > list.get(m).second())
				{
					remove(currentR);
					counter[a[currentR]]--;
					currentR--;
				}
				while(currentR <= list.get(m).second())
				{
					add(currentR);
					counter[a[currentR]]++;
					currentR++;
				}

				 ans[list.get(m).geti()]= count;
			}

			for(int m=0;m<q;m++)
			{
				System.out.println(ans[m]);
			}
	}

}