1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cstdint>
#include <iostream>
#include <cstdio>
#include <vector>
#define PRINTN(ARG) printf("[ %i, %i]", ARG.key, ARG.value);
#define PRINT(ARG) std::cout << #ARG << " = " << ARG << '\n';

typedef int32_t int32;
typedef int64_t int64;
typedef int64_t int64;
const int32 MAX_N = 1000000;

int32 foo(int64, int32);
void printTree();

struct Node{ int32 key=0, value=0; };
std::vector<Node> map = std::vector<Node>(MAX_N);
std::vector<int32> stack = std::vector<int32>(MAX_N);
int32 stackIter = 0;
void push(int32 v){ stack[stackIter] = v; stackIter++; }
void pop(){ stackIter--; }

int32 n, dn, x;
int64 sum,epsi, thet, diff, del, delsum;
int main(){
//reading
    std::ios_base::sync_with_stdio(0);
    std::cin >> n;
    int32 buffer;
    for(int32 i=0; i<n; i++){
        std::cin >> buffer; 
        if(buffer != 1) sum += buffer;
        if(map[buffer].value == 0){
            map[buffer].key = buffer; dn++; }
        map[buffer].value++;
    }

    int32 free_i = 0;
    for(int32 i=0; i<MAX_N; i++){
        if(map[i].value!=0){ map[free_i] = map[i]; free_i++; } }
    
    //for(int32 i=0; i<dn; i++){
        //PRINTN(map[i]);
    //}

    thet = (map[0].key == 1 ? map[0].value : 0);
    if(thet < 2){
        dn = 1;
        x = 2-thet;
        std::cout << x << '\n'; 
        std::cout << 2 << '\n';
        std::cout << "1 2" << '\n';
        return 0;
    }
    epsi = sum - 2*(n-thet-1); 
    diff = epsi - thet;

    if (diff <= 0){
        map[0].value -= abs(diff); 
    }
    else{
        int32 ret = foo(0,2);
        if(ret != -1){}
        else{
            map[0].value -= ret;
        }
    }
    std::cout << x << '\n';
    std::cout << (dn-1)+map[0].value << '\n';
    printTree();
}
int32 foo(int64 r, int32 i){
    for(int32 j=i; j<n ; j++){
        if(map[j].value == 0) continue;
        r += map[j].key - 2;
        map[j].value--;
        del++;
        delsum += map[j].key;
        if(r == diff) { return 0; }
        else if(r < diff){ if( foo(r,j) == 0 )return 0; }
        else{ if((r-diff) <= (thet-2)) return (r-diff); } 
        delsum -= map[j].key;
        del--;
        map[j].value++;
        r-= map[j].key - 2;
    }
    return -1;
}
void printTree(){
    int32 v_iter = 1, off = 0;
    for(int32 i=dn-1; i >= 1; i--){
        for(int32 j=0; j<map[i].value; j++){
            for(int32 k=1; k<=map[i].key-off; k++){ 
                std::cout << v_iter << " " << v_iter+k << "\n"; 
            }
            v_iter += map[i].key-off; 
            off = 1;
        }
    }
}