<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

458. The Monochrome Picture
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



An artist Kalevich is very ambitious and he has many different achievements over the years of his work. Kalevich became extremely famous when he first produced the largest digital picture in the world, setting a new world record in digital painting. It was a great victory with a very unusual image — a billion pixels in width, and... only one pixel in height. The win changed the entire Kalevich's life, so starting from that memorable moment all his digital masterpieces have the height of 1 pixel.

Recently Kalevich was invited to an exhibition in order to demonstrate the best picture he has ever painted. The picture is n pixels in width, 1 pixel in height, and it is called "The Monochrome Snake". As you have already guessed, the painting is indeed monochrome, so the i-th pixel is characterized by a single integer ci from 0 to 106 that is a grayscale representation of its color.

Many visitors at the exhibition have never seen any pictures with colors different from the standard 24-bit RGB, so they look at Kalevich's masterpiece with a great suspicion. Kalevich realized that the visitors do not like monochrome pictures at all, and what is even worse, if the colors of two adjacent pixels in a monochrome picture differ exactly by one, the visitors get angry and go away. Kalevich feels really nervous about this, so he wants to improve his painting in order to please the exigent visitors and keep them at the exhibition. At the same time he wants to preserve the idea of the picture — the snake should be still recognizable, so the only change he wants to make is to delete some pixels here and there. When he deletes a pixel, the width of the painting decreases by 1 of course. Kalevich will be satisfied with the result if |ri-ri+1| ≠ 1 for all i=1... m-1, where r is the final masterpiece and m is its length.

Your task is to help Kalevich and write a program that will help him to delete the minimum number of pixels from the picture, so that the resulting masterpiece does not have any two adjacent pixels with the colors that differ exactly by one.

Input
The first line of input contains a single integer n (1 ≤ n ≤ 105). The second line of input contains n integers separated by spaces — pixel colors c1, c2,..., cn (0 ≤ ci ≤ 106).

Output
To the first line of output print the minimum number of pixel deletions t that are needed to satisfy Kalevich's requirements. To the second line print m integer numbers (m = n-t)  — the masterpiece that is left after t pixel deletions.

If there are many solutions, you may output any of them.

Example(s)
sample input
sample output
6
4 2 2 1 1 1
2
4 1 1 1

sample input
sample output
5
1 2 3 2 1
2
1 3 1

<|response|>
1. Abridged problem statement
You are given a sequence of n grayscale values c₁…cₙ (0 ≤ cᵢ ≤ 10⁶). You may delete any elements, but you must preserve the order of those you keep.

You want to obtain a sequence r of maximum possible length such that for every adjacent pair in r, their values do NOT differ by exactly 1, i.e. |rᵢ − rᵢ₊₁| ≠ 1.

Output:
- the minimum number of deletions t = n − |r|,
- and one valid resulting sequence r.


2. Key observations

1. Deleting minimum pixels = keeping a longest valid subsequence
   We only delete elements; the remaining ones keep their original order. So this is a classic "longest subsequence under a constraint" problem. If we find the longest subsequence satisfying the rule, we automatically minimize deletions.

2. Local constraint depends only on neighboring kept elements
   For consecutive kept indices i < j in the subsequence, we need |c[i] − c[j]| ≠ 1. The constraint depends only on colors, not on how far apart indices are.

3. DP by last chosen position
   Let:
   - dp[i] = length of longest valid subsequence that ends at position i (i.e., includes c[i] last).

   Then:
   - dp[i] = 1 + max dp[j] over all j < i such that |c[i] − c[j]| ≠ 1.
   Brute-forcing j gives O(n²), too slow for n ≤ 10⁵.

4. Switch from indices to colors
   The constraint is about colors: |c[i] − c[j]| ≠ 1.
   We can track, for each color v, the best dp value of any position with that color:

   - best[v] = max dp[j] over all j with c[j] = v we have processed so far.

   For color x = c[i], all allowed previous colors v must satisfy |v − x| ≠ 1, so we want:
   - max over all colors v where v ≠ x − 1 and v ≠ x + 1 of best[v].

   Note: v = x is allowed (difference 0).

5. Allowed colors form at most 3 intervals
   Over the color axis (0…10⁶), disallowed colors are just x−1 and x+1. So allowed colors are:

   - [0, x−2]         (if x ≥ 2)
   - [x, x]           (same color)
   - [x+2, MAXV]      (if x+2 ≤ MAXV)

   Where MAXV ≥ 10⁶ is an upper bound we pick for the segment tree.

6. Segment tree over colors
   We need range maximum queries over best[v] on those intervals.
   Maintain a segment tree indexed by color v. In each node we store:
   - a pair (dp_value, index) = best dp and some position achieving it.

   For each i:
   - query up to three segments to find the best predecessor,
   - compute dp[i] = best_dp + 1,
   - record parent[i] = best_index for reconstruction,
   - update the tree at color c[i] with the new candidate (dp[i], i).

7. Reconstruction
   After processing all positions:
   - find i where dp[i] is maximal (let max_len, end_pos),
   - follow parent[] pointers from end_pos back to -1 to recover the subsequence indices,
   - reverse those indices to get correct order,
   - output n − max_len and the corresponding colors.

8. Complexity
   - Colors up to 10⁶ ⇒ segment tree size O(10⁶).
   - For each of n positions:
     - ≤ 3 range-max queries + 1 point update on the segment tree ⇒ O(log MAXV).
   - Total: O(n log 10⁶) ≈ O(n · 20), fine for n = 10⁵ and time limit 0.25s (especially in C++).


3. Full solution approach

1. Preliminaries
   - Read n and the array c[0…n−1].
   - Let MAXV = 10⁶ + some small margin (e.g. 42).

2. Segment tree structure
   - Build a segment tree on indices [0 … MAXV].
   - Each node stores a pair (best_dp, index).
   - The segment tree merge is max() on pairs (lexicographic: first, then second).
   - The identity (for empty) is (−∞, −1) so it doesn't affect maxima.

3. DP arrays
   - dp[i]: length of the best subsequence that ends exactly at i.
   - parent[i]: previous index used to reach dp[i] (−1 if this is the first element in subsequence).

4. Initialization
   - For i = 0:
     - We can start a subsequence with c[0], so dp[0] = 1, parent[0] = −1.
     - Update best for color c[0]:
       - At position c[0] in the segment tree, set (1, 0).

5. Transition step (for i from 1 to n−1)
   Let x = c[i].

   1) Initialize best = (0, −1): means "empty predecessor, length 0".
   2) Consider allowed color ranges:
      - If x ≥ 2:
        - cand = query(0, x−2); best = max(best, cand)
      - Same color:
        - cand = query(x, x); best = max(best, cand)
      - If x+2 ≤ MAXV:
        - cand = query(x+2, MAXV); best = max(best, cand)

   3) Now best = (best_dp, best_index) is the best previous subsequence we can extend.
      - dp[i] = best_dp + 1
      - parent[i] = best_index

   4) Update segment tree at color x:
      - current = get_pos(x)  // what's currently stored at this color
      - new_val = max(current, (dp[i], i))
      - update(x, new_val)

6. Find global best and reconstruct solution
   - max_len = max over all dp[i].
   - end_pos = some i achieving max_len.
   - Reconstruct indices:
     - path = empty list
     - cur = end_pos
     - while cur != −1:
         - path.append(cur)
         - cur = parent[cur]
     - reverse path.

   - The kept sequence is c[path[0]], c[path[1]], …, c[path[k−1]] where k = max_len.
   - Number of deletions: t = n − max_len.

7. Output
   - Print t on the first line.
   - Print the kept values c[path[j]] separated by spaces on the second line.


4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
// #include <coding_library/data_structures/segment_tree.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T, T (*merge)(T, T), T (*e)()>
class SegmentTree {
  private:
    int n, size;
    vector<T> tr;

    void pull(int x) { tr[x] = merge(tr[2 * x], tr[2 * x + 1]); }

  public:
    SegmentTree() { init(vector<T>()); }
    SegmentTree(int _n) { init(vector<T>(_n, e())); }
    SegmentTree(const vector<T>& _a) { init(_a); }

    void init(const vector<T>& _a) {
        n = _a.size();
        size = 1;
        while(size < n) {
            size <<= 1;
        }

        tr.assign(2 * size, e());
        for(int i = 0; i < n; i++) {
            tr[size + i] = _a[i];
        }
        for(int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }

    void update(int pos, T val) {
        pos += size;
        tr[pos] = val;
        for(pos >>= 1; pos > 0; pos >>= 1) {
            pull(pos);
        }
    }

    T get_pos(int pos) { return tr[pos + size]; }

    T query(int l, int r) {
        T ansl = e(), ansr = e();
        for(l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) {
                ansl = merge(ansl, tr[l++]);
            }
            if(r & 1) {
                ansr = merge(tr[--r], ansr);
            }
        }
        return merge(ansl, ansr);
    }

    T query_all() { return tr[1]; }

    template<bool (*f)(T)>
    int max_right(int l) const {
        return max_right(l, [](T x) { return f(x); });
    }
    template<class F>
    int max_right(int l, F f) const {
        if(l == n) {
            return n;
        }

        l += size;
        T sm = e();
        do {
            while(l % 2 == 0) {
                l >>= 1;
            }
            if(!f(merge(sm, tr[l]))) {
                while(l < size) {
                    l = (2 * l);
                    if(f(merge(sm, tr[l]))) {
                        sm = merge(sm, tr[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = merge(sm, tr[l]);
            l++;
        } while((l & -l) != l);
        return n;
    }

    template<bool (*f)(T)>
    int min_left(int r) const {
        return min_left(r, [](T x) { return f(x); });
    }
    template<class F>
    int min_left(int r, F f) const {
        if(r == -1) {
            return 0;
        }

        r += size + 1;
        T sm = e();
        do {
            r--;
            while(r > 1 && (r % 2)) {
                r >>= 1;
            }
            if(!f(merge(tr[r], sm))) {
                while(r < size) {
                    r = (2 * r + 1);
                    if(f(merge(tr[r], sm))) {
                        sm = merge(tr[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = merge(tr[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

pair<int, int> max_custom(pair<int, int> a, pair<int, int> b) {
    return max(a, b);
}
pair<int, int> max_e() { return {INT_MIN, -1}; }

const int MAXV = (int)1e6 + 42;

int n;
vector<int> c;

void read() {
    cin >> n;
    c.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> c[i];
    }
}

void solve() {
    // We can solve this problem with DP - there is a direct N^2 solution that
    // keeps a dp[pos] as a state, and tries to select the largest dp[last],
    // such that last < pos and |c[pos] - c[last]| != 1. The cost of (pos - last
    // - 1), so overall:
    //
    //    dp[pos] = max dp[last] + pos - last - 1, over the eligible last
    //    positions
    //
    // We do the classic approach of separating what depends on last, and what
    // depends on pos, which in this case makes it easy as there are no terms
    // depending on both.
    //
    //    dp[pos] = pos - 1 + max (dp[last] - last)
    //
    // Essentially, for some pos, we are interested in the largest value of
    // dp[last] - last, excluding such positions that c[last] = c[pos]. We can
    // notice that this is two ranges: [0;c[pos]-2], [c[pos];c[pos]] and [c[pos]
    // + 2;MAXV], and so we can use a max segment tree to query this
    // efficiently. The problem does ask to recover the solution, so at index
    // c[last] in the segment tree, we will keep the largest value of {dp[last]
    // - last, last}.
    //
    // The overall complexity is O(N log MAXV).

    auto t = SegmentTree<pair<int, int>, max_custom, max_e>(MAXV + 1);

    vector<int> dp(n);
    vector<int> parent(n, -1);

    dp[0] = 1;
    t.update(c[0], {1, 0});

    for(int i = 1; i < n; i++) {
        pair<int, int> best = {0, -1};

        if(c[i] >= 2) {
            best = max(best, t.query(0, c[i] - 2));
        }
        best = max(best, t.query(c[i], c[i]));
        if(c[i] + 2 <= MAXV) {
            best = max(best, t.query(c[i] + 2, MAXV));
        }

        dp[i] = best.first + 1;
        parent[i] = best.second;

        auto current_val = make_pair(dp[i], i);
        t.update(c[i], max(t.get_pos(c[i]), current_val));
    }

    int max_len = *max_element(dp.begin(), dp.end());
    int end_pos = max_element(dp.begin(), dp.end()) - dp.begin();

    vector<int> path;
    int curr = end_pos;
    while(curr != -1) {
        path.push_back(curr);
        curr = parent[curr];
    }
    reverse(path.begin(), path.end());

    cout << n - max_len << '\n';
    for(int p: path) {
        cout << c[p] << ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments

```python
import sys

# We will implement an iterative segment tree for max over pairs (dp, index).
# Python compares tuples lexicographically (first element, then second),
# so max() on tuples works as needed.

INT_MIN = -10**18          # sufficiently small negative number
MAXV = 10**6 + 42          # color domain upper bound for segment tree


class SegmentTree:
    """
    Segment tree for range maximum over tuples (dp, index) on [0..n-1].

    Node value is a tuple (dp_value, index).
    Identity is (INT_MIN, -1).
    """

    def __init__(self, n):
        # n = number of leaves
        self.n = n
        size = 1
        while size < n:
            size <<= 1
        self.size = size
        # tree nodes, 1-based internal indexing; we'll use slice [1 .. 2*size-1].
        self.tr = [(INT_MIN, -1)] * (2 * size)

    def update(self, pos, val):
        """
        Point update: set position 'pos' (0-based) to 'val'.
        """
        i = pos + self.size
        self.tr[i] = val
        i >>= 1
        # Rebuild parents up to root
        while i > 0:
            left = self.tr[2 * i]
            right = self.tr[2 * i + 1]
            # max by dp_value, then index (tuple comparison)
            self.tr[i] = left if left >= right else right
            i >>= 1

    def get_pos(self, pos):
        """
        Get the value stored at leaf 'pos' (0-based).
        """
        return self.tr[pos + self.size]

    def query(self, l, r):
        """
        Range maximum on [l, r] inclusive, 0-based.
        Returns (INT_MIN, -1) for empty ranges (l > r).
        """
        if l > r:
            return (INT_MIN, -1)

        resl = (INT_MIN, -1)
        resr = (INT_MIN, -1)
        L = l + self.size
        R = r + self.size + 1  # treat the right boundary as exclusive

        while L < R:
            if L & 1:
                if self.tr[L] > resl:
                    resl = self.tr[L]
                L += 1
            if R & 1:
                R -= 1
                if self.tr[R] > resr:
                    resr = self.tr[R]
            L >>= 1
            R >>= 1

        return resl if resl >= resr else resr


def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    c = [int(next(it)) for _ in range(n)]

    # Segment tree over color domain [0 .. MAXV].
    seg = SegmentTree(MAXV + 1)

    dp = [0] * n       # dp[i] = best subsequence length ending at i
    parent = [-1] * n  # parent[i] = previous index in that subsequence

    # First element: start a subsequence with it
    dp[0] = 1
    parent[0] = -1
    old = seg.get_pos(c[0])
    if old < (dp[0], 0):
        seg.update(c[0], (dp[0], 0))

    # Process subsequent elements
    for i in range(1, n):
        x = c[i]
        best_dp, best_idx = 0, -1  # best predecessor info

        # Query allowed intervals: [0, x-2], [x, x], [x+2, MAXV].

        # [0, x-2]
        if x >= 2:
            cand = seg.query(0, x - 2)
            if cand[0] > best_dp:
                best_dp, best_idx = cand

        # [x, x] (same color)
        cand = seg.query(x, x)
        if cand[0] > best_dp:
            best_dp, best_idx = cand

        # [x+2, MAXV]
        if x + 2 <= MAXV:
            cand = seg.query(x + 2, MAXV)
            if cand[0] > best_dp:
                best_dp, best_idx = cand

        # Current dp and parent
        dp[i] = best_dp + 1
        parent[i] = best_idx

        # Update color x with (dp[i], i) if it is better for that color.
        old = seg.get_pos(x)
        if old < (dp[i], i):
            seg.update(x, (dp[i], i))

    # Find best subsequence length and its ending index
    max_len = 0
    end_pos = 0
    for i in range(n):
        if dp[i] > max_len:
            max_len = dp[i]
            end_pos = i

    # Reconstruct the subsequence indices.
    path = []
    cur = end_pos
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()

    deletions = n - max_len

    # Output result
    out_lines = []
    out_lines.append(str(deletions))
    out_lines.append(' '.join(str(c[idx]) for idx in path))
    sys.stdout.write('\n'.join(out_lines) + '\n')


if __name__ == "__main__":
    solve()
```

This completes the step-by-step explanation and both C++ and Python solutions that implement the optimal O(n log MAXV) algorithm.
