Clasa din care faceţi parte merge în excursie! Principalul obiectiv este Lacul Roşu, o locaţie deosebit de frumoasă. Pentru a vă bucura cât mai mult de peisaj toţi elevii se vor plimba cu barca pe lac. Bărcile sunt de maxim două persoane şi au restricţiile următoare:

• greutatea totală suportată de o barcă este C;
• dacă în barcă se aşază două persoane, atunci diferența în modul dintre greutățile acestora trebuie să fie maxim B, în caz contrar barca nu este balansată și riscă să se răstoarne.

Dacă o singură persoană se aşază în barcă, nu se aplică restricția a doua.

Cerința

Care este numărul minim de bărci necesare pentru a putea plimba toţi elevii în condiţii de siguranţă?

Date de intrare

Fișierul de intrare barci.in conţine pe prima linie trei numere naturale separate prin spaţiu: N, C și B, reprezentând numărul de elevi, capacitatea maximă a unei bărci şi respectiv diferenţa maximă dintre greutatea a două persoane care se pot aşeza în aceeaşi barcă. Pe a doua linie se află N numere naturale separate prin spaţiu w[i] (1 ≤ i ≤ N), reprezentând greutăţile celor N elevi.

Date de ieșire

Fișierul de ieșire barci.out va conţine o singură linie pe care va fi scris numărul minim de bărci necesare.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ w[i] ≤ C ≤ 1 000 000 000, pentru 1 ≤ i ≤ N
• 0 ≤ B ≤ 1 000 000 000
• Pentru teste în valoare de 30 de puncte, N ≤ 10
• Pentru teste în valoare de 60 de puncte, N ≤ 1000

#include <bits/stdc++.h>
using namespace std;

ifstream in("barci.in");
ofstream out("barci.out");

int n, wmax, wmin, w[100001], used[100001];

struct unom {
    int previous, next, weight;
} people[100001];

bool cmp(unom a, unom b) {
    return a.weight >  b.weight;
}

void deletePair(int &pos) {
    people[people[pos].previous].next = people[pos].next;
    people[people[pos].next].previous = people[pos].previous;
    pos = people[pos].next;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    in >> n >> wmax >> wmin;
    for(int i = 1; i <= n; ++i) {
        in >> w[i];
        people[i].previous = i - 1;
        people[i].next = i + 1;
    }

    sort(w + 1, w + 1 + n, greater<int>());
    for(int i = 1; i <= n; ++i) {
        people[i].weight = w[i];
    }

    int pos = n;
    while(pos && people[1].weight + people[pos].weight <= wmax) {
        --pos;
    }

    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        if(used[i] == 0) {
            ++cnt;
            used[i] = 1;
            if(pos == i) {
                pos = people[pos].next;
            }

            while(people[pos].previous > i && people[i].weight + people[people[pos].previous].weight <= wmax) {
                pos = people[pos].previous;
            }

            if(used[pos] == 0 && pos <= n && i >= 1 && abs(people[i].weight - people[pos].weight) <= wmin && people[i].weight + people[pos].weight <= wmax) {
                used[pos] = 1;
                deletePair(pos);
            }
        }
    }
    out << cnt;
    return 0;
}