English · Original
Chinese · Translation
Formal · Original
Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from $1$ to the number of steps in this stairway. She speaks every number aloud. For example, if she climbs two stairways, the first of which contains $3$ steps, and the second contains $4$ steps, she will pronounce the numbers $1, 2, 3, 1, 2, 3, 4$.
You are given all the numbers pronounced by Tanya. How many stairways did she climb? Also, output the number of steps in each stairway.
The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.
## Input
The first line contains $n$ ($1 \le n \le 1000$) — the total number of numbers pronounced by Tanya.
The second line contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — all the numbers Tanya pronounced while climbing the stairs, in order from the first to the last pronounced number. Passing a stairway with $x$ steps, she will pronounce the numbers $1, 2, \dots, x$ in that order.
The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.
## Output
In the first line, output $t$ — the number of stairways that Tanya climbed. In the second line, output $t$ numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.
[samples]
[{"iden":"statement","content":"小女孩塔尼娅在一座多层建筑内爬楼梯。每次塔尼娅爬一段楼梯时，她都会从 $1$ 开始计数，直到该段楼梯的步数，并将每个数字大声说出来。例如，如果她爬了两段楼梯，第一段有 $3$ 步，第二段有 $4$ 步，她会说出数字 $1, 2, 3, 1, 2, 3, 4$。\n\n给你塔尼娅说出的所有数字。请问她爬了几段楼梯？并输出每段楼梯的步数。\n\n给定的序列是塔尼娅在爬一段或多段楼梯时可能说出的有效序列。\n\n第一行包含 $n$ ($1 lt.eq n lt.eq 1000$) —— 塔尼娅说出的数字总数。\n\n第二行包含整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 1000$) —— 塔尼娅在爬楼梯时按顺序说出的所有数字。当她经过一段有 $x$ 步的楼梯时，她会按顺序说出数字 $1, 2, dots.h, x$。\n\n给定的序列是塔尼娅在爬一段或多段楼梯时可能说出的有效序列。\n\n第一行输出 $t$ —— 塔尼娅爬的楼梯段数。第二行输出 $t$ 个数字 —— 她每段楼梯的步数。请按通过楼梯的正确顺序写出这些数字。"},{"iden":"input","content":"第一行包含 $n$ ($1 lt.eq n lt.eq 1000$) —— 塔尼娅说出的数字总数。第二行包含整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 1000$) —— 塔尼娅在爬楼梯时按顺序说出的所有数字。当她经过一段有 $x$ 步的楼梯时，她会按顺序说出数字 $1, 2, dots.h, x$。给定的序列是塔尼娅在爬一段或多段楼梯时可能说出的有效序列。"},{"iden":"output","content":"第一行输出 $t$ —— 塔尼娅爬的楼梯段数。第二行输出 $t$ 个数字 —— 她每段楼梯的步数。请按通过楼梯的正确顺序写出这些数字。"},{"iden":"examples","content":"输入71 2 3 1 2 3 4输出23 4 输入41 1 1 1输出41 1 1 1 输入51 2 3 4 5输出15 输入51 2 1 2 1输出32 2 1 "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be the total number of pronounced numbers.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of integers pronounced by Tanya, where $ a_i \in \mathbb{Z}^+ $.
**Constraints**
1. $ 1 \le n \le 1000 $
2. $ 1 \le a_i \le 1000 $ for all $ i \in \{1, \dots, n\} $
3. The sequence $ A $ is valid: it consists of one or more contiguous increasing subsequences starting at 1, each representing the steps of a stairway.
**Objective**
Find the number of stairways $ t $ and the sequence $ S = (s_1, s_2, \dots, s_t) $, where each $ s_j \in \mathbb{Z}^+ $ is the number of steps in the $ j $-th stairway, such that:
- Each stairway corresponds to a maximal contiguous subsequence $ (a_k, a_{k+1}, \dots, a_{k+s_j-1}) = (1, 2, \dots, s_j) $,
- The entire sequence $ A $ is the concatenation of these subsequences in order.
**Output**
- $ t $: the count of stairways,
- $ S = (s_1, s_2, \dots, s_t) $: the lengths of the stairways in order.
**Solution Method**
Each time $ a_i = 1 $, a new stairway begins. The length of a stairway is the value of the last number in that increasing run (i.e., the maximum value before the next 1 or end of sequence).
Thus, $ t $ is the number of times 1 appears in $ A $, and each $ s_j $ is the last element of the $ j $-th increasing run starting at 1.
API Response (JSON)
{
"problem": {
"name": "A. Tanya and Stairways",
"description": {
"content": "Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from $1$ to the number of steps in this stairway. She speaks every num",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1005A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from $1$ to the number of steps in this stairway. She speaks every num...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"小女孩塔尼娅在一座多层建筑内爬楼梯。每次塔尼娅爬一段楼梯时，她都会从 $1$ 开始计数，直到该段楼梯的步数，并将每个数字大声说出来。例如，如果她爬了两段楼梯，第一段有 $3$ 步，第二段有 $4$ 步，她会说出数字 $1, 2, 3, 1, 2, 3, 4$。\\n\\n给你塔尼娅说出的所有数字。请问她爬了几段楼梯？并输出每段楼梯的步数。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the total number of pronounced numbers. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of integers pronounced by Tanya, where $ a_i \\in \\mathbb{Z}^+...",
"is_translate": false,
"language": "Formal"
}
]
}