#include<bits/stdc++.h>
#define N 200050
#define ls ch[x][0]
#define rs ch[x][1]
#define ll unsigned long long
using namespace std;
int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
ll ha[N], mi[N], S;
const ll B = 11117;
const ll mod = 100003;
void update(int x) {
    size[x] = size[ls] + size[rs] + 1;
    ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
}
int get(int x) {
    return ch[fa[x]][1] == x;
}
void rotate(int x) {
    int f = fa[x], gf = fa[f], k = get(x);
    if(!f) return ;
    if(gf) ch[gf][get(f)] = x; fa[x] = gf;
    ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
    ch[x][!k] = f, fa[f] = x;
    update(f), update(x);
}
inline void splay(int x) {
    int f = fa[x];
    while(f) {
        if(fa[f]) rotate(get(x) == get(f)? f : x);
        rotate(x);
        f = fa[x];
       // printf("%d %d\n", x, f);
    }
    root = x;
}
void insert(int &x, int id, int f) {
   // printf("%d %d %d   \n", x, id, f);
    if(!x) {x = id; fa[x] = f; update(x); splay(x); return ;}
    if(v[id] < v[x]) insert(ls, id, x);
    else insert(rs, id, x);
}
void clear(int x) {
    fa[x] = ls = rs = size[x] = 0;
}
void del(int x) {
    splay(x);
    if(!ls || !rs) {root = ls + rs; fa[root] = 0; clear(x); return ; }
    int now = ls;
    while(ch[now][1]) now = ch[now][1];
    splay(now);
    ch[now][1] = ch[x][1], fa[ch[x][1]] = now;
    clear(x); update(now);
}
void deb(int x) {
    if(!x) return ;
    deb(ls);
    printf(" %d %d %d   ", x, ls, rs);
    deb(rs);
}


struct HAT {
    int nxt, s;
    ll val;
} e[N << 1];
int p[N], eid;
void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}
void INS(ll x) {
    int u = x % mod;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        if(x == e[i].val) { ++ e[i].s; return ;}
    }
    e[eid].val = x, e[eid].s = 1, e[eid].nxt = p[u];
    p[u] = eid ++;
}
int QRY(ll x) {
    int u = x % mod;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        if(x == e[i].val)  return e[i].s;
    } return 0;
}
int main() {
    init();
    scanf("%d%d%d", &n ,&m, &q);
    mi[0] = 1;
    for(int i = 1; i <= n; i ++) mi[i] = mi[i - 1] * B;
    
    for(int i = 1; i <= n; i ++) scanf("%d", &v[i]);
    
    for(int i = 1; i <= m; i ++) insert(root, i, 0), S += mi[i - 1];
    for(int i = m; i <= n; i ++) {
        INS(ha[root] - S * (i - m));
      //  printf("\n **  %llu   ", ha[root]); deb(root); printf("\n");
        del(i - m + 1);
     //   printf("\n **  "); deb(root); printf("\n");
        insert(root, i + 1, 0);
    }
    root = 0;
    
    memset(ch, 0, sizeof ch), memset(fa, 0, sizeof fa);
    for(int i = 1; i <= m; i ++) scanf("%d", &v[i]), insert(root, i, 0);
    while(q --) {
        int x, y;
        scanf("%d%d", &x, &y);
        del(x);
        v[x] = y; insert(root, x, 0);
        printf("%d\n", QRY(ha[root]));
    }
    return 0;
}
/*#include<bits/stdc++.h>
#define N 200050
#define ls ch[x][0]
#define rs ch[x][1]
#define ll unsigned long long
using namespace std;
int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
ll ha[N], mi[N], S;
const ll B = 11117;
const ll mod = 100003;
void update(int x) {
    size[x] = size[ls] + size[rs] + 1;
    ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
}
int get(int x) {
    return ch[fa[x]][1] == x;
}
void rotate(int x) {
    int f = fa[x], gf = fa[f], k = get(x);
    if(!f) return ;
    if(gf) ch[gf][get(f)] = x; fa[x] = gf;
    ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
    ch[x][!k] = f, fa[f] = x;
    update(f), update(x);
}
inline void splay(int x) {
    int f = fa[x];
    while(f) {
        if(fa[f]) rotate(get(x) == get(f)? f : x);
        rotate(x);
        f = fa[x];
       // printf("%d %d\n", x, f);
    }
    root = x;
}
void insert(int &x, int id, int f) {
   // printf("%d %d %d   \n", x, id, f);
    if(!x) {x = id; fa[x] = f; update(x); splay(x); return ;}
    if(v[id] < v[x]) insert(ls, id, x);
    else insert(rs, id, x);
}
void clear(int x) {
    fa[x] = ls = rs = size[x] = 0;
}
void del(int x) {
    splay(x);
    return 0;
}
*/

answer.code: In function ‘void update(int)’:
answer.code:12:5: error: reference to ‘size’ is ambiguous
   12 |     size[x] = size[ls] + size[rs] + 1;
      |     ^~~~
In file included from /usr/include/c++/13/string:53,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:1:
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code:12:15: error: reference to ‘size’ is ambiguous
   12 |     size[x] = size[ls] + size[rs] + 1;
      |               ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code:12:26: error: reference to ‘size’ is ambiguous
   12 |     size[x] = size[ls] + size[rs] + 1;
      |                          ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code:13:25: error: reference to ‘size’ is ambiguous
   13 |     ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
      |                         ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code:13:48: error: reference to ‘size’ is ambiguous
   13 |     ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
      |                                                ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code: In function ‘void clear(int)’:
answer.code:43:23: error: reference to ‘size’ is ambiguous
   43 |     fa[x] = ls = rs = size[x] = 0;
      |                       ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
answer.code:7:5: note:                 ‘int size [200050]’
    7 | int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
      |     ^~~~
answer.code: In function ‘int main()’:
answer.code:87:10: warn...