The sequence of $m$ integers is called the permutation if it contains all integers from $1$ to $m$ exactly once. The number $m$ is called the length of the permutation.

Dreamoon has two permutations $p_1$ and $p_2$ of non-zero lengths $l_1$ and $l_2$.

Now Dreamoon concatenates these two permutations into another sequence $a$ of length $l_1 + l_2$. First $l_1$ elements of $a$ is the permutation $p_1$ and next $l_2$ elements of $a$ is the permutation $p_2$. 

You are given the sequence $a$, and you need to find two permutations $p_1$ and $p_2$. If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10\,000$) denoting the number of test cases in the input.

Each test case contains two lines. The first line contains one integer $n$ ($2 \leq n \leq 200\,000$): the length of $a$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n-1$).

The total sum of $n$ is less than $200\,000$.


-----Output-----

For each test case, the first line of output should contain one integer $k$: the number of ways to divide $a$ into permutations $p_1$ and $p_2$.

Each of the next $k$ lines should contain two integers $l_1$ and $l_2$ ($1 \leq l_1, l_2 \leq n, l_1 + l_2 = n$), denoting, that it is possible to divide $a$ into two permutations of length $l_1$ and $l_2$ ($p_1$ is the first $l_1$ elements of $a$, and $p_2$ is the last $l_2$ elements of $a$). You can print solutions in any order.


-----Example-----
Input
6
5
1 4 3 2 1
6
2 4 1 3 2 1
4
2 1 1 3
4
1 3 3 1
12
2 1 3 4 5 6 7 8 9 1 10 2
3
1 1 1

Output
2
1 4
4 1
1
4 2
0
0
1
2 10
0



-----Note-----

In the first example, two possible ways to divide $a$ into permutations are $\{1\} + \{4, 3, 2, 1\}$ and $\{1,4,3,2\} + \{1\}$.

In the second example, the only way to divide $a$ into permutations is $\{2,4,1,3\} + \{2,1\}$.

In the third example, there are no possible ways.

Difficulty: interview

Starter code:

Solutions:
def possible(a):
    ans = set()
    s = set()
    lmax = 0
    for i in range(len(a)):
        lmax = max(lmax, a[i])
        s.add(a[i])
        if lmax == i + 1 and len(s) == i + 1:
            ans.add(i + 1)
    return ans


t = int(input())
for case_num in range(t):
    n = int(input())
    a = list(map(int, input().split(' ')))
    left = possible(a)
    a.reverse()
    right = possible(a)
    ans = []
    for l in left:
        if n - l in right:
            ans.append(l)
    print(len(ans))
    for l in ans:
        print(l, n - l)


import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    aa=list(map(int,input().split()))
    ss=set()
    
    st=0
    ind=1
    pre=[0 for i in range(n)]
    for i in range(n):
        if aa[i] in ss:
            break
        ss.add(aa[i])
        while ind<=len(ss):
            if ind in ss:
                ind+=1
            else:
                break
        if len(ss)!=ind-1:
            pre[i]=0
        else:
            pre[i]=ind
    ind=1
   # print(pre)
    ss=set()
    suff=[0 for i in range(n)]
    for i in range(n-1,-1,-1):
        if aa[i] in ss:
            break
        ss.add(aa[i])
        while ind<=len(ss):
            if ind in ss:
                ind+=1
            else:
                break
        if len(ss)!=ind-1:
            suff[i]=0
        else:
            suff[i]=ind
    tot=0
    ans=[]
    for i in range(n-1):
        if pre[i]>0 and suff[i+1]>0:
            tot+=1
            ans.append([i+1,n-i-1])
    print(tot)
    for i in ans:
        print(i[0],i[1])
        



# @author 

import sys

