오리 무리 2 timer 1s memory 1024MB

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

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

오리들은 특이한 습성이 있기에 키가 오름차순인 순서로 걸어간다. (단 몇몇 오리들은 걸음이 느려 무리와 다소 떨어져 걸어갈 수 있다)

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

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

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

이를 알아내는 프로그램을 작성하시오.