package main

import (
	"bufio"
	"fmt"
	"os"
)

const INF = 1 << 30

type Node struct {
	min  int
	max  int
	ansL int
	ansR int
}

var tree []Node
var a []int

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func first_greater(node, l, r, X int) int {
	if tree[node].max <= X {
		return INF
	}
	if l == r {
		return l
	}
	mid := (l + r) / 2
	if tree[node*2].max > X {
		return first_greater(node*2, l, mid, X)
	}
	return first_greater(node*2+1, mid+1, r, X)
}

func last_smaller(node, l, r, X int) int {
	if tree[node].min >= X {
		return -INF
	}
	if l == r {
		return l
	}
	mid := (l + r) / 2
	if tree[node*2+1].min < X {
		return last_smaller(node*2+1, mid+1, r, X)
	}
	return last_smaller(node*2, l, mid, X)
}

func pull(node, l, r int) {
	lc := node * 2
	rc := node*2 + 1

	tree[node].min = min(tree[lc].min, tree[rc].min)
	tree[node].max = max(tree[lc].max, tree[rc].max)

	mid := (l + r) / 2

	v1 := tree[lc].ansL
	v3 := tree[rc].ansL
	v2 := first_greater(lc, l, mid, tree[rc].min)

	tree[node].ansL = min(v1, min(v2, v3))

	u1 := tree[lc].ansR
	u3 := tree[rc].ansR
	u2 := last_smaller(rc, mid+1, r, tree[lc].max)

	tree[node].ansR = max(u1, max(u2, u3))
}

func build(node, l, r int) {
	if l == r {
		tree[node] = Node{min: a[l], max: a[l], ansL: INF, ansR: -INF}
		return
	}
	mid := (l + r) / 2
	build(node*2, l, mid)
	build(node*2+1, mid+1, r)
	pull(node, l, r)
}

func update(node, l, r, pos, val int) {
	if l == r {
		tree[node] = Node{min: val, max: val, ansL: INF, ansR: -INF}
		return
	}
	mid := (l + r) / 2
	if pos <= mid {
		update(node*2, l, mid, pos, val)
	} else {
		update(node*2+1, mid+1, r, pos, val)
	}
	pull(node, l, r)
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	nextInt := func() int {
		scanner.Scan()
		b := scanner.Bytes()
		res := 0
		sign := 1
		for _, c := range b {
			if c == '-' {
				sign = -1
			} else {
				res = res*10 + int(c-'0')
			}
		}
		return res * sign
	}

	if !scanner.Scan() {
		return
	}
	b := scanner.Bytes()
	t := 0
	for _, c := range b {
		t = t*10 + int(c-'0')
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for tc := 0; tc < t; tc++ {
		n := nextInt()
		a = make([]int, n+1)
		for i := 1; i <= n; i++ {
			a[i] = nextInt()
		}
		tree = make([]Node, 4*n+1)
		if n > 0 {
			build(1, 1, n)
		}

		q := nextInt()

		if n > 0 {
			if tree[1].ansL == INF {
				fmt.Fprintln(out, "-1 -1")
			} else {
				fmt.Fprintln(out, tree[1].ansL, tree[1].ansR)
			}
		}

		for i := 0; i < q; i++ {
			pos := nextInt()
			val := nextInt()
			if n > 0 {
				update(1, 1, n, pos, val)
				if tree[1].ansL == INF {
					fmt.Fprintln(out, "-1 -1")
				} else {
					fmt.Fprintln(out, tree[1].ansL, tree[1].ansR)
				}
			}
		}
	}
}