(1.)Description

艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为L，平均分为L段，从左到右编号为1，2，……， L。木板的上侧为锯齿形，高度为整数，第i段的高度为Ai，Ai>=2（如右图所示）。这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实 用性的艺术品是他设计的理念。根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，“对，就把它做成梳子！”他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖 掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉），使得剩下的木板构成“规则锯齿形”（这样才好梳头）。 例如，对上图，挖掉第3、7、8列最上面的1个格子和第5列最上面的2个格子后，剩下的区域就构成“规则锯齿形”（如右图所示）。一个锯齿形称为“规则锯 齿形”当且仅当它的上边界（右图中红色曲线所示）的拐点序列不包含“010”或者“101”。右图中红色曲线的拐点序列为：“011001”，（其中0代 表左拐，1代表右拐），沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。

Input

多组测试数据 文件第一行为整数L，其中4<=L<=100000，表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL，其中1<=108，表示第i段的高度。 以0为结束标志.

Output

对于每组测试数据 仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。

Sample Input

9
4 4 6 5 4 2 3 3 5
0

Sample Output

3

(2)

Description

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正 整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥 的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙 已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

Input

输入包含多组数据，每组数据第一行有一个正整数L（1 <= L <= 20000），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。输入以一个0结束。

Output

对每组数据输出一行，这一行只包括一个整数，表示青蛙过河最少需要踩到的石子数。

Sample Input

10
2 3 5
2 3 5 6 7
10
5 5 1
1
0

Sample Output

2
0