package main

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

const N = 600005

type Node struct {
	min_val int
	lazy    int
}

var tree [4 * N]Node
var count0 [4 * N]int
var T [N + 1]int

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

func build(node, l, r int) {
	if l == r {
		tree[node].min_val = -l
		tree[node].lazy = 0
		return
	}
	mid := l + (r-l)/2
	build(2*node, l, mid)
	build(2*node+1, mid+1, r)
	tree[node].min_val = min(tree[2*node].min_val, tree[2*node+1].min_val)
}

func push(node int) {
	if tree[node].lazy != 0 {
		tree[2*node].min_val += tree[node].lazy
		tree[2*node].lazy += tree[node].lazy
		tree[2*node+1].min_val += tree[node].lazy
		tree[2*node+1].lazy += tree[node].lazy
		tree[node].lazy = 0
	}
}

func add(node, l, r, ql, qr, val int) {
	if ql > r || qr < l {
		return
	}
	if ql <= l && r <= qr {
		tree[node].min_val += val
		tree[node].lazy += val
		return
	}
	push(node)
	mid := l + (r-l)/2
	add(2*node, l, mid, ql, qr, val)
	add(2*node+1, mid+1, r, ql, qr, val)
	tree[node].min_val = min(tree[2*node].min_val, tree[2*node+1].min_val)
}

func query_min(node, l, r, ql, qr int) int {
	if ql > r || qr < l {
		return 1e9
	}
	if ql <= l && r <= qr {
		return tree[node].min_val
	}
	push(node)
	mid := l + (r-l)/2
	return min(query_min(2*node, l, mid, ql, qr), query_min(2*node+1, mid+1, r, ql, qr))
}

func find_first_le(node, l, r, ql, qr, val int) int {
	if ql > r || qr < l {
		return N + 1
	}
	if tree[node].min_val > val {
		return N + 1
	}
	if l == r {
		return l
	}
	push(node)
	mid := l + (r-l)/2
	res := find_first_le(2*node, l, mid, ql, qr, val)
	if res != N+1 {
		return res
	}
	return find_first_le(2*node+1, mid+1, r, ql, qr, val)
}

func build_U(node, l, r int) {
	count0[node] = r - l + 1
	if l == r {
		return
	}
	mid := l + (r-l)/2
	build_U(2*node, l, mid)
	build_U(2*node+1, mid+1, r)
}

func update_U(node, l, r, idx, val int) {
	if l == r {
		if val == 1 {
			count0[node] = 0
		} else {
			count0[node] = 1
		}
		return
	}
	mid := l + (r-l)/2
	if idx <= mid {
		update_U(2*node, l, mid, idx, val)
	} else {
		update_U(2*node+1, mid+1, r, idx, val)
	}
	count0[node] = count0[2*node] + count0[2*node+1]
}

func find_prev0(node, l, r, x int) int {
	if l > x || count0[node] == 0 {
		return -1
	}
	if l == r {
		return l
	}
	mid := l + (r-l)/2
	res := find_prev0(2*node+1, mid+1, r, x)
	if res != -1 {
		return res
	}
	return find_prev0(2*node, l, mid, x)
}

func find_next0(node, l, r, x int) int {
	if r < x || count0[node] == 0 {
		return -1
	}
	if l == r {
		return l
	}
	mid := l + (r-l)/2
	res := find_next0(2*node, l, mid, x)
	if res != -1 {
		return res
	}
	return find_next0(2*node+1, mid+1, r, x)
}

type Pair struct{ l, r int }

var net_added map[Pair]bool
var net_removed map[Pair]bool

func add_interval(l, r int) {
	p := Pair{l, r}
	if net_removed[p] {
		delete(net_removed, p)
	} else {
		net_added[p] = true
	}
}

func rem_interval(l, r int) {
	p := Pair{l, r}
	if net_added[p] {
		delete(net_added, p)
	} else {
		net_removed[p] = true
	}
}

func add_to_U(z int) {
	u := find_prev0(1, 0, N, z-1)
	v := find_next0(1, 0, N, z+1)
	if u+1 <= z-1 {
		rem_interval(u+1, z)
	}
	if z+1 <= v-1 {
		rem_interval(z+1, v)
	}
	add_interval(u+1, v)
	update_U(1, 0, N, z, 1)
}

func remove_from_U(z int) {
	u := find_prev0(1, 0, N, z-1)
	v := find_next0(1, 0, N, z+1)
	rem_interval(u+1, v)
	if u+1 <= z-1 {
		add_interval(u+1, z)
	}
	if z+1 <= v-1 {
		add_interval(z+1, v)
	}
	update_U(1, 0, N, z, 0)
}

func find_zeros(node, l, r, ql, qr int, cur_min *int) {
	if ql > r || qr < l {
		return
	}
	if tree[node].min_val > *cur_min {
		return
	}
	if l == r {
		if tree[node].min_val <= *cur_min {
			*cur_min = tree[node].min_val
			remove_from_U(l)
		}
		return
	}
	push(node)
	mid := l + (r-l)/2
	find_zeros(2*node, l, mid, ql, qr, cur_min)
	find_zeros(2*node+1, mid+1, r, ql, qr, cur_min)
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)

	build(1, 0, N)
	build_U(1, 0, N)

	net_added = make(map[Pair]bool)
	net_removed = make(map[Pair]bool)

	for i := 0; i < n; i++ {
		var x int
		fmt.Fscan(reader, &x)

		if T[x] == 0 {
			T[x] = 1
			add(1, 0, N, x, N, 2)
			target := query_min(1, 0, N, 0, x-1)
			y := find_first_le(1, 0, N, x, N, target)
			if y == -1 {
				y = N + 1
			}
			for {
				z := find_next0(1, 0, N, x)
				if z == -1 || z >= y {
					break
				}
				add_to_U(z)
			}
		} else {
			T[x] = 0
			add(1, 0, N, x, N, -2)
			target := query_min(1, 0, N, 0, x-1) - 2
			y := find_first_le(1, 0, N, x, N, target)
			if y == -1 {
				y = N + 1
			}
			cur_min := query_min(1, 0, N, 0, x-1)
			find_zeros(1, 0, N, x, y-1, &cur_min)
		}

		fmt.Fprintln(writer, len(net_removed))
		for p := range net_removed {
			fmt.Fprintln(writer, p.l, p.r)
		}
		fmt.Fprintln(writer, len(net_added))
		for p := range net_added {
			fmt.Fprintln(writer, p.l, p.r)
		}

		net_added = make(map[Pair]bool)
		net_removed = make(map[Pair]bool)
	}
}