思路
首先看全是零的部分分，如果 \(n\) 不是很小的时候，手模几个发现似乎都可以构造出来，我们考虑转化。
我们把所有的数分成是 \(0\) 的和不是 \(0\) 的，对于不是 \(0\) 的数，我们可以让他两两配对取 \(\operatorname{mex}\) 变成是 \(0\) 的数，此时我们剩下一堆 \(0\)，和至多一个非 \(0\) 的数。
分类讨论一下。
如果剩下一个非 \(0\) 的数，考虑怎么用这几个已有 \(0\) 构造出非 \(0\) 的数。
如图：
如果没有剩下非 \(0\) 的数，可以这样构造。
如图：
这样可以轻松解决，注意当 \(n\) 较小的时候需要特判。
代码
int bg = n + 1;
for(int i = 1; i <= n; ++i) if(a[i] != 0){ bg = i; break;}
int cnt = bg - 1;
for(int i = bg; i + 1 <= n; i += 2) ans.pb({a[i], a[i + 1]}), cnt++;
if((n - bg + 1) % 2 == 0 && bg != 0){int now = 0;for(int i = 2; i <= cnt - 2; ++i) ans.pb({0, now}), now = mex(now, 0);ans.pb({0, 0});ans.pb({now, 1});now = mex(now, 1);if(now == 0) for(auto [a, b] : ans) cout << a << ' ' << b << '\n';
}
else{int now = 0;for(int i = 2; i <= cnt; ++i) ans.pb({0, now}), now = mex(now, 0);ans.pb({now, a[n]});now = mex(now, a[n]);if(now == 0) for(auto [a, b] : ans) cout << a << ' ' << b << '\n';
}
造福后人给一个 checker。
inline void check(){multiset<int> s;for(int i = 1; i <= n; ++i) s.insert(a[i]), cerr << a[i] << ' ';cerr << '\n';for(auto [a, b] : ans){if(s.find(a) != s.end()) s.erase(s.find(a));else cerr << "WA" << '\n', assert(0);if(s.find(b) != s.end()) s.erase(s.find(b));else cerr << "WA" << '\n', assert(0);s.insert(mex(a, b));}if(s.size() > 1) cerr << "WA" << '\n', assert(0);if(*s.begin() != 0) cerr << "WA" << '\n',assert(0);else cerr << "AC" << '\n';
}