Пиріг за пиріг

Бессі та Елсі спекли по $n$ пирогів кожна. Кожен із $2n$ пирогів має значення смаковитості, присвоєне Бессі, і, можливо, інше значення смаковитості, присвоєне Елсі.

Бессі збирається подарувати один зі своїх пирогів Елсі. Якщо Елсі отримує пиріг від Бессі, вона вважає себе зобов'язаною у відповідь подарувати Бессі один зі своїх пирогів. Щоб не здатися ні скупою, ні надто щедрою, Елсі намагатиметься обрати пиріг, який, на її думку, не менш смачний, ніж отриманий нею пиріг, але не більш ніж на $d$ одиниць смачніший. Такого пирога може не знайтися, і в цьому випадку Елсі візьме собі псевдонім і вирушить у вигнання до Японії.

Якщо Елсі все ж віддає Бессі пиріг у відповідь, Бессі аналогічним чином намагатиметься подарувати Елсі пиріг, який, на її думку, не менш смачний, але не більш ніж на $d$ одиниць смачніший за пиріг, щойно отриманий від Елсі. Якщо це неможливо, Бессі також вирушить у вигнання. В іншому випадку вона віддає Елсі обраний пиріг. Цей процес триває доти, доки або одна з корів не буде вигнана, що призведе до нещасливого результату, або одна з корів не отримає пиріг, який вона вважає таким, що має значення смаковитості $0$. В останньому випадку обмін подарунками закінчується, і обидві корови щасливі.

Зверніть увагу, що жоден пиріг не може бути подарований більше одного разу, і жодна з корів не може повернути пиріг, який вона раніше отримала.

Для кожного з $n$ пирогів, які Бессі може обрати як свій перший подарунок Елсі, визначте мінімальну кількість пирогів, які можуть бути подаровані в результаті такого обміну до того, як корови стануть щасливими.