Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5+5;
- int a[N], len[N], p[N], last[10*N];
- struct comp {
- bool operator()(const int& l, const int& r) const {
- return len[l] == len[r] ? l < r : len[l] > len[r];
- }
- };
- void dfs(int x) {
- if (!x) return;
- dfs(p[x]);
- printf("%d ", a[x]);
- }
- int main() {
- set<int, comp> s;
- s.insert(0);
- a[0] = -2;
- int n; scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- scanf("%d", a+i);
- bool done = false;
- for (set<int, comp>::iterator it = s.begin(); it != s.end(); it++) {
- int j = *it;
- if (abs(a[j]-a[i]) == 1) continue;
- s.erase(i);
- len[i] = len[j] + 1;
- s.insert(i);
- p[i] = j;
- if (last[a[i]]) s.erase(last[a[i]]);
- last[a[i]] = i;
- done = true;
- break;
- }
- }
- int x = *s.begin();
- printf("%d\n", n-len[x]);
- dfs(x);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement