방송 탑

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

요약
높이 H인 탑을 건물들 사이 어디에나 세울 수 있을 때, 서쪽 건물이 신호를 받으려면 그 사이에 더 높은 건물이 없어야 한다. 신호를 받는 건물 수의 최댓값을 구한다.
난이도

보통10점 중 5점

유형
스택, 배열
정답자
아직 제출이 없습니다

문제

도시 X에는 건물 NN개가 서쪽에서 동쪽으로 한 줄로 서 있다. 서쪽 끝 건물이 1번이고 동쪽 끝 건물이 NN번이다. 각 건물의 높이는 정수 h1,h2,…,hNh_1, h_2, \dots, h_N이고, 높이가 같은 건물은 없다. 시는 이 줄에 방송 탑 하나를 세우려고 한다. 탑은 1번 건물의 서쪽, 이웃한 두 건물 사이, NN번 건물의 동쪽 중 아무 곳에나 세울 수 있다. 탑의 높이는 HH이고, HH는 모든 건물의 높이와 다르다.

설계가 특이해서 탑은 서쪽으로만 신호를 보낸다. 신호는 땅과 평행하게 나아가는 수평 광선이고, 탑의 몸통 전체, 즉 꼭대기부터 바닥까지에서 나온다. 그래서 폭이 탑의 높이와 같은 광선 띠가 서쪽으로 뻗어 나간다고 보면 된다. 광선은 건물에 닿으면 그 자리에서 멈춘다. 각 건물은 옥상에 수신기가 있고, 광선이 하나라도 수신기에 닿으면 그 건물은 메시지를 받는다.

다시 말해 ii번 건물이 메시지를 받는 것은 다음 세 조건이 모두 성립할 때다. ii번 건물이 탑의 서쪽에 있고, hih_i가 탑의 높이보다 크지 않고, ii번 건물과 탑 사이에 있는 건물 jj (j>ij > i) 중에 ii번 건물보다 높은 건물이 없다.

위 그림에서 메시지를 받는 건물은 2, 5, 6, 9번이다.

건물의 높이와 탑의 높이가 주어진다. 메시지를 받는 건물이 가장 많아지는 위치에 탑을 세웠을 때, 메시지를 받는 건물의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 건물의 개수 NN과 탑의 높이 HH가 공백을 두고 주어진다.

둘째 줄에 건물 NN개의 높이가 1번 건물부터 NN번 건물까지 순서대로 공백을 두고 주어진다.

출력

탑을 가장 좋은 위치에 세웠을 때 메시지를 받는 건물의 최대 개수를 한 줄에 출력한다.

제한

  • 1≤N≤10000001 \le N \le 1000000
  • 1≤hi≤1091 \le h_i \le 10^9, 1≤H≤1091 \le H \le 10^9
  • 건물의 높이는 모두 서로 다르고, HH는 어떤 hih_i와도 같지 않다

설명

첫 번째 예제에서는 8번 건물과 9번 건물 사이에 탑을 세우는 것이 가장 좋다. 이때 2, 5, 6, 7, 8번 건물이 메시지를 받는다.

예제4

  1. 예제 1

    입력
    12 180
    200 170 130 90 150 140 40 30 100 160 50 110
    
    예상 출력
    5
    
  2. 예제 2

    입력
    1 10
    3
    
    예상 출력
    1
    
  3. 예제 3

    입력
    1 5
    7
    
    예상 출력
    0
    
  4. 예제 4

    입력
    5 100
    1 2 3 4 5
    
    예상 출력
    1