class BDreamoonLikesPermutations:
    def solve(self):
        for _ in range(int(input())):
            
            def is_perm(a):
                return len(set(a)) == len(a) and min(a) == 1 and max(a) == len(a)
            
            n = int(input())
            a = [int(_) for _ in input().split()]
            done = set()
            ans = set()
            i = 0
            for i in range(n):
                if a[i] in done:
                    break
                done.add(a[i])
            
            if is_perm(a[:i]) and is_perm(a[i:]):
                ans.add((i, n - i))

            done = set()
            for i in range(n - 1, -1, -1):
                if a[i] in done:
                    break
                done.add(a[i])

            if is_perm(a[:i + 1]) and is_perm(a[i + 1:]):
                ans.add((i + 1, n - i - 1))

            print(len(ans))
            for sol in ans:
                print(*sol)

solver = BDreamoonLikesPermutations()
input = sys.stdin.readline

solver.solve()


def readIntArray():
    return list(map(int,input().split()))

t = int(input())
for _ in range(t):
    n = int(input())
    a = readIntArray()
    mp = {}
    for val in a:
        if val not in mp:
            mp[val] = 0
        mp[val] += 1
    l1 = max(a)
    l2 = n - l1
    if l2 <= 0:
        print(0)
        continue
    good = True
    for i in range(1, l2 + 1):
        if i not in mp or mp[i] != 2:
            good = False
            break
    for i in range(l2 + 1, l1 + 1):
        if i not in mp or mp[i] != 1:
            good = False
            break
    if not good:
        print(0)
        continue
    mp = {}
    ans = set()
    cur = 0
    st = set()
    used = set()
    for i in range(n):
        if a[i] in used:
            break
        st.add(a[i])
        used.add(a[i])
        while cur + 1 in st:
            st.remove(cur + 1)
            cur += 1
        if cur == l1 or cur == l2 and len(st) == 0:
            ans.add((cur, n - cur))
    print(len(ans))
    for val in ans:
        print(val[0], val[1])


t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    mx = max(a)
    sols = []
    if mx < n:
        l1 = list(sorted(a[:mx]))
        l2 = list(sorted(a[mx:]))
        rl1 = list(range(1, mx+1))
        rl2 = list(range(1, n-mx+1))
        if l1 == rl1 and l2 == rl2:
            sols.append((mx, n - mx))
        l1 = list(sorted(a[:n-mx]))
        l2 = list(sorted(a[n-mx:]))
        if mx*2 != n and l1 == rl2 and l2 == rl1:
            sols.append((n-mx, mx))
    print(len(sols))
    for p in sols:
        print(*p)


from collections import deque
t = int(input())
for _ in range(t):
    n = int(input())
    liste = list(map(int, input().split()))
    vis = [0 for i in range(n)]
    can = [0 for i in range(n)]
    can2 = [0 for i in range(n)]
    maxi = 0
    for i in range(1, n):
        if (vis[liste[i-1]]):
            break
        vis[liste[i-1]] = 1
        maxi = max(maxi, liste[i-1])
        if (maxi == i):
            can[maxi] = 1
    liste = liste[::-1]
    maxi = 0
    vis = [0 for i in range(n)]
    for i in range(1, n):
        if (vis[liste[i-1]]):
            break
        vis[liste[i-1]] = 1
        maxi = max(maxi, liste[i-1])
        if (maxi == i):
            can2[maxi] = 1
    count = 0
    for i in range(1, n):
        if (can[i] and can2[n-i]):
            count += 1
    print(count)
    for i in range(1, n):
        if (can[i] and can2[n-i]):
            print(i, n-i)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    dpF = [0 for i in range(n)]
    dpB = [0 for i in range(n)]
    noRep = 1
    r = {}
    m = 0
    for i in range(n):
        if r.get(a[i]) == None:
            r[a[i]] = 1
            m = max(m, a[i])
            if m == i + 1:
                dpF[i] = 1
        else:
            break
    r = {}
    m = 0
    for i in range(n - 1, -1, -1):
        if r.get(a[i]) == None:
            r[a[i]] = 1
            m = max(m, a[i])
            if m == n - i:
                dpB[i] = 1
        else:
            break
    # print(dpF)
    # print(dpB)
    ans = 0
    ansList = []
    for i in range(n - 1):
        if dpF[i] == 1 and dpB[i + 1] == 1:
            ans += 1
            ansList.append([i + 1, n - i - 1])
    print(ans)
    for i in ansList:
        print(i[0], i[1])

from math import *

mod = 1000000007

for zz in range(int(input())):
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = []
    cs = set()
    d = {}
    c = 0
    for i in range(n):
        if a[i] not in d:
            c += 1
            d[a[i]] = 0
        d[a[i]] += 1
    mv = 0
    m = [0] * n
    m[-1] = a[-1]
    for i in range(n - 2, -1, -1):
        m[i] = max(m[i + 1], a[i])

    for i in range(n):
        mv = max(a[i], mv)
        if a[i] in cs:
            break
        cs.add(a[i])
        d[a[i]] -= 1
        if d[a[i]] <= 0:
            c -= 1
        if mv == i + 1 and c == n - i - 1 and m[i + 1] == n - i - 1:
            ans.append(i)
    print(len(ans))
    for i in ans:
        print(i + 1, n - i - 1)


def per(X):
    S=set(X)
    if not len(X)==len(S):
        return False
    for i in range(1,len(X)+1):
        if i not in S: return False
    return True
for y in range(int(input())):
    n=int(input())
    L=list(map(int,input().split()))
    m=max(L)
    r=[]
    if n!=m:
        if per(L[:m]) and per(L[m:]):
            r.append((m,n-m))
        if per(L[-m:]) and per(L[:-m]):
            r.append((n-m,m))
    r=list(set(r))
    print(len(r))
    for a,b in r:
        print(a,b)

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    seen = [False] * (n+1)
    ans = set()
    for i, x in enumerate(a):
        if seen[x]:
            if sorted(a[:i]) == list(range(1, i+1)) and sorted(a[i:]) == list(range(1, n-i+1)):
                ans.add((i, n-i))
            break
        seen[x] = True
    seen = [False] * (n+1)
    for i, x in list(enumerate(a))[::-1]:
        if seen[x]:
            if sorted(a[:i+1]) == list(range(1, i+2)) and sorted(a[i+1:]) == list(range(1, n-i)):
                ans.add((i+1, n-i-1))
            break
        seen[x] = True
    print(len(ans))
    for l1, l2 in ans:
        print(l1, l2)



import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    d=dict()
    demand=1
    pre=[0]*n
    post=[0]*n
    for i in range(n):
        d[arr[i]]=1
        if(demand in d):
            while(demand in d):
                demand+=1
            pre[i]=demand-1
    d2=dict()
    #print(pre)
    demand=1
    for i in range(n-1,-1,-1):
        d2[arr[i]]=1
        if(demand in d2):
            while(demand in d2):
                demand+=1
            post[i]=demand-1
    #print(post)
    l=[]
    for i in range(1,n):
        if(post[i]+pre[i-1]==n):
            l+=[[pre[i-1],post[i]]]
    print(len(l))
    for i in l:
        print(*i)
    
            


import heapq, sys


def ps(l):
    n = len(l)
    nxt = 1
    heap = []
    ans = []
    for i in range(n):
        heapq.heappush(heap, l[i])
        while heap and heap[0] == nxt:
            nxt += 1
            heapq.heappop(heap)
        if not heap:
            ans.append(i)
    return ans


for q in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    d = [int(i) for i in sys.stdin.readline().split()]
    st = set(ps(d))
    # print(st)
    d.reverse()
    anss = []
    ap = ps(d)
    # print(ap)
    for a in ap:
        b = n-2-a
        if b in st:
            anss.append(str(b+1)+' '+ str(n - b - 1) + '\n')
    sys.stdout.write(str(len(anss)) + '\n')
    sys.stdout.write(''.join(anss))