[중등부] 2024 KOI 1차대회 대비 모의고사 (1주차)

N마리의 오리들은 1번부터 N번까지 키순서로 번호가 매겨져있다 (모든 오리의 키는 다르고, 번호도 다르다).

오리들이 무작위 순서로 일렬로 나란히 걸어가고 있다.

오리들은 특이한 습성이 있기에 키가 오름차순인 순서로 무리를 지어 연속하여 일렬로 붙어서 걸어간다 (하나의 무리는 떨어져 걷지 않는다).

위 그림은 여러 무리의 오리들이 한 줄로 이어서 걸어가고 있는 상황이다.

생각을 해보니 첫 번째 오리인 3번 오리는 홀로 하나의 무리일 수도 있고, 뒤에 이어서 걸어오는 5번 오리와 함께 하나의 무리일 수도 있다.

그렇게 위의 그림에서는 [3], [3, 5], [5], [2], [1], [1, 4], [4], 총 일곱 종류의 오리 무리들이 있을 수 있다.

N마리의 오리들 중 한 무리의 오리들을 고르려고 하는데, 이 때, 고를 수 있는 무리의 종류가 몇 종류나 되는지 알아내는 프로그램을 작성하시오.