XKC , the captain of the basketball team , is directing a train of nn team members. He makes all members stand in a row , and numbers them 1 \cdots n1⋯n from left to right. 채 서 곤 은 농구 팀 의 주장 으로 n 명의 선수 에 대한 훈련 을 지도하 고 있다.그 는 모든 구성원 을 한 줄 로 만 들 고 왼쪽 에서 오른쪽으로 1 부터 레이 블 을 시작 했다. The ability of the ii-th person is w_iwi , and if there is a guy whose ability is not less than w_i+mwi+m stands on his right , he will become angry. It means that the jj-th person will make the ii-th person angry if j>ij>i and w_j \ge w_i+mwj≥wi+m. i. 개인의 능력 치 는 와 이 입 니 다. 오른쪽 에 와 이 + m 보다 작은 능력 이 있다 면 분노 할 것 입 니 다. We define the anger of the ii-th person as the number of people between him and the person , who makes him angry and the distance from him is the longest in those people. If there is no one who makes him angry , his anger is -1−1 . 우 리 는 i 개인의 분노 치 를 그 와 그 를 분노 하 게 하 는 사람들 사이 의 가장 긴 거리 로 정의 한다. 만약 그 를 기분 나 쁘 게 하 는 사람 이 없다 면 수출 - 1 Please calculate the anger of every team member . 모든 사람의 분노 치 를 계산 해 보 세 요. 이 문 제 는 각 구간 의 최대 치 를 선분 트 리 로 유지 한 후, 어떤 값 에 해당 하 는 답 을 조회 할 때 기본적으로 오른쪽 하위 트 리 부터 답 을 찾 을 수 있 습 니 다. 존재 한다 면 (욕심) 검색 은 해당 위치 색인 값 으로 돌아 갑 니 다. 예 를 들 어 샘플 3, 4, 5, 6, 2, 10 은 3 의 대응 답 을 조회 하려 면 뿌리 노드 부터 (뿌리 노드 가 전체 구간 의 최대 치 를 저장 했다: 10) 오른쪽 서브 트 리 ([4, 6] 구간) 의 최대 치 는 3 보다 작 지 않 은 것 을 발견 하고 직접 오른쪽으로 조회 한 다음 에 [5, 6] 구간 의 최대 치 는 3 보다 작 지 않 고 계속 오른쪽으로 조회 하여 답 을 찾 을 때 까지 한다.오른쪽 나무 에 합 리 적 인 답 이 있다 면 왼쪽 나무 에 이런 답 이 존재 하 더 라 도 조회 할 필요 가 없다. 문제 의 줄기 에서 가장 긴 거 리 를 요구 하기 때문에 항상 오른쪽 에서 왼쪽으로 찾 을 수 있다.
