A. Snacktower

Codeforces

IDCF767A

Time2000ms

Memory256MB

Difficulty—

data structuresimplementation

English · Original

Chinese · Translation

Formal · Original

According to an old legeng, a long time ago Ankh-Morpork residents did something wrong to miss Fortune, and she cursed them. She said that at some time _n_ snacks of distinct sizes will fall on the city, and the residents should build a Snacktower of them by placing snacks one on another. Of course, big snacks should be at the bottom of the tower, while small snacks should be at the top. Years passed, and once different snacks started to fall onto the city, and the residents began to build the Snacktower. <center>![image](https://espresso.codeforces.com/240575cab323e956b5e86d7c49e88e028d650fc5.png)</center>However, they faced some troubles. Each day exactly one snack fell onto the city, but their order was strange. So, at some days the residents weren't able to put the new stack on the top of the Snacktower: they had to wait until all the bigger snacks fell. Of course, in order to not to anger miss Fortune again, the residents placed each snack on the top of the tower immediately as they could do it. Write a program that models the behavior of Ankh-Morpork residents. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 100 000) — the total number of snacks. The second line contains _n_ integers, the _i_\-th of them equals the size of the snack which fell on the _i_\-th day. Sizes are distinct integers from 1 to _n_. ## Output Print _n_ lines. On the _i_\-th of them print the sizes of the snacks which the residents placed on the top of the Snacktower on the _i_\-th day in the order they will do that. If no snack is placed on some day, leave the corresponding line empty. [samples] ## Note In the example a snack of size 3 fell on the first day, and the residents immediately placed it. On the second day a snack of size 1 fell, and the residents weren't able to place it because they were missing the snack of size 2. On the third day a snack of size 2 fell, and the residents immediately placed it. Right after that they placed the snack of size 1 which had fallen before.

根据一个古老的传说，很久以前，安克-莫尔克的居民做了一些惹怒命运女神的事情，于是她诅咒了他们。她说，在某个时刻，会有 #cf_span[n] 个大小互不相同的零食落入城市，居民们必须将这些零食一个接一个地堆叠起来，建成一座“零食塔”。当然，大的零食必须在塔底，小的零食必须在塔顶。岁月流逝，不同大小的零食开始陆续落入城市，居民们也开始建造零食塔。然而，他们遇到了一些麻烦。每天恰好有一个零食落入城市，但它们的顺序很奇怪。因此，在某些日子里，居民们无法将新落下的零食放在零食塔的顶部：他们必须等待所有更大的零食都落下。当然，为了避免再次激怒命运女神，居民们一旦能够放置零食，就会立即将其放在塔顶。请编写一个程序，模拟安克-莫尔克居民的行为。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100 000]）—— 零食的总数。第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 天落下的零食的大小。这些大小是互不相同的整数，范围从 #cf_span[1] 到 #cf_span[n]。请输出 #cf_span[n] 行。在第 #cf_span[i] 行中，输出第 #cf_span[i] 天居民在零食塔顶部放置的零食的大小，按放置顺序排列。如果某天没有放置任何零食，则对应行留空。在示例中，第一天落下一个大小为 #cf_span[3] 的零食，居民立即将其放置。第二天落下一个大小为 #cf_span[1] 的零食，但居民无法放置它，因为他们缺少大小为 #cf_span[2] 的零食。第三天落下一个大小为 #cf_span[2] 的零食，居民立即将其放置，紧接着他们又放置了之前落下的大小为 #cf_span[1] 的零食。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100 000]）—— 零食的总数。第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 天落下的零食的大小。这些大小是互不相同的整数，范围从 #cf_span[1] 到 #cf_span[n]。 ## Output 请输出 #cf_span[n] 行。在第 #cf_span[i] 行中，输出第 #cf_span[i] 天居民在零食塔顶部放置的零食的大小，按放置顺序排列。如果某天没有放置任何零食，则对应行留空。 [samples] ## Note 在示例中，第一天落下一个大小为 #cf_span[3] 的零食，居民立即将其放置。第二天落下一个大小为 #cf_span[1] 的零食，但居民无法放置它，因为他们缺少大小为 #cf_span[2] 的零食。第三天落下一个大小为 #cf_span[2] 的零食，居民立即将其放置，紧接着他们又放置了之前落下的大小为 #cf_span[1] 的零食。

Let $ n \in \mathbb{N} $, $ n \geq 1 $. Let $ a = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $, where $ a_i $ is the size of the snack that falls on day $ i $. Let $ S \subseteq \{1, 2, \dots, n\} $ be a set representing the snacks that have fallen but not yet placed on the tower. Let $ T $ be a stack (LIFO structure) representing the snack tower, with the largest snack at the bottom and smallest at the top. Let $ \text{next} = n $ be the largest snack size that has not yet been placed on the tower. For each day $ i = 1 $ to $ n $: 1. Add $ a_i $ to $ S $. 2. While $ \text{next} \in S $: - Remove $ \text{next} $ from $ S $. - Push $ \text{next} $ onto $ T $. - Decrement $ \text{next} $ by 1. 3. Output the sequence of snacks pushed onto $ T $ on day $ i $ (in the order they were pushed). The output for day $ i $ is the list of snack sizes placed on the tower on that day, in the order they were placed (from bottom to top of the newly added segment). If no snack is placed on day $ i $, output an empty line.

Samples

Input #1

3
3 1 2

Output #1

3
 
2 1

Input #2

5
4 5 1 2 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Snacktower",
    "description": {
      "content": "According to an old legeng, a long time ago Ankh-Morpork residents did something wrong to miss Fortune, and she cursed them. She said that at some time _n_ snacks of distinct sizes will fall on the ci",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF767A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "According to an old legeng, a long time ago Ankh-Morpork residents did something wrong to miss Fortune, and she cursed them. She said that at some time _n_ snacks of distinct sizes will fall on the ci...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "根据一个古老的传说，很久以前，安克-莫尔克的居民做了一些惹怒命运女神的事情，于是她诅咒了他们。她说，在某个时刻，会有 #cf_span[n] 个大小互不相同的零食落入城市，居民们必须将这些零食一个接一个地堆叠起来，建成一座“零食塔”。当然，大的零食必须在塔底，小的零食必须在塔顶。\n\n岁月流逝，不同大小的零食开始陆续落入城市，居民们也开始建造零食塔。\n\n然而，他们遇到了一些麻烦。每天恰好有一个零食落...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ n \\geq 1 $.  \nLet $ a = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, where $ a_i $ is the size of the snack that falls on day $ i $.\n\nLet $ S \\subse...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments