本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1362. Mountain Ranges


Description

Famous for its mountain ranges, Nlogonia attracts millions of tourists every year. The government has a dedicated budget for continuous maintenance of the hiking trails spread across the country and most of them are  lled with scenic viewpoints, accessible through wooden walkways and stairs.

Currently on a trip through Nlogonia and with hopes of going back home with lots of breath-taking pictures, Lola and her husband want to visit as many viewpoints as possible. They plan to hike a different trail each day and explore its viewpoints. However, to avoid being exhausted at the end of the day, if moving from one viewpoint to the next requires going up more than \$X\$ meters they simply call it a day and go back to their hotel in order to get some rest. Fortunately, every hiking trail in Nlogonia is equipped with modern chairlifts, so the couple can start hiking the trail at any viewpoint they decide. Once the hiking begins the couple only moves towards the peak of the mountain.

To make sure she doesn't waste a day Lola only wants to hike on trails where she'll get to a reasonable number of viewpoints. Given the altitudes of the scenic viewpoints on a hiking trail, you must determine the maximum number of viewpoints that the couple can visit.

Input

The first line contains two integers \$N (1 \leq N \leq 1000)\$ and \$X (0 \leq X \leq 8848)\$, indicating respectively the number of scenic viewpoints on the hiking trail, and the maximum number of meters that Lola and her husband are willing to go up from one viewpoint to the next. The second line contains \$N\$ integers \$A_1, A_2,\ldots,A_N (1 \leq Ai \leq 8848\$ for \$i = 1, 2,\ldots,N)\$, where \$A_i\$ the altitude (in meters) of the \$i\$-th viewpoint. Viewpoints are given in the order they appear on the hiking trail and their altitudes are non-decreasing, that is, \$A_i \leq A_{i+1}\$ for \$i = 1, 2,\ldots N -1\$.

Output

Output a single line with an integer indicating the maximum number of scenic viewpoints that can be visited without going up more than \$X\$ meters from one viewpoint to the next, and considering that the journey can be started at any viewpoint.

Samples

Input Copy
9 2
3 14 15 92 653 5897 5897 5898 5900
Output
4
Input Copy
9 0
3 14 15 92 653 5897 5897 5898 5900
Output
2
Input Copy
9 8848
3 14 15 92 653 5897 5897 5898 5900
Output
9

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 64MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register