2024_帕鲁任务分配_1523_牛客题霸

小明有个帕鲁排成一排进行工作，每个帕鲁都有一个容忍度。现在共有个任务需要分配给这些帕鲁，每个帕鲁至少要分配到一个任务。如果某个帕鲁的工作量与其相邻帕鲁的工作量之差大于其容忍度，则该帕鲁会生病。今天第个帕鲁偷吃了蛋糕，为了惩罚它，小明希望尽量给这个帕鲁分配最多的任务。请计算在保证所有帕鲁都不生病的情况下，第个帕鲁能承担的最大任务量。

输入描述:

第一行包含三个整数 , , ，分别表示帕鲁的数量、任务的总数和需要惩罚的帕鲁编号（编号从 开始）。第二行包含 个整数，表示每个帕鲁的容忍度 。

输出描述:

输出一个整数，表示在保证所有帕鲁都不生病的情况下，第 个帕鲁能承担的最大任务量

示例1

输入

3 10 2
1 2 1

输出

说明

有  个帕鲁，总任务数为 ，需要惩罚第  个帕鲁。
容忍度分别为：, , 。
为了保证帕鲁不生病，任务分配可能为：[3, 4, 3]。
第  个帕鲁的最大任务量为 。