#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; void solve() { int n; cin >> n; vector dp(n, 1e9); vector> ans; rep(k, 0, n) { int x; cin >> x; int i = lower_bound(dp.begin(), dp.end(), x) - dp.begin(); if (dp[i] == 1e9) { ans.push_back({k + 1, -1}); } dp[i] = x; } rep(i, 0, ans.size()) ans[i].second = dp[i]; for (auto &p : ans) { cout << p.first << " " << p.second << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; while (t--) solve(); }