Description

Suppose that N apartments are placed in a row. In some apartments among these, 4g base station is installed at the rooftop. As demand for 5g increases due to the advancement of technology, you want to replace 4g base station with 5g base station. But, since the coverage of 5g base station is smaller than 4g base station, some apartments cannot receive signal after replacing 4g base station with 5g base station.

For example, assume that 11 apartments are places in a row, and 4g base station is installed at the rooftop of [4, 11]-th apartment. If these 4g base stations are replaced with 5g base station with coverage of length 1, signal is not delivered to all apartments. (When the coverage is length W, signal is delivered within the range of W from both side of apartment where base station is installed.)

  • At the beginning, apartments at the position of 1, 2, 6, 7, 8, and 9 cannot receive the signal.

기지국설치1_pvskxt.png

  • If the 5g base station is installed at the apartments of position 1, 7, and 9, signal is delivered to all apartments.

기지국설치2_kml0pb.png

  • In the case of installing 5g base station at more than 3 apartments, signal is delivered to all apartments.

기지국설치3_xhv7r3.png

At this point, you want to deliver the signal to all apartments by installing the minimum number of base stations. In the above example, installing at least 3 base stations is required to deliver signal to all apartments.

Given the number of apartments N, an 1-dimensional array stations containing the position of apartments where 4g base station is installed, and the coverage of base station W as parameters, write a function solution to return the minimum number of base stations to be installed additionally to deliver the signal for all apartments.

Constraints
  • N : natural number less than 200,000,000.
  • Length of stations : natural number less than 10,000.
  • stations is sorted in ascending order, and its elements are natural number less than N.
  • W : natural number less than 10,000.

Examples
N stations W answer
11 [4, 11] 1 3
16 [9] 2 3

Example #1
This is the same with the example in the problem statement.

Example #2

  • At the initial stage, signal is not delivered to the apartments of position 1~6 and 12~16.

기지국설치4_nqfrmm.png

  • When installing the base station at the apartments of position 3, 6, and 14, signal is delivered to all apartments.

기지국설치5_zh4ebk.png

Result Stop
Result of [Run] or [Submit] will be displayed here