今天不是\(lan\)的生日，他想買一條蛋糕慶祝。

這條蛋糕可以切成 \(n\) 單位，編號\(1～n\)。每單位的蛋糕都有一種口味，以數字\(a_i\)表示。

\(lan\) 的預算只能購買\([l, r]\)的蛋糕，她想將這段蛋糕切塊分給朋友。為了讓朋友們滿意，她希望每位朋友分到的蛋糕中，至少要包含\(k\) 種不同的口味。(切點必須在兩單位間，不能將一單位切成兩半)

請回答 \(q\)筆詢問。每個詢問給一段範圍 \([l, r]\)，請回答\(lan\)最多可以把這段蛋糕分給幾個朋友

輸入說明

第一行有三個數字\(n, q, k\)
第二行有\(n\)個數字以空白隔開\(a_i\)
接下來有\(q\)行，每行有兩個數字，以空白隔開\(l, r\)

\(1\ \le\ n,q\ \le\ 10^6\)
\(1\ \le\ a_i\ \le\ n\)
\(1\ \le\ k\ \le\ 500\)

輸出說明

輸出\(q\)行，代表\(q\)筆詢問的答案

範例輸入1

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

範例輸出1

2
0
1

範例說明1

對於第一筆詢問\(lan\)買了\([1, 5]\)的蛋糕,在切在\(2, 3\)間可得到兩塊蛋糕\([1, 2]\) 以及 \([2, 2, 1]\)，滿足每段皆有兩種口味
對於第二筆詢問\(lan\)買了\([2, 4]\)的蛋糕,沒有任何切法可以得到有兩種口味的蛋糕
對於第一筆詢問\(lan\)買了\([3, 5]\)的蛋糕,不切可以得到一段有兩種口味的蛋糕

註:最佳切法不唯一

子題配分