B. Three-level Laser

Codeforces

IDCF956B

Time1000ms

Memory256MB

Difficulty—

binary searchgreedytwo pointers

An atom of element X can exist in _n_ distinct states with energies _E_1 < _E_2 < ... < _E__n_. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified description of the scheme. Three distinct states _i_, _j_ and _k_ are selected, where _i_ < _j_ < _k_. After that the following process happens: 1. initially the atom is in the state _i_, 2. we spend _E__k_ - _E__i_ energy to put the atom in the state _k_, 3. the atom emits a photon with useful energy _E__k_ - _E__j_ and changes its state to the state _j_, 4. the atom spontaneously changes its state to the state _i_, losing energy _E__j_ - _E__i_, 5. the process repeats from step 1. Let's define the energy conversion efficiency as , i. e. the ration between the useful energy of the photon and spent energy. Due to some limitations, Arkady can only choose such three states that _E__k_ - _E__i_ ≤ _U_. Help Arkady to find such the maximum possible energy conversion efficiency within the above constraints. ## Input The first line contains two integers _n_ and _U_ (3 ≤ _n_ ≤ 105, 1 ≤ _U_ ≤ 109) — the number of states and the maximum possible difference between _E__k_ and _E__i_. The second line contains a sequence of integers _E_1, _E_2, ..., _E__n_ (1 ≤ _E_1 < _E_2... < _E__n_ ≤ 109). It is guaranteed that all _E__i_ are given in increasing order. ## Output If it is not possible to choose three states that satisfy all constraints, print _\-1_. Otherwise, print one real number η — the maximum possible energy conversion efficiency. Your answer is considered correct its absolute or relative error does not exceed 10 - 9. Formally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if . [samples] ## Note In the first example choose states 1, 2 and 3, so that the energy conversion efficiency becomes equal to . In the second example choose states 4, 5 and 9, so that the energy conversion efficiency becomes equal to .

Samples

Input #1

4 4
1 3 5 7

Output #1

0.5

Input #2

10 8
10 13 15 16 17 19 20 22 24 25

Output #2

0.875

Input #3

3 1
2 5 10

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Three-level Laser",
    "description": {
      "content": "An atom of element X can exist in _n_ distinct states with energies _E_1 < _E_2 < ... < _E__n_. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified descript",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF956B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An atom of element X can exist in _n_ distinct states with energies _E_1 < _E_2 < ... < _E__n_. Arkady wants to build a laser on this element, using a three-level scheme. Here is a simplified descript...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments