H. Repairing Of String

Codeforces

IDCF774H

Time2000ms

Memory256MB

Difficulty—

constructive algorithms

Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet. After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. But Stepan remembers some information about the string, namely the sequence of integers _c_1, _c_2, ..., _c__n_, where _n_ equals the length of the string _s_, and _c__i_ equals the number of substrings in the string _s_ with the length _i_, consisting of the **same** letters. The substring is a sequence of consecutive characters in the string _s_. For example, if the Stepan's favorite string is equal to "_tttesst_", the sequence _c_ looks like: _c_ = \[7, 3, 1, 0, 0, 0, 0\]. Stepan asks you to help to repair his favorite string _s_ according to the given sequence _c_1, _c_2, ..., _c__n_. ## Input The first line contains the integer _n_ (1 ≤ _n_ ≤ 2000) — the length of the Stepan's favorite string. The second line contains the sequence of integers _c_1, _c_2, ..., _c__n_ (0 ≤ _c__i_ ≤ 2000), where _c__i_ equals the number of substrings of the string _s_ with the length _i_, consisting of the same letters. It is guaranteed that the input data is such that the answer always exists. ## Output Print the repaired Stepan's favorite string. If there are several answers, it is allowed to print any of them. The string should contain only lowercase letters of the English alphabet. [samples] ## Note In the first test Stepan's favorite string, for example, can be the string "_kkrrrq_", because it contains 6 substrings with the length 1, consisting of identical letters (they begin in positions 1, 2, 3, 4, 5 and 6), 3 substrings with the length 2, consisting of identical letters (they begin in positions 1, 3 and 4), and 1 substring with the length 3, consisting of identical letters (it begins in the position 3).

Samples

Input #1

6
6 3 1 0 0 0

Output #1

kkrrrq

Input #2

4
4 0 0 0

Output #2

abcd

API Response (JSON)

{
  "problem": {
    "name": "H. Repairing Of String",
    "description": {
      "content": "Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet. After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF774H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet.\n\nAfter graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments