E. Merge Equal Elements

Codeforces

IDCF926E

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsdata structures

You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_. While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such pair, find the leftmost (with the smallest indices of elements). If the two integers are equal to _x_, delete both and insert a single integer _x_ + 1 on their place. This way the number of elements in the sequence is decreased by 1 on each step. You stop performing the operation when there is no pair of equal consecutive elements. For example, if the initial sequence is \[5, 2, 1, 1, 2, 2\], then after the first operation you get \[5, 2, 2, 2, 2\], after the second — \[5, 3, 2, 2\], after the third — \[5, 3, 3\], and finally after the fourth you get \[5, 4\]. After that there are no equal consecutive elements left in the sequence, so you stop the process. Determine the final sequence after you stop performing the operation. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of elements in the sequence. The second line contains the sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109). ## Output In the first line print a single integer _k_ — the number of elements in the sequence after you stop performing the operation. In the second line print _k_ integers — the sequence after you stop performing the operation. [samples] ## Note The first example is described in the statements. In the second example the initial sequence is \[1000000000, 1000000000, 1000000000, 1000000000\]. After the first operation the sequence is equal to \[1000000001, 1000000000, 1000000000\]. After the second operation the sequence is \[1000000001, 1000000001\]. After the third operation the sequence is \[1000000002\]. In the third example there are no two equal consecutive elements initially, so the sequence does not change.

Samples

Input #1

6
5 2 1 1 2 2

Output #1

2
5 4

Input #2

4
1000000000 1000000000 1000000000 1000000000

Output #2

1
1000000002

Input #3

7
4 10 22 11 12 5 6

Output #3

7
4 10 22 11 12 5 6

API Response (JSON)

{
  "problem": {
    "name": "E. Merge Equal Elements",
    "description": {
      "content": "You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_. While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF926E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_.\n\nWhile possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments