지뢰
시간 제한2초메모리 제한128 MB
직선상에 놓인 N개 지뢰의 연쇄 폭발 규칙이 주어질 때, 모든 지뢰를 터뜨리기 위해 직접 기폭해야 할 최소 지뢰 번호들을 구합니다.
문제
N개의 지뢰가 일직선 위에 같은 간격으로 놓여 있다. i번째 지뢰의 충격 강도는 P_i이다.
한 지뢰가 폭발하면 바로 왼쪽과 오른쪽에 있는 아직 폭발하지 않은 지뢰에 자신의 충격 강도만큼 힘을 전달한다. 전달된 힘이 그 지뢰의 충격 강도보다 클 때만 그 지뢰도 폭발하며, 다시 같은 방식으로 양옆에 힘을 전달한다. 전달된 힘이 충격 강도 이하이면 그 방향의 연쇄 반응은 멈춘다.
직접 폭발시킬 지뢰를 여러 개 고를 수 있다. 모든 지뢰가 폭발하도록 하면서 직접 폭발시키는 지뢰 수를 최소로 만들 때, 직접 폭발시켜야 하는 지뢰들의 번호를 구하시오.
입력
첫째 줄에 지뢰의 개수 N이 주어진다. 이어지는 N개의 줄에는 1번부터 N번까지 각 지뢰의 충격 강도 P_i가 차례대로 주어진다.
출력
직접 폭발시켜야 하는 지뢰의 번호를 오름차순으로 한 줄에 하나씩 출력한다.
제한
- 1 <= N <= 50,000
- 1 <= P_i <= 10,000