You are the second person Tadalin was promoted. You have seen Ginara upset for a long time, but now the Coplu sector is facing a powerful enemy ------ Imoen, a fallen Sarnagar. Aranak sends your troops to a fortress in Tanzanis to stop Imoen's special forces-the ghost. Everything went well originally, but the enemy suddenly started using tactical nuclear missile, which seriously affected your plan. After all, no troops can withstand a nuclear bomb. Fortunately, Archbishop Artanis of the Protoss agreed to provide you with Zap Technology, which gave the battlefield a glimmer of hope. You will use the Zap to send N troops to the battlefield.
According to the information sent back by your adjutant, we found that there is a safe window period for the enemy's nuclear missile strike, and this window period shows a periodicity with a period of H hours, that is, from time L to R in every H hours is safe .Faced with this situation, you should be very happy, but you find that the authority of the Zap system is not in your hands, which means that troops may arrive when you don't want to. According to the wire report, your i-th troop will arrive ai+H hours after the i-1th troop arrives (the first troop will arrive at the ai-th hour as planned). You understand that if you let the troops arrive in this situation, you will probably have to regroup your troops. Fortunately, you can use the starry sky acceleration technology, which can make the troops arrive one hour earlier, so that you may be able to regroup fewer troops.
Commander, it's time to make a decision. Please find the maximum number of surviving troops.
输入描述:
In the first line of the input data, four integer numbers will be given, N, H, L, R, (1≤N≤200000, 3≤H≤200, 0≤L≤R<H) respectively represent the number of troops , The period of the security window, the left end of the security window, and the right end of the security window.
The second line gives N integer numbers separated by spaces, where the i-th number represents ai. (1≤ai<H) is the result of your i-th troop minus H according to the planned arriving time.
输出描述:
Output an integer number, indicating the maximum number of troops that can survive.
示例1
输入
复制
7 24 21 23
16 17 14 20 20 11 22