using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5 3");
WillReturn.Add("1 2 1 3 2");
WillReturn.Add("1 3");
WillReturn.Add("2 5");
WillReturn.Add("1 5");
//2
//3
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("10 5");
WillReturn.Add("3 1 4 1 5 9 2 6 5 3");
WillReturn.Add("1 5");
WillReturn.Add("3 7");
WillReturn.Add("1 10");
WillReturn.Add("5 5");
WillReturn.Add("2 8");
//4
//5
//7
//1
//6
}
else if (InputPattern == "Input3") {
WillReturn.Add("20 8");
WillReturn.Add("5 3 5 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 4");
WillReturn.Add("1 20");
WillReturn.Add("1 1");
WillReturn.Add("10 15");
WillReturn.Add("5 10");
WillReturn.Add("1 10");
WillReturn.Add("11 20");
WillReturn.Add("7 14");
WillReturn.Add("3 8");
//5
//1
//5
//5
//5
//5
//5
//5
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
class QueryInfoDef
{
internal long No;
internal long RangeSta;
internal long RangeEnd;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] CArr = GetSplitArr(InputList[1]);
long[] wkArr = { };
Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
// クエリ[Ind]なDict
var QueryListDict = new Dictionary<long, List<QueryInfoDef>>();
long CurrNo = 1;
foreach (string EachStr in InputList.Skip(2)) {
SplitAct(EachStr);
var WillAdd = new QueryInfoDef(); ;
WillAdd.No = CurrNo++;
WillAdd.RangeSta = wkArr[0] - 1;
WillAdd.RangeEnd = wkArr[1] - 1;
if (QueryListDict.ContainsKey(WillAdd.RangeSta) == false) {
QueryListDict[WillAdd.RangeSta] = new List<QueryInfoDef>();
}
QueryListDict[WillAdd.RangeSta].Add(WillAdd);
}
// Indのキュー[値]なDict
var QueueDict = new Dictionary<long, Queue<long>>();
for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
if (QueueDict.ContainsKey(CArr[I]) == false) {
QueueDict[CArr[I]] = new Queue<long>();
}
QueueDict[CArr[I]].Enqueue(I);
}
var Ins_Fenwick_Tree = new Fenwick_Tree(CArr.GetUpperBound(0));
foreach (var EachPair in QueueDict) {
long DequeuedVal = EachPair.Value.Dequeue();
Ins_Fenwick_Tree[DequeuedVal] = 1;
}
var AnswerDict = new Dictionary<long, long>();
for (long I = 0; I <= CArr.GetUpperBound(0); I++) {
if (QueryListDict.ContainsKey(I)) {
foreach (QueryInfoDef EachQueryInfo in QueryListDict[I]) {
long RangeSta = EachQueryInfo.RangeSta;
long RangeEnd = EachQueryInfo.RangeEnd;
long Answer = Ins_Fenwick_Tree.GetSum(RangeSta, RangeEnd);
AnswerDict[EachQueryInfo.No] = Answer;
}
}
long CurrVal = CArr[I];
if (QueueDict[CurrVal].Count > 0) {
long DequeuedVal = QueueDict[CurrVal].Dequeue();
Ins_Fenwick_Tree[DequeuedVal] = 1;
}
}
foreach (var EachPair in AnswerDict.OrderBy(pX => pX.Key)) {
Console.WriteLine(EachPair.Value);
}
}
}
// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
private long[] mBitArr;
private long mExternalArrUB;
// ノードのIndexの列挙を返す
internal IEnumerable<long> GetNodeIndEnum()
{
for (long I = 0; I <= mExternalArrUB; I++) {
yield return I;
}
}
// 木のノードのUBを返す
internal long GetUB()
{
return mExternalArrUB;
}
// コンストラクタ(外部配列のUBのみ指定)
internal Fenwick_Tree(long pExternalArrUB)
{
mExternalArrUB = pExternalArrUB;
// フェニック木の外部配列は0オリジンで、
// フェニック木の内部配列は1オリジンなため、2を足す
mBitArr = new long[pExternalArrUB + 2];
}
// コンストラクタ(初期化用の配列指定)
internal Fenwick_Tree(long[] pArr)
: this(pArr.GetUpperBound(0))
{
for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
this.Add(I, pArr[I]);
}
}
// コンストラクタ(初期化用のList指定)
internal Fenwick_Tree(List<long> pList)
: this(pList.Count - 1)
{
for (int I = 0; I <= pList.Count - 1; I++) {
this.Add(I, pList[I]);
}
}
// インデクサ
internal long this[long pInd]
{
get { return GetSum(pInd, pInd); }
set { Add(pInd, value - GetSum(pInd, pInd)); }
}
// [pSta,pEnd] のSumを返す
internal long GetSum(long pSta, long pEnd)
{
return GetSum(pEnd) - GetSum(pSta - 1);
}
// [0,pEnd] のSumを返す
internal long GetSum(long pEnd)
{
pEnd++; // 1オリジンに変更
long Sum = 0;
while (pEnd >= 1) {
Sum += mBitArr[pEnd];
pEnd -= pEnd & -pEnd;
}
return Sum;
}
// [I] に Xを加算
internal void Add(long pI, long pX)
{
pI++; // 1オリジンに変更
while (pI <= mBitArr.GetUpperBound(0)) {
mBitArr[pI] += pX;
pI += pI & -pI;
}
}
}
#endregion