페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5814

짝을 찾아서 2s 1024MB

문제

길이 N의 서로 다른 값을 가진 수열 a_i가 있다. 여기에 임의의 구간 l, r(1 \le l \le r \le N) a_l, ..., a_r에 각각 k만큼 더한다. 이 작업을 한 번 수행하였을 때, i \lt j 이면서 a_i \ge a_j를 만족하는 (i,j) 쌍의 최대 개수를 출력하라.

(제약 조건)

1 \le N\le100,000

-1,000,000,000 \le k \le 1,000,000,000

-1,000,000,000 \le a_i \le 1,000,000,000


입력

첫 줄에 수열의 길이 N과 임의의 구간에 더하는 값 k가 주어진다.

그 다음 줄에 길이 N의 수열 a_i가 공백을 구분으로 주어진다.


출력

위 조건에 만족하는 쌍의 최대를 출력한다.


부분문제

번호 점수 조건
#15점

N\le10

#210점

N\le100

#315점

N\le5,000

#420점

k=0

#550점

추가 제약 조건 없음.


예제 #1

3 2
1 2 3
2

예제 #2

4 -2
1 2 3 4
3
로그인해야 코드를 작성할 수 있어요.