Collecting Numbers

Explanation

Here, in this problem, we are given an array of numbers which contains numbers from 1 to N. We are told to take trips from left to right of the array and collect whatever numbers appear in increasing order. We need to find out how many trips we need to take to collect all the numbers from 1 to N.

Let's take an example. Suppose we have an array [3, 1, 2, 4]. We can collect the numbers in the following order:

1. [3, 1, 2, 4] - We collect 3 and 4.
2. [1, 2] - We collect 1 and 2.

So, we need to take 2 trips to collect all the numbers from 1 to 4.

Now, we can solve this using a simple observation. For every pair of numbers, if the first number appears after the second number then we'll need an extra trip. For example, in the above array, for the pair (2, 3), 2 appears after 3. So, we'll need an extra trip that we would have needed otherwise (which would default to 1).

So, our answer would be: 1 + (number of pairs where first number appears after second number).

Code

n = int(input())
arr = list(map(int, input().split()))

indices = {}
for i, e in enumerate(arr):
    indices[e] = i

count = 1
for i in range(1, n):
    if indices[i] > indices[i + 1]:
        count += 1

print(count)