package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

const INF int64 = 2000000000000000000

type Node struct {
	is_leaf bool
	a_val   int64
	M       int64
	T1      int64
}

var tree []Node

func isqrt(n int64) int64 {
	if n == 0 {
		return 0
	}
	x := int64(math.Sqrt(float64(n)))
	for (x+1)*(x+1) <= n {
		x++
	}
	for x*x > n {
		x--
	}
	return x
}

func req_leaf(a_val int64, v int64) int64 {
	if v > 2000000000 {
		return INF
	}
	ans := v*v - a_val
	if ans < 0 {
		return 0
	}
	if ans > INF {
		return INF
	}
	return ans
}

func req(node int, v int64) int64 {
	if v >= INF {
		return INF
	}
	if v <= tree[node].M {
		return 0
	}
	if v == tree[node].M+1 {
		return tree[node].T1
	}
	if tree[node].is_leaf {
		return req_leaf(tree[node].a_val, v)
	}

	mid := req(2*node+1, v)
	if mid >= INF {
		return INF
	}
	return req(2*node, mid)
}

func eval(node int, x int64) int64 {
	if x < tree[node].T1 {
		return tree[node].M
	}
	if tree[node].is_leaf {
		return isqrt(tree[node].a_val + x)
	}

	v := tree[node].M + 1
	for {
		if req(node, v+1) <= x {
			v++
		} else {
			break
		}
	}
	return v
}

func pull(node int) {
	L := 2 * node
	R := 2*node + 1

	tree[node].M = eval(R, tree[L].M)
	mid := req(R, tree[node].M+1)
	tree[node].T1 = req(L, mid)
	tree[node].is_leaf = false
}

func build(node, l, r int, a []int64) {
	if l == r {
		tree[node].is_leaf = true
		tree[node].a_val = a[l]
		tree[node].M = isqrt(a[l])
		tree[node].T1 = req_leaf(a[l], tree[node].M+1)
		return
	}
	mid := (l + r) / 2
	build(2*node, l, mid, a)
	build(2*node+1, mid+1, r, a)
	pull(node)
}

func update(node, l, r int, k int, x int64) {
	if l == r {
		tree[node].a_val = x
		tree[node].M = isqrt(x)
		tree[node].T1 = req_leaf(x, tree[node].M+1)
		return
	}
	mid := (l + r) / 2
	if k <= mid {
		update(2*node, l, mid, k, x)
	} else {
		update(2*node+1, mid+1, r, k, x)
	}
	pull(node)
}

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

	nextInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	nextInt64 := func() int64 {
		scanner.Scan()
		res, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		return res
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	q := nextInt()

	a := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		a[i] = nextInt64()
	}

	tree = make([]Node, 4*n+1)
	build(1, 1, n, a)

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

	for i := 0; i < q; i++ {
		k := nextInt()
		x := nextInt64()
		update(1, 1, n, k, x)
		fmt.Fprintln(out, tree[1].M)
	}
}