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
#include <cstdio>

using namespace std;

int create_node(int *S,int M,int N)
{
// S[m] - count of nodes with m edges
// M - number of edges in this node
// N - number of this node
int m,n = N+1;

	for (m = 0; m < M-2; m++)	// -1 due to egde up -1 due to last edge (possible multiple)
	{
		printf("%d %d\n",N,n);	//creating nodes with 1 edge
		S[1]--;
		n++;
	}
	printf("%d %d\n",N,n);	//last edge for this node, possible with multiple edges
	S[M]--;
	m = M;
	while (m > 1 && S[m] == 0) m--;
	if (m > 1) n = create_node(S,m,n);
	
	return n;
}

int main()
{
int N,S[200001],s,M,m,R,x;

	scanf("%d",&N);
	for (int n = 0; n < N; n++) S[n] = 0;
	
	M = 0;
	R = 0;
	for (int n = 0; n < N; n++)
	{
		scanf("%d",&s);
		if (M < s) M = s;
		S[s]++;
		if (s > 2) R += s-2;
	}
	R += 2;
	
//	printf("Debug: S[1] = %d, R = %d\n",S[1],R);
	
	if (S[1] != R)
	{
		if (S[1] == 0) x = 2;
		else if (S[1] == 1) x = 1;
		else x = 0;
		printf("%d\n%d\n",x,2);
		printf("%d %d\n",1,2); // 1st node with 1 edge		
	}
	else if (S[1] == R)
	{
		x = 0;
		printf("%d\n%d\n",x,N);
		printf("%d %d\n",1,2); // 1st node with 1 edge
		S[1]--;
		if (N > 2) create_node(S,M,2);
	}
	
	return 0;
}