<|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| ≠q 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.

This guarantees:
- Adjacent kept values never differ by exactly 1 (by how we chose predecessors),
- The subsequence is as long as possible (by DP optimality),
- Thus deletions are minimal.


4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

// -------------------- Segment Tree Template --------------------

// Generic iterative segment tree supporting range queries and point updates.
// The tree is 1-based internally, leaves start at index 'size'.
// merge: function to combine children's values.
// e: function returning the identity element for merge.
template<class T, T (*merge)(T, T), T (*e)()>
class SegmentTree {
private:
    int n;          // number of elements in the logical array
    int size;       // power-of-two base size
    vector<T> tr;   // tree array, size 2 * size

    // Update internal node from its two children.
    void pull(int x) {
        tr[x] = merge(tr[2 * x], tr[2 * x + 1]);
    }

public:
    SegmentTree() { init(vector<T>()); }

    // Construct tree with 'n' elements, all initialized with identity e().
    SegmentTree(int _n) { init(vector<T>(_n, e())); }

    // Construct tree from an existing array.
    SegmentTree(const vector<T>& a) { init(a); }

    // Initialize / rebuild the tree from array 'a'.
    void init(const vector<T>& a) {
        n = (int)a.size();
        // Find smallest power of two >= n.
        size = 1;
        while (size < n) size <<= 1;

        // Allocate and initialize with identity.
        tr.assign(2 * size, e());

        // Copy 'a' into the leaves.
        for (int i = 0; i < n; i++) {
            tr[size + i] = a[i];
        }
        // Build internal nodes.
        for (int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }

    // Point update: set position 'pos' (0-based) to 'val'.
    void update(int pos, T val) {
        int i = pos + size;  // go to leaf
        tr[i] = val;
        // Recompute parents up to the root
        for (i >>= 1; i > 0; i >>= 1) {
            pull(i);
        }
    }

    // Get the value at a single position (0-based).
    T get_pos(int pos) const {
        return tr[pos + size];
    }

    // Range query on [l, r] inclusive (0-based).
    T query(int l, int r) const {
        if (l > r) return e();  // empty range
        T leftRes = e();
        T rightRes = e();
        int L = l + size;
        int R = r + size + 1;   // we will treat as [L, R)

        while (L < R) {
            if (L & 1) {
                leftRes = merge(leftRes, tr[L]);
                L++;
            }
            if (R & 1) {
                --R;
                rightRes = merge(tr[R], rightRes);
            }
            L >>= 1;
            R >>= 1;
        }
        return merge(leftRes, rightRes);
    }
};

// -------------------- Problem-Specific Code --------------------

// We store (dp_value, index) as the node type.
// merge = max by dp_value (and then by index, since pair uses lexicographic).
pair<int,int> max_pair(pair<int,int> a, pair<int,int> b) {
    return max(a, b);
}

// Identity element for max over pairs: extremely small dp, invalid index.
pair<int,int> pair_identity() {
    return make_pair(INT_MIN, -1);
}

// Colors are up to 1e6; add a bit of slack for x+2 queries near boundary.
const int MAXV = (int)1e6 + 42;

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

    int n;
    if (!(cin >> n)) {
        return 0;
    }

    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    // Segment tree over color domain [0 .. MAXV].
    // At color v we store (best_dp_for_color_v, some_index_with_that_dp).
    SegmentTree<pair<int,int>, max_pair, pair_identity> seg(MAXV + 1);

    vector<int> dp(n);       // dp[i] = best subsequence length ending at i
    vector<int> parent(n);   // parent[i] = previous index in that subsequence

    // Process first element: can always start with it.
    dp[0] = 1;
    parent[0] = -1;
    // Update color c[0] with (1, 0)
    auto cur0 = seg.get_pos(c[0]);
    if (cur0 < make_pair(dp[0], 0)) {
        seg.update(c[0], make_pair(dp[0], 0));
    }

    // Process positions 1..n-1
    for (int i = 1; i < n; i++) {
        int x = c[i];

        // best = (best_dp, index) among valid predecessors.
        pair<int,int> best = make_pair(0, -1);  // length 0 means "no predecessor"

        // Allowed intervals: [0, x-2], [x, x], [x+2, MAXV].
        if (x >= 2) {
            auto cand = seg.query(0, x - 2);
            if (cand.first > best.first) best = cand;
        }

        {
            auto cand = seg.query(x, x);  // same color allowed
            if (cand.first > best.first) best = cand;
        }

        if (x + 2 <= MAXV) {
            auto cand = seg.query(x + 2, MAXV);
            if (cand.first > best.first) best = cand;
        }

        // Compute dp[i] and parent[i].
        dp[i] = best.first + 1;  // if best.first = 0 and best.second = -1, we get 1
        parent[i] = best.second;

        // Update the segment tree at color x with (dp[i], i) if it's better.
        auto old = seg.get_pos(x);
        pair<int,int> newval = old;
        if (newval < make_pair(dp[i], i)) {
            newval = make_pair(dp[i], i);
        }
        seg.update(x, newval);
    }

    // Find the overall best subsequence length and its ending position.
    int max_len = 0;
    int end_pos = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > max_len) {
            max_len = dp[i];
            end_pos = i;
        }
    }

    // Reconstruct indices of the subsequence by following parent pointers.
    vector<int> path;
    for (int cur = end_pos; cur != -1; cur = parent[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());

    // Output result
    int deletions = n - max_len;
    cout << deletions << "\n";
    for (int idx : path) {
        cout << c[idx] << ' ';
    }
    cout << "\n";

    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.