#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pair<int, int>>;
using pl = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pl>;
using ld = long double;
#define all(v) (v).begin(), (v).end()
#define ar array
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
os << '{';
string sep;
for (const T &x : v)
os << sep << x, sep = ", ";
return os << '}';
}
void dbg_out()
{
cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
cerr << ' ' << H;
dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const int N = 1<<20;
int a[N], res=0, previous=0;
int mi[N], mx[N];
int leftmost[N], n, m, k;
vector<pair<int,pi>> mem;
void addleft(int idx){
mem.pb({0, {a[idx], mi[a[idx]]}});
mem.pb({1, {a[idx], mx[a[idx]]}});
mi[a[idx]] = idx;
if (mx[a[idx]]<0) mx[a[idx]] = idx;
res = max(res, mx[a[idx]]-mi[a[idx]]);
}
void addright(int idx){
mx[a[idx]] = idx;
if (mi[a[idx]]>n) mx[a[idx]] = idx;
res = max(res, mx[a[idx]]-mi[a[idx]]);
}
void snapshot(){
previous = res;
}
void rollback(){
while(sz(mem)){
pair<int,pi> p = mem.back();
if (p.fi==0){
mi[p.se.fi] = p.se.se;
}else{
mx[p.se.fi] = p.se.se;
}
mem.pop_back();
}
res = previous;
}
void init(){
for (int i=1;i<=m;++i) mi[i] = INF, mx[i] = -INF;
res = 0;
}
const int block=320; //Dont forget to set
struct Query {
int l, r, idx;
inline pair<int, int> toPair() const {
return make_pair(l / block, r);
}
};
inline bool operator<(const Query &a, const Query &b) {
return a.toPair() < b.toPair();
}
using vq = vector<Query>;
vi mo(vq queries) {
vi answers(queries.size());
sort(queries.begin(), queries.end());
/*
Light Queries
*/
for (Query q: queries){
if (q.r-q.l+1<=block){
int ans = 0;
for (int j=q.l;j<=q.r;++j){
leftmost[a[j]] = INF;
}
for (int j=q.l;j<=q.r;++j){
ans = max(ans, j-leftmost[a[j]]);
if(leftmost[a[j]]>=n) leftmost[a[j]] = j;
}
answers[q.idx] = ans;
}
}
/*
Heavy Queries
*/
int l, r;
int last_bucket = -1;
for (Query q : queries) {
if (q.r-q.l+1<=block) continue;
int bucket = q.l/block;
if (bucket!=last_bucket){
init();
l = (bucket+1)*block;
if (l>=n) l = n;
r = q.r;
for (int j=l;j<=r;++j){
addright(j);
}
}
last_bucket = bucket;
while(r<q.r){
addright(++r);
}
snapshot();
for (int j=l-1;j>=q.l;--j){
addleft(j);
}
answers[q.idx] = res;
rollback();
}
return answers;
}
void solve()
{
cin >> n >> m>>k;
for (int i=0;i<n;++i) cin >> a[i];
vq q(k);
for (int i=0;i<k;++i){
int l,r;
cin >> l >> r;
l--;r--;
q[i] = {l,r,i};
}
vi ans = mo(q);
for (int x:ans) cout << x <<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
}