#include<iostream>
#include <forward_list>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include <climits>
#include <fstream>
#include <random>
#include<list>
#include<iomanip>
#include<numeric>
#include<map>
#include<bitset>
#include<unordered_map>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<functional>
#include<deque>
#include<utility>
#include <chrono>
using namespace std::chrono;
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
#define ordered_set tree<pi, null_type,less<pi>, rb_tree_tag,tree_order_statistics_node_update>
#define fo(i, a, b) for (ll i = a; i < b; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define no cout << "No" << "\n"
#define yes cout << "Yes" << "\n"
ll p = 1e9 + 7;
#define mod p
vector<ll> primes;
set<ll> primes_set;
vector<ll> fac;
vector<int> pf;
vector<ll> mob;
vector<ll> phi;
vector<bool> prime;
void sieve(int n)
{
    prime.resize(n + 1);
    for (int p = 0; p <= n; p++) {
        prime[p] = 1;
    }
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            primes.pb(p);
}
void sieve_set(int n)
{
    prime.resize(n + 1);
    for (int p = 0; p <= n; p++) {
        prime[p] = 1;
    }
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            primes_set.insert(p);
}


void sievepf(int n)
{
    for (int i = 0; i <= n; ++i) {
        pf.pb(0);
    }
    for (int i = 2; i <= n; ++i) {
        if (pf[i] == 0) {
            pf[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; i * primes[j] <= n; ++j) {
            pf[i * primes[j]] = primes[j];
            if (primes[j] == pf[i]) {
                break;
            }
        }
    }
}
void mobius(int n) {
    sievepf(n);
    for (int i = 0; i <= n; ++i) {
        mob.pb(0);
    }
    mob[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (pf[i] == i)mob[i] = -1;
        else {
            if ((i / pf[i]) % pf[i] == 0)mob[i] = 0;
            else mob[i] = mob[pf[i]] * mob[i / pf[i]];
        }
    }
}
ll gcd(ll a, ll b) {
    if (a == 0)return b;
    else return gcd(b % a, a);
}
inline long long mul(long long x, long long y)
{
    return ((x % mod) * 1ll * (y % mod)) % mod;
}
long long binpow(long long a, long long b)
{
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
ll gcd_dio(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd_dio(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
ll binpow2(ll a, ll b) {
    ll mod1 = mod - 1;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod1;
        a = (a * a) % mod1;
        b >>= 1;
    }
    return res;
}
long long inv(long long x)
{
    return binpow(x % mod, mod - 2);
}

long long divide(long long x, long long y)
{
    return mul(x, inv(y));
}
inline long long add(long long x, long long y)
{
    x %= mod;
    y %= mod;

    return (x + y) % mod;
}

inline long long sub(long long A, long long B)
{
    A = (A - B) % mod;
    return (A + mod) % mod;
}
void fact(long long c) {
    fac.pb(1);
    for (long long i = 1; i <= c; ++i) {
        fac.pb(mul(fac[i - 1], i));
    }
}
ll fib(ll n) {
    ll c[4] = { 1,1,1,0 };
    ll ans[4] = { 1,0,0,1 };
    ll base[4];
    base[0] = c[0];
    base[1] = c[1];
    base[2] = c[2];
    base[3] = c[3];
    ll base1[4];
    if (n == 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    n -= 2;
    while (n > 0) {
        if ((n & 1) == 1) {
            base1[0] = ans[0];
            base1[1] = ans[1];
            base1[2] = ans[2];
            base1[3] = ans[3];
            ans[0] = add(mul(base1[0], base[0]), mul(base1[1], base[2]));
            ans[1] = add(mul(base1[0], base[1]), mul(base1[1], base[3]));
            ans[2] = add(mul(base1[2], base[0]), mul(base1[3], base[2]));
            ans[3] = add(mul(base1[2], base[1]), mul(base1[3], base[3]));
        }
        base1[0] = base[0];
        base1[1] = base[1];
        base1[2] = base[2];
        base1[3] = base[3];
        base[0] = add(mul(base1[0], base1[0]), mul(base1[1], base1[2]));
        base[1] = add(mul(base1[0], base1[1]), mul(base1[1], base1[3]));
        base[2] = add(mul(base1[2], base1[0]), mul(base[3], base1[2]));
        base[3] = add(mul(base1[2], base1[1]), mul(base1[3], base1[3]));
        n >>= 1;
    }
    return add(ans[0], ans[1]);
}
ll inverse(ll a, ll m)
{
    ll x, y;
    ll g = gcd_dio(a, m, x, y);
    if (g != 1) {
        return -1;
    }
    else {
        x = (x % m + m) % m;
        return x;
    }
}
stack<pair<ll, ll>> s1, s2;
ll getmin() {
    ll minimum;
    if (s1.empty() || s2.empty())
        minimum = s1.empty() ? s2.top().second : s1.top().second;
    else
        minimum = min(s1.top().second, s2.top().second);
    return minimum;
}
void addele(ll new_element) {
    ll minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
    s1.push({ new_element, minimum });
}
void remove() {
    if (s2.empty()) {
        while (!s1.empty()) {
            ll element = s1.top().first;
            s1.pop();
            ll minimum = s2.empty() ? element : min(element, s2.top().second);
            s2.push({ element, minimum });
        }
    }
    s2.pop();
}
void clears() {
    while (!s1.empty())s1.pop();
    while (!s2.empty())s2.pop();
}
stack<pair<ll, ll>> s3, s4;
ll getmax() {
    ll maximum;
    if (s3.empty() || s4.empty())
        maximum = s3.empty() ? s4.top().second : s3.top().second;
    else
        maximum = max(s3.top().second, s4.top().second);
    return maximum;
}
void addele1(ll new_element) {
    ll maximum = s3.empty() ? new_element : max(new_element, s3.top().second);
    s3.push({ new_element, maximum });
}
void remove1() {
    if (s4.empty()) {
        while (!s3.empty()) {
            ll element = s3.top().first;
            s3.pop();
            ll maximum = s4.empty() ? element : max(element, s4.top().second);
            s4.push({ element, maximum });
        }
    }
    s4.pop();
}
void clears1() {
    while (!s3.empty())s3.pop();
    while (!s4.empty())s4.pop();
}
vl dsu(1);
vector<list<ll>> dsuset(1);
// first value in list contains size of list
void addset(ll x) {
    dsuset.pb(list<ll>({ 1,x }));
    dsu.pb(x);
}
int getset(int x) {
    if (dsu[x] == x)return x;
    else return getset(dsu[x]);
}
void joinset(int x, int y) {
    int a = getset(x);
    int b = getset(y);
    if (a != b) {
        if (*dsuset[a].begin() < *dsuset[b].begin()) {
            swap(x, y);
            swap(a, b);
        }
        // x has bigger size set
        dsu[b] = a;
        *dsuset[a].begin() += *dsuset[b].begin();
        dsuset[b].erase(dsuset[b].begin());
        dsuset[a].splice(dsuset[a].end(), dsuset[b]);
    }
}
vector<ll> dist;
vector<bool> vis;
// make sure that vis is clear before using it again and resize it
vector<vi> edges;
// resize edges
void bfs_dist(int n, int k) {
    dist.clear();
    dist.resize(n + 1);
    int a;
    queue<int> d;
    d.push(k);
    while (!d.empty()) {
        a = d.front();
        d.pop();
        vis[a] = 1;
        fo(i, 0, edges[a].size()) {
            if (vis[edges[a][i]] == 0) {
                d.push(edges[a][i]);
                dist[edges[a][i]] = dist[a] + 1;
            }
        }
    }
}

//requires dist amd edges to be cleared and resized, intial call is (Root,root,root,0)
void dfs_shortdis(int k, int a, int p, int dep) {
    dist[a] = dep;
    for (auto x : edges[a]) {
        if (x != p) {
            dfs_shortdis(k, x, a, dep + 1);
        }
    }
}
void bfs_shortdis(int n, int k) {
    //shortest distance for unweighted graphs from source node,complexity-O(V+E)
    dist.clear();
    dist.resize(n + 1, 1e9);
    int a;
    queue<int> d;
    d.push(k);
    vis[k] = 1;
    dist[k] = 0;
    while (!d.empty()) {
        a = d.front();
        d.pop();
        fo(i, 0, edges[a].size()) {
            if (vis[edges[a][i]] == 0) {
                vis[edges[a][i]] = 1;
                d.push(edges[a][i]);
            }
            if (dist[edges[a][i]] > dist[a] + 1) {
                dist[edges[a][i]] = dist[a] + 1;
            }
        }
    }
}

void dfs(int k) {
    // template for recursuve dfs functions
    vis[k] = 1;
    fo(i, 0, edges[k].size()) {
        if (vis[edges[k][i]] == 0) {
            dfs(edges[k][i]);
        }
    }
}
void dfs_graph(int n) {
    //template to apply dfs to more than 1 connected component graphs
    fo(i, 1, n + 1) {
        if (!vis[i]) {
            dfs(i);
        }
    }
}

vi child;
// clear and resize child before reuse
void dfs_child(int k) {
    //returns number of nodes below a node in a tree
    vis[k] = 1;
    child[k] = 1;
    fo(i, 0, edges[k].size()) {
        if (vis[edges[k][i]] == 0) {
            dfs_child(edges[k][i]);
            child[k] += child[edges[k][i]];
        }
    }
}

vector<vi> ancestor;
void dfs_k_ances(int k) {
    //forms array for kth ancestor and also gives depth array
    // also resize and clear dist and flatten and node_first before use
    // also build tree flatten array
    vis[k] = 1;
    if (!ancestor[k].empty()) {
        int i = 0;
        while (ancestor[ancestor[k][i]].size() >= (i + 1)) {
            ancestor[k].pb(ancestor[ancestor[k][i]][i]);
            i++;
        }
    }
    fo(i, 0, edges[k].size()) {
        if (vis[edges[k][i]] == 0) {
            ancestor[edges[k][i]].pb(k);
            dist[edges[k][i]] = dist[k] + 1;
            dfs_k_ances(edges[k][i]);
        }
    }
}
int get_kth_ances(int a, int k) {
    // call dfs_k_ances beforehand, returns -1 if no kth ancestor
    stack<int> d;
    int q = 0;
    while (k > 0) {
        if (k & 1) {
            d.push(q);
        }
        q++;
        k >>= 1;
    }
    q = a;
    while (!d.empty()) {
        if (ancestor[q].size() >= (d.top() + 1)) {
            q = ancestor[q][d.top()];
        }
        else {
            q = -1;
            break;
        }
        d.pop();
    }
    return q;
}
int lca(int a, int b) {
    // call dfs_k_ances beforehand
    if (dist[a] > dist[b])swap(a, b);
    b = get_kth_ances(b, dist[b] - dist[a]);
    if (a == b)return a;
    int k = -1, l = dist[a];
    while (l > 0) {
        l >>= 1;
        k++;
    }
    int at = -2, bt = -1;
    for (int i = k; i >= 0; --i) {
        if (ancestor[a].size() >= (i + 1))at = ancestor[a][i];
        if (ancestor[b].size() >= (i + 1))bt = ancestor[b][i];
        if (at != bt)a = at, b = bt;
    }
    return ancestor[a][0];
}

vi flatten;
vi node_first;// first occurance of node in flatten
vi node_last;
int timer = 0;

// needs only edges to be filled
void euler_dfs(int k) {
    // k is root
    vis[k] = 1;
    node_first[k] = timer++;
    flatten.pb(k);
    for (auto x : edges[k]) {
        if (!vis[x]) {
            euler_dfs(x);
            flatten.pb(k);
            timer++;
        }
    }
}
vector<vector<pi>> lef, rig;
void buildsparse(int n, int root) {
    // n is no of vertices
    vl f(22);
    f[0] = 1;
    fo(i, 1, 22)f[i] = f[i - 1] * 2;

    vis.clear();
    vis.resize(n + 1);
    dist.clear();
    dist.resize(n + 1);
    node_first.clear();
    node_first.resize(n + 1);
    timer = 0;

    euler_dfs(root);
    dfs_shortdis(root, root, root, 0);

    lef.clear();
    rig.clear();
    ll m = flatten.size();
    lef.resize(m, vector<pi>(ceil(log2(m)) + 1, mp(1e9, 0)));
    rig.resize(m, vector<pi>(ceil(log2(m)) + 1, mp(1e9, 0)));

    fo(i, 0, ceil(log2(m)) + 1) {
        if (i == 0) {
            fo(j, 0, m)lef[j][i] = mp(dist[flatten[j]], flatten[j]);
        }
        else {
            fo(j, 0, m)if (j + f[i - 1] < m)lef[j][i] = min(lef[j][i - 1], lef[j + f[i - 1]][i - 1]);
        }
    }
    fo(i, 0, ceil(log2(m)) + 1) {
        if (i == 0) {
            fo(j, 0, m)rig[j][i] = mp(dist[flatten[j]], flatten[j]);
        }
        else {
            for (ll j = m - 1; j >= 0; --j)if (j >= f[i - 1])rig[j][i] = min(rig[j][i - 1], rig[j - f[i - 1]][i - 1]);
        }
    }
}

int lcacon(ll a, ll b) {
    // make sure to call buildsparse before using this
    ll x = log2(abs(node_first[a] - node_first[b]) + 1);
    if (node_first[a] <= node_first[b]) {
        return min(lef[node_first[a]][x], rig[node_first[b]][x]).S;
    }
    else {
        return min(lef[node_first[b]][x], rig[node_first[a]][x]).S;
    }
}
vector<vector<pair<int, ll>>> edges_weight;
//clear and resize edges_weight before using dijkstra and if source is not connected to ith node then dist is 4*1e18
void dijkstra(int n, int k) {
    // result in dist
    dist.clear();
    dist.resize(n + 1, 4 * 1e18);
    vis.clear();
    vis.resize(n + 1);
    dist[k] = 0;
    priority_queue<pair<ll, int>> q;
    q.push(mp(0, k));
    int a;
    while (!q.empty()) {
        a = q.top().second;
        q.pop();
        if (vis[a] == 1)continue;
        vis[a] = 1;
        for (auto x : edges_weight[a]) {
            if (!vis[x.F]) {
                if (dist[x.first] > dist[a] + x.second && dist[a] != 4 * 1e18) {
                    dist[x.F] = dist[a] + x.second;
                    q.push(mp(-dist[x.F], x.first));
                }
            }
        }
    }
}
vector<vector<ll>> dist_all;
bool negative_cycle = 0;
// only need to resize edges_weight for this function,if no path from i to j then then dist_all[i][j] is 4*1e18
void floyd_warsh(int n) {
    // result in dist_alland also in bool of negative_cycle
    dist_all.clear();
    dist_all.resize(n + 1, vector<ll>((n + 1), 4 * 1e18));
    fo(i, 1, n + 1) {
        for (auto x : edges_weight[i]) {
            dist_all[i][x.first] = min(dist_all[i][x.first], x.second);
        }
    }
    fo(i, 1, n + 1)dist_all[i][i] = 0;
    fo(k, 1, n + 1) {
        fo(i, 1, n + 1) {
            fo(j, 1, n + 1) {
                dist_all[i][j] = min(dist_all[i][k] + dist_all[k][j], dist_all[i][j]);
            }
        }
    }
    // loop to detect negative cycle
    fo(i, 1, n + 1) {
        if (dist_all[i][i] < 0) {
            negative_cycle = 1;
        }
    }
}

// needs edges_weight to be clear and resized
void bellman_ford(int n, int k) {
    // result in dist and also in bool of negative_cycle
    dist.clear();
    dist.resize(n + 1, 4 * 1e18);
    bool v;
    dist[k] = 0;
    fo(i, 0, n - 1) {
        v = 0;
        fo(j, 1, n + 1) {
            for (auto x : edges_weight[j]) {
                if (dist[x.first] > dist[j] + x.S) {
                    dist[x.F] = dist[j] + x.second;
                    v = 1;
                }
            }
        }
        if (!v) {
            // no relaxation in a round
            break;
        }
    }
    // last loop to detect negative cycle
    fo(j, 1, n + 1) {
        for (auto x : edges_weight[j]) {
            if (dist[x.first] > dist[j] + x.S) {
                dist[x.F] = dist[j] + x.second;
                negative_cycle = 1;
            }
        }
    }
}
vi topo_sorted;
void topo_sort(int n) {
    // needs edges vector
    // stores result of topo sort in topo_sorted
    vi a(n + 1);
    queue<int> d;
    fo(i, 1, n + 1) {
        for (auto x : edges[i]) {
            a[x] += 1;
        }
    }
    fo(i, 1, n + 1) {
        if (a[i] == 0)d.push(i);
    }
    while (!d.empty()) {
        topo_sorted.pb(d.front());
        for (auto x : edges[d.front()]) {
            if (a[x] == 1)d.push(x);
            a[x] -= 1;
        }
        d.pop();
    }
}

// nothing to resize for this func not even edges_weight
vector<pair<pi, ll>> edges1;
vector<vector<pair<int, ll>>> edges_mintree;
void kruskal(int n, int m) {
    // n is no of vertices and m is no of edges
    // puts edges of min spanning tree in edges_mintree
    // returns -1 if no spanning tree i.e. graph has > 1 connected components
    edges_mintree.clear();
    edges_mintree.resize(n + 1);
    dsuset.clear();
    dsu.clear();
    dsuset.resize(1);
    dsu.resize(1);
    fo(i, 1, n + 1) {
        addset(i);
    }
    priority_queue<pair<ll, pi>> q;
    ll a, b, c;
    for (auto x : edges1) {
        a = x.F.first;
        b = x.first.second;
        c = x.second;
        q.push(mp(-c, mp(a, b)));
    }
    pair<ll, pi> x;
    while (!q.empty()) {
        x = q.top();
        x.first = -x.first;
        if (getset(x.second.F) != getset(x.second.S)) {
            joinset(x.second.first, x.second.S);
            edges_mintree[x.second.F].pb(mp(x.second.S, x.F));
        }
        q.pop();
    }
}
// needs edges creates scc of components in dsu
stack<int> finished;
vector<vi> edges_rev;
vector<int> comp;
int compno;
void dfs_scc(int k) {
    vis[k] = 1;
    for (auto x : edges[k]) {
        if (!vis[x])dfs_scc(x);
    }
    finished.push(k);
}
void dfs_scc2(int k, int j) {
    vis[k] = 1;
    comp[k] = j;
    for (auto x : edges_rev[k]) {
        if (!vis[x]) {
            joinset(x, k);
            dfs_scc2(x, j);
        }
    }
}
void kosaraju(int n) {
    vis.clear();
    vis.resize(n + 1);
    dsuset.clear();
    dsu.clear();
    dsuset.resize(1);
    dsu.resize(1);
    comp.clear();
    comp.resize(n + 1);
    fo(i, 1, n + 1) {
        addset(i);
    }
    int a;
    compno = 0;
    fo(i, 1, n + 1) {
        if (!vis[i]) {
            dfs_scc(i);
        }
    }
    vis.clear();
    vis.resize(n + 1);
    edges_rev.clear();
    edges_rev.resize(n + 1);
    fo(i, 1, n + 1) {
        for (auto x : edges[i]) {
            edges_rev[x].pb(i);
        }
    }
    while (!finished.empty()) {
        a = finished.top();
        finished.pop();
        if (!vis[a])dfs_scc2(a, compno++);
    }
}
bool solvable = 1;
vector<bool> solution;
void sat2_solve(int n) {
    // ith variable negation is (n+i)th variable
    fo(i, 1, n + 1) {
        if (comp[i] == comp[n + i]) {
            solvable = 0;
            break;
        }
    }
    solution.clear();
    solution.resize(n + 1);
    if (solvable) {
        fo(i, 1, n + 1) {
            if (comp[i] < comp[n + i]) {
                solution[i] = 0;
            }
            else {
                solution[i] = 1;
            }
        }
    }
}
//Normal segment tree for associative operations on a position(both works),(point update,range/point query)
// mass for associative and commutative operations on segment(add to prev i.e. order is not important),(range update,range/point query)
// lazy for associative operations on segment(assignment and matrix mul i.e. order is important),(range update,range/point query)
vector<ll> segtree;
// stores segtree
vector<ll> segarray;
// input array for segtree


long long operation(ll a, ll b) {
    return a + b;
}
void build(int v, int tl, int tr) {
    // resize segtree before use and  resize and take input in segarray
    // inital call is build(1,0,n-1)
    if (tl == tr) {
        segtree[v] = segarray[tl];
    }
    else {
        build(2 * v, tl, (tl + tr) / 2);
        build(2 * v + 1, (tl + tr) / 2 + 1, tr);
        segtree[v] = operation(segtree[2 * v], segtree[2 * v + 1]);
    }
}
ll query(int v, int tl, int tr, int l, int r) {
    // call it as (1,0,n-1,l,r)
    if (l > r) {
        // in case of min keep this as LLONG_MAX but 0 in case of sum and -LLONG_max in case of max
        return 0;
    }
    if (l == tl && r == tr) {
        return segtree[v];
    }
    int tm = (tl + tr) / 2;
    return operation(query(2 * v, tl, tm, l, min(r, tm)), query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
void update(int v, int tl, int tr, int pos, ll new_val) {
    // doesnt change segarray
    // call it as (1,0,n-1,pos,new_val)
    if (tl == tr) {
        segtree[v] = operation(segtree[v], new_val);
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2 * v, tl, tm, pos, new_val);
        }
        else {
            update(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        segtree[v] = operation(segtree[2 * v], segtree[2 * v + 1]);
    }
}
long long operation_m(ll a, ll b) {
    return a + b;
}
void update_m(int v, int tl, int tr, int l, int r, ll val) {
    // call it as (1,0,n-1,l,r,val)
    if (l <= r) {
        if (l == tl && r == tr) {
            segtree[v] = operation_m(segtree[v], val);
        }
        else {
            int tm = (tl + tr) / 2;
            update_m(2 * v, tl, tm, l, min(r, tm), val);
            update_m(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
        }
    }
}
ll query_m(int v, int tl, int tr, int pos) {
    // doesnt change segarray
    // call it as (1,0,n-1,pos)
    if (tl == tr) {
        return segtree[v];
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            return operation_m(segtree[v], query_m(2 * v, tl, tm, pos));
        }
        else {
            return operation_m(segtree[v], query_m(2 * v + 1, tm + 1, tr, pos));
        }
    }
}

vector<bool> marked;
void push(int v) {
    if (marked[v]) {
        segtree[2 * v] = segtree[v];
        segtree[2 * v + 1] = segtree[v];
        marked[2 * v] = 1;
        marked[2 * v + 1] = 1;
        marked[v] = 0;
    }
}
// size of marked is same as as segtree
void update_l(int v, int tl, int tr, int l, int r, ll val) {
    // call it as (1,0,n-1,l,r,val)
    if (l <= r) {
        if (l == tl && r == tr) {
            segtree[v] = val;
            marked[v] = 1;
        }
        else {
            push(v);
            int tm = (tl + tr) / 2;
            update_l(2 * v, tl, tm, l, min(r, tm), val);
            update_l(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
        }
    }
}
ll query_l(int v, int tl, int tr, int pos) {
    // doesnt change segarray
    // call it as (1,0,n-1,pos)
    if (tl == tr) {
        return segtree[v];
    }
    else {
        push(v);
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            return query_l(2 * v, tl, tm, pos);
        }
        else {
            return query_l(2 * v + 1, tm + 1, tr, pos);
        }
    }
}

// range update range queries 
vector<pair<ll, ll>> segt;
// F is min and S is added value
// operation_r is the operation you query for and operation_r1 is the operation you update for
long long operation_r(ll a, ll b) {
    return (a & b);
}
long long operation_r1(ll a, ll b) {
    return (a | b);
}
void build_r(int v, int tl, int tr) {
    // resize segtree before use and  resize and take input in segarray
    // inital call is build(1,0,n-1)
    if (tl == tr) {
        segt[v].F = segarray[tl];

    }
    else {
        build_r(2 * v, tl, (tl + tr) / 2);
        build_r(2 * v + 1, (tl + tr) / 2 + 1, tr);
        segt[v].F = operation_r(segt[2 * v].F, segt[2 * v + 1].F);
    }
}
void update_r(int v, int tl, int tr, int l, int r, ll val) {
    // call it as (1,0,n-1,l,r,val)
    if (l <= r) {
        if (l == tl && r == tr) {
            segt[v].S = operation_r1(segt[v].S, val);
            segt[v].F = operation_r1(segt[v].F, val);
        }
        else {
            int tm = (tl + tr) / 2;
            update_r(2 * v, tl, tm, l, min(r, tm), val);
            update_r(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
            segt[v].F = operation_r1(segt[v].S, operation_r(segt[2 * v].F, segt[2 * v + 1].F));
        }
    }
}
ll query_r(int v, int tl, int tr, int l, int r) {
    // doesnt change segarray
    // call it as (1,0,n-1,pos)
    if (l > r) {
        return LLONG_MAX;
        // dont forget to change this for different operations
    }
    else {
        if (l == tl && r == tr) {
            return segt[v].F;
        }
        else {
            int tm = (tl + tr) / 2;
            return operation_r1(segt[v].S, operation_r(query_r(2 * v, tl, tm, l, min(r, tm)), query_r(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)));
        }
    }
}
// range update range query but lazy
// operation_rl is the operation you query for
long long operation_rl(ll a, ll b) {
    return a + b;
}
void push_r(int v) {
    if (marked[v]) {
        segt[2 * v].S = segt[v].S;
        segt[2 * v + 1].S = segt[v].S;
        segt[2 * v].F = segt[v].S;
        segt[2 * v + 1].F = segt[v].S;
        marked[2 * v] = 1;
        marked[2 * v + 1] = 1;
        marked[v] = 0;
    }
}
void build_rl(int v, int tl, int tr) {
    // resize segt and marked before use and  resize and take input in segarray
    // inital call is build(1,0,n-1)
    if (tl == tr) {
        segt[v].F = segarray[tl];
    }
    else {
        build_rl(2 * v, tl, (tl + tr) / 2);
        build_rl(2 * v + 1, (tl + tr) / 2 + 1, tr);
        segt[v].F = operation_rl(segt[2 * v].F, segt[2 * v + 1].F);
    }
}
void update_rl(int v, int tl, int tr, int l, int r, ll val) {
    // call it as (1,0,n-1,l,r,val)
    if (l <= r) {
        if (l == tl && r == tr) {
            segt[v].S = val;
            segt[v].F = val;
            marked[v] = 1;
        }
        else {
            push_r(v);
            int tm = (tl + tr) / 2;
            update_rl(2 * v, tl, tm, l, min(r, tm), val);
            update_rl(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
            segt[v].F = operation_rl(segt[2 * v].F, segt[2 * v + 1].F);
        }
    }
}
ll query_rl(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        return 0;
        // dont forget to change this for different operations
    }
    else {
        if (l == tl && r == tr) {
            return segt[v].F;
        }
        else {
            push_r(v);
            int tm = (tl + tr) / 2;
            return operation_rl(query_rl(2 * v, tl, tm, l, min(r, tm)), query_rl(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        }
    }
}
// when using structs make sure to use a intializer, check for nulls, and pass the address to root in a function
const int MAX_ASCII = 2;
int len = 30;
struct vert {
    int count = 0;
    vert* childs[MAX_ASCII] = { nullptr };
};
vector<string> st;
void trie_build(vert* root) {
    // needs list of bit strings in st
    fo(i, 0, st.size()) {
        vert* start = root;
        fo(j, 0, st[i].size()) {
            if (start->childs[int(st[i][j]) - 48] == nullptr) {
                start->childs[int(st[i][j]) - 48] = new vert();
            }
            start = start->childs[int(st[i][j]) - 48];
            start->count += 1;
        }
    }

}
void add(string s, vert* root) {
    vert* start = root;
    fo(i, 0, s.size()) {
        if (start->childs[int(s[i]) - 48] == nullptr) {
            start->childs[int(s[i]) - 48] = new vert();
            start->childs[int(s[i]) - 48]->count = 0;
        }
        start = start->childs[int(s[i]) - 48];
        start->count += 1;
    }
}
void remove(string s, vert* root) {
    // assuming it already exists
    vert* start = root;
    fo(i, 0, s.size()) {

        vert* x = start->childs[int(s[i]) - 48];
        if (x->count == 1)start->childs[int(s[i]) - 48] = nullptr;
        swap(start, x);
        if (x->count == 0 && x != root)delete x;
        start->count -= 1;

    }
}
string query_string(string s, vert* root) {
    vert* start = root;
    string ans = "";
    fo(i, 0, s.size()) {
        if (start->childs[int(s[i]) - 48] == nullptr) {
            start = start->childs[1 - (int(s[i]) - 48)];
            ans += char(97 - int(s[i]));

        }
        else {
            start = start->childs[int(s[i]) - 48];
            ans += s[i];

        }

    }
    return ans;
}
queue<pi> d;
vector<vi> c;
void merge(int l, int r) {
    if (r > l) {
        int m = (r + l) / 2;
        fo(i, m + 1, r+1) {
            for (auto x : c[i]) {
                d.push(mp(2, x));
            }
        }
        fo(i, l+1, m+1) {
            d.push(mp(1, i));
        }
        merge(m+1,r);
        merge(l, m);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    clock_t tm = clock();
#endif
    /*#ifdef ONLINE_JUDGE
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vi b(n);
    c.resize(n + 1);
    fo(i, 0, n)cin >> b[i];
    fo(i, 0, n) {
        c[b[i]].pb(i + 1);
    }
    merge(0, n);
    cout << d.size() << "\n";
    while (!d.empty()) {
        cout << d.front().first << " " << d.front().second << "\n";
        d.pop();
    }
    return 0;
}