Rounds to collect numbers

Analysis

We have a permutation $A$ of the numbers $\{1,2,\dots,n\}$. We want to "collect" the numbers in ascending order (from $1$ up to $n$) by repeatedly scanning $A$ from left to right. Each scan (or round) allows us to pick up as many of the needed numbers in increasing order as we encounter them. Once we cannot proceed (i.e., we've passed a needed number), we have to start a new round.

A clean way to figure out how many rounds this process will take uses the following observation:

1. Let $p_i$ be the position of the number $i$ in the array $A$. (That is, if $A[k] = i$, then $p_i = k$.)
2. In a single left-to-right scan, we can pick up the numbers $1, 2, 3, \dots$ in ascending numerical order as long as their positions also increase; that is, as long as $$p_1 < p_2 < p_3 < \dots$$
3. If at some point $p_i > p_{i+1}$, that means the position of $i+1$ is to the left of the position of $i$ in the array, so once we've passed $i$, we have already skipped over $i+1$. Therefore, $i+1$ cannot be collected in the same pass as $i$, forcing a new round to start.

Hence, counting how many times $p_i > p_{i+1}$ (for $i = 1,2,\dots,n-1$) tells us exactly how many "breaks" in the sequence we have—and thus how many times we need a new round.

Formally,

$$\text{Number of rounds} \;=\; 1 \;+\; \bigl|\{\, i \mid p_i > p_{i+1},\; 1 \le i < n \}\bigr|.$$

---

Step-by-Step Solution

1. Read input:

   • $n$, the size of the array (and the range of numbers from $1$ to $n$).
   • The array $A$ of length $n$, which contains a permutation of $\{1,2,\dots,n\}$.

2. Record positions:
   Create an array pos of length $n+1$ (if using 1-based indexing) so that:

   $$\text{pos}[x] = \text{index of } x \text{ in the array }A.$$

   Concretely, if you read the array as $A[1], A[2], \dots, A[n]$ (1-based):

   pseudo
   for i in 1..n:
       pos[A[i]] = i

3. Count breaks:
   Initialize rounds = 1.
   Then compare consecutive positions $p_i$ and $p_{i+1}$ for $i=1$ to $n-1$.
   Each time we find $p_i > p_{i+1}$, it means we need another round:

   pseudo
   rounds = 1
   for i in 1..(n-1):
       if pos[i] > pos[i+1]:
           rounds += 1

4. Print the result (rounds).

---

Example Walkthrough

Consider the example:

text
n = 5
A = [4, 2, 1, 5, 3]

1. We find the positions of each number (1-based indexing for clarity):

   • The number $1$ is at index $3$, so $p_1 = 3$.
   • The number $2$ is at index $2$, so $p_2 = 2$.
   • The number $3$ is at index $5$, so $p_3 = 5$.
   • The number $4$ is at index $1$, so $p_4 = 1$.
   • The number $5$ is at index $4$, so $p_5 = 4$.

2. Compare positions for $i$ from $1$ to $4$:

   • Compare $p_1 = 3$ and $p_2 = 2$. Since $3 > 2$, break → need a new round.
   • Compare $p_2 = 2$ and $p_3 = 5$. Since $2 < 5$, no new round needed here.
   • Compare $p_3 = 5$ and $p_4 = 1$. Since $5 > 1$, break → need a new round.
   • Compare $p_4 = 1$ and $p_5 = 4$. Since $1 < 4$, no new round here.

   We have 2 "breaks" → total rounds = $1 + 2 = 3$.

This matches the process of physically scanning the array in passes:

• Round 1: Collect the 1.
• Round 2: Collect 2 then 3.
• Round 3: Finally collect 4 then 5.

Hence the answer is 3.

---

Final Answer

The total number of rounds equals:

$$1 \;+\; \text{(number of indices } i \text{ where } p_i > p_{i+1}).$$

To implement:

1. Read $n$ and the array $A$.
2. Build pos so that pos[value] = index_of_that_value_in_A.
3. Initialize rounds = 1.
4. For $i = 1$ to $n-1$:
   • If pos[i] > pos[i+1], increment rounds.
5. Output rounds.

This runs in $O(n)$ time and $O(n)$ space, which is efficient for $n \le 2 \times 10^5$.