호 안에 수류탄이야!!

시간 제한2초메모리 제한512 MB

요약
수직선 위에 선 사람들의 투척 사거리가 주어질 때, 수류탄이 첫 사람에서 마지막 사람까지 전달될 수 있는지 판정한다.
난이도

쉬움10점 중 3점

유형
그리디, 구간, 구현
정답자
아직 제출이 없습니다

문제

욱제를 포함한 NN명이 수직선 위에 일렬로 서 있다. 욱제의 좌표는 00이며, 좌표는 왼쪽부터 순서대로 주어진다. 각 사람은 자신의 사거리 rr 안에 있는 누구에게나 수류탄을 던질 수 있고, 날아온 수류탄은 항상 받을 수 있다. 같은 좌표에 여러 명이 있으면 그중 아무나 받아서 다음 사람에게 던질 수 있다.

수류탄은 욱제에게서 시작한다. 왼쪽에서 NN번째 사람, 곧 가장 오른쪽 사람이 수류탄을 받으면 게임이 조용히 끝난다. 모두가 협력하므로 도달 가능한 전달 경로가 하나라도 있으면 성공이다. 바닥에 떨어지면 실패한다.

입력

첫째 줄에 NN이 주어진다. 1≤N≤300001 \le N \le 30000이다.

둘째 줄에 좌표 NN개가 왼쪽부터 순서대로 주어진다. 첫 좌표는 욱제의 좌표 00이다. 각 좌표는 00 이상 10000001000000 이하의 정수이다.

N>1N > 1이면 셋째 줄에 사거리 N−1N-1개가 같은 순서로 주어진다. 첫 사거리는 욱제의 것이고, 가장 오른쪽 사람은 제외된다. 각 사거리는 00 이상 10000001000000 이하의 정수이다. N=1N = 1이면 셋째 줄은 주어지지 않는다.

출력

마지막 사람이 수류탄을 받을 수 있으면 권병장님, 중대장님이 찾으십니다를 출력한다. 그렇지 않으면 엄마 나 전역 늦어질 것 같아를 출력한다. 각 출력은 한 줄이며 마지막에 줄 바꿈을 포함한다.

예제2

  1. 예제 1

    입력
    5
    0 5 10 15 100
    10 5 6 100
    
    예상 출력
    권병장님, 중대장님이 찾으십니다
    
  2. 예제 2

    입력
    5
    0 5 10 15 100
    10 5 6 0
    
    예상 출력
    엄마 나 전역 늦어질 것 같아