AtCoder Grand Contest 009 - Division into Two

There is a set consisting of N distinct integers. The i-th smallest element in this set is S_i. We want to divide this set into two sets, X and Y, such that:

* The absolute difference of any two distinct elements in X is A or greater.
* The absolute difference of any two distinct elements in Y is B or greater.



How many ways are there to perform such division, modulo 10^9 + 7? Note that one of X and Y may be empty.

Constraints

* All input values are integers.
* 1 ≦ N ≦ 10^5
* 1 ≦ A , B ≦ 10^{18}
* 0 ≦ S_i ≦ 10^{18}(1 ≦ i ≦ N)
* S_i < S_{i+1}(1 ≦ i ≦ N - 1)

Input

The input is given from Standard Input in the following format:


N A B
S_1
:
S_N


Output

Print the number of the different divisions under the conditions, modulo 10^9 + 7.

Examples

Input

5 3 7
1
3
6
9
12


Output

5


Input

7 5 3
0
2
4
7
8
11
15


Output

4


Input

8 2 9
3
4
5
13
15
22
26
32


Output

13


Input

3 3 4
5
6
7


Output

0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
INF = 10 ** 18 + 100
(N, A, B) = map(int, input().split())
S = [-INF] + [int(x) for x in sys.stdin.read().split()]
MOD = 10 ** 9 + 7
dpX = [0] * (N + 1)
dpY = [0] * (N + 1)
dpX[0] = 1
dpY[0] = 1
dpX_cum = [1] * (N + 1) + [0]
dpY_cum = [1] * (N + 1) + [0]
dpX_left = 0
dpY_left = 0
for (n, x) in enumerate(S[2:], 2):
	iA = bisect_right(S, x - A)
	iB = bisect_right(S, x - B)
	xy = dpY_cum[iB - 1] - dpY_cum[dpY_left - 1] if iB >= dpY_left else 0
	yx = dpX_cum[iA - 1] - dpX_cum[dpX_left - 1] if iA >= dpX_left else 0
	if iA != n:
		dpY_left = n - 1
	if iB != n:
		dpX_left = n - 1
	dpX[n - 1] = xy
	dpX_cum[n - 1] = (dpX_cum[n - 2] + xy) % MOD
	dpX_cum[n] = dpX_cum[n - 1]
	dpY[n - 1] = yx
	dpY_cum[n - 1] = (dpY_cum[n - 2] + yx) % MOD
	dpY_cum[n] = dpY_cum[n - 1]
answer = dpX_cum[N - 1] - dpX_cum[dpX_left - 1]
answer += dpY_cum[N - 1] - dpY_cum[dpY_left - 1]
answer %= MOD
print(answer)


import sys
from bisect import bisect

class BinaryIndexedTree:

	def __init__(self, n, MOD):
		self.size = n + 1
		self.tree = [0] * (n + 2)
		self.MOD = MOD

	def sum(self, i):
		i += 1
		s = 0
		while i > 0:
			s = (s + self.tree[i]) % self.MOD
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] = (self.tree[i] + x) % self.MOD
			i += i & -i

	def debug_print(self, limit=None):
		if limit is None:
			limit = self.size
		acc = [0] + [self.sum(i) for i in range(limit)]
		aaa = [a1 - a0 for (a0, a1) in zip(acc, acc[1:])]
		print(aaa)

def solve(n, a, b, sss):
	if a > b:
		(a, b) = (b, a)
	for (s0, s2) in zip(sss, sss[2:]):
		if s2 - s0 < a:
			return 0
	MOD = 10 ** 9 + 7
	bit = BinaryIndexedTree(n, MOD)
	bit.add(0, 1)
	bit.add(1, 1)
	sss.insert(0, -10 ** 18 - 1)
	pos = 0
	for i in range(1, n):
		s0 = sss[i]
		s1 = sss[i + 1]
		lim = bisect(sss, s1 - b) - 1
		if lim >= pos:
			bit.add(i + 1, bit.sum(lim))
		if s1 - s0 < a:
			bit.add(i - 1, -bit.sum(i - 1))
			pos = i - 1
	return bit.sum(n)
(n, a, b, *sss) = map(int, sys.stdin.read().split())
print(solve(n, a, b, sss))


import sys
from sys import stdin
from collections import deque

def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	ret = 0
	x = a
	while x > 0:
		ret += bit[x]
		x -= x & -1 * x
	return ret
(N, A, B) = map(int, stdin.readline().split())
mod = 10 ** 9 + 7
BITA = [0] * (N + 3)
BITB = [0] * (N + 3)
bitadd(1, 1, BITA)
aq = deque([])
bq = deque([])
Slis = [float('-inf')]
for loop in range(N):
	S = int(stdin.readline())
	aq.append((S, loop + 2))
	bq.append((S, loop + 2))
	while aq[0][0] <= S - A:
		aq.popleft()
	while bq[0][0] <= S - B:
		bq.popleft()
	Aans = bitsum(bq[0][1] - 1, BITB)
	Bans = bitsum(aq[0][1] - 1, BITA)
	if Aans < 0:
		Aans = 0
	if Bans < 0:
		Bans = 0
	Aans %= mod
	Bans %= mod
	if S - Slis[-1] >= B:
		bitadd(loop + 1, Aans, BITA)
	else:
		nowsum = bitsum(N + 2, BITA)
		bitadd(1, -1 * nowsum, BITA)
		bitadd(loop + 1, Aans, BITA)
	if S - Slis[-1] >= A:
		bitadd(loop + 1, Bans, BITB)
	else:
		nowsum = bitsum(N + 2, BITB)
		bitadd(1, -1 * nowsum, BITB)
		bitadd(loop + 1, Bans, BITB)
	Slis.append(S)
	if len(Slis) >= 3 and Slis[-1] - Slis[-3] < min(A, B):
		print(0)
		sys.exit()
print((bitsum(N + 2, BITA) + bitsum(N + 2, BITB)) % mod)


import sys
readline = sys.stdin.readline

class Lazysegtree:

	def __init__(self, A, intv, initialize=True, segf=min):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.intv = intv
		self.segf = segf
		self.lazy = [None] * (2 * self.N0)
		if initialize:
			self.data = [intv] * self.N0 + A + [intv] * (self.N0 - self.N)
			for i in range(self.N0 - 1, -1, -1):
				self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [intv] * (2 * self.N0)

	def _ascend(self, k):
		k = k >> 1
		c = k.bit_length()
		for j in range(c):
			idx = k >> j
			self.data[idx] = self.segf(self.data[2 * idx], self.data[2 * idx + 1])

	def _descend(self, k):
		k = k >> 1
		idx = 1
		c = k.bit_length()
		for j in range(1, c + 1):
			idx = k >> c - j
			if self.lazy[idx] is None:
				continue
			self.data[2 * idx] = self.data[2 * idx + 1] = self.lazy[2 * idx] = self.lazy[2 * idx + 1] = self.lazy[idx]
			self.lazy[idx] = None

	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		self._descend(L // (L & -L))
		self._descend(R // (R & -R) - 1)
		s = self.intv
		while L < R:
			if R & 1:
				R -= 1
				s = self.segf(s, self.data[R])
			if L & 1:
				s = self.segf(s, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def update(self, l, r, x):
		L = l + self.N0
		R = r + self.N0
		Li = L // (L & -L)
		Ri = R // (R & -R)
		self._descend(Li)
		self._descend(Ri - 1)
		while L < R:
			if R & 1:
				R -= 1
				self.data[R] = x
				self.lazy[R] = x
			if L & 1:
				self.data[L] = x
				self.lazy[L] = x
				L += 1
			L >>= 1
			R >>= 1
		self._ascend(Li)
		self._ascend(Ri - 1)
inf = 10 ** 19
(N, A, B) = map(int, readline().split())
S = [-inf] + [int(readline()) for _ in range(N)]
MOD = 10 ** 9 + 7
dpa = Lazysegtree([1] + [0] * N, 0, initialize=True, segf=lambda x, y: (x + y) % MOD)
dpb = Lazysegtree([1] + [0] * N, 0, initialize=True, segf=lambda x, y: (x + y) % MOD)
for i in range(1, N + 1):
	oka = 0
	ng = i
	while abs(oka - ng) > 1:
		med = (oka + ng) // 2
		if S[i] - S[med] >= A:
			oka = med
		else:
			ng = med
	okb = 0
	ng = i
	while abs(okb - ng) > 1:
		med = (okb + ng) // 2
		if S[i] - S[med] >= B:
			okb = med
		else:
			ng = med
	tb = dpa.query(0, okb + 1)
	dpa.update(i - 1, i, dpb.query(0, oka + 1))
	dpb.update(i - 1, i, tb)
	if S[i] - S[i - 1] < A:
		dpa.update(0, i - 1, 0)
	if S[i] - S[i - 1] < B:
		dpb.update(0, i - 1, 0)
print((dpa.query(0, N + 1) + dpb.query(0, N + 1)) % MOD)


mod = 10 ** 9 + 7
import bisect, sys
input = sys.stdin.readline
(N, A, B) = map(int, input().split())
S = [int(input()) for i in range(N)]
datax = [i for i in range(N + 1)]
datay = [i for i in range(N + 1)]
for i in range(2, N + 1):
	if S[i - 1] - S[i - 2] >= A:
		datax[i] = datax[i - 1]
	if S[i - 1] - S[i - 2] >= B:
		datay[i] = datay[i - 1]
dpx = [0] * (N + 1)
imosx = [0] * (N + 1)
dpy = [0] * (N + 1)
imosy = [0] * (N + 1)
dpx[0] = 1
dpy[0] = 1
imosx[0] = 1
imosy[0] = 1
for i in range(1, N):
	id = bisect.bisect_right(S, S[i] - B)
	R = min(id + 1, i)
	L = datax[i]
	if R >= L:
		dpx[i] = (imosy[R - 1] - imosy[L - 2] * (L >= 2)) % mod
		imosx[i] = (imosx[i - 1] + dpx[i]) % mod
	else:
		imosx[i] = imosx[i - 1]
	id = bisect.bisect_right(S, S[i] - A)
	R = min(id + 1, i)
	L = datay[i]
	if R >= L:
		dpy[i] = (imosx[R - 1] - imosx[L - 2] * (L >= 2)) % mod
		imosy[i] = (imosy[i - 1] + dpy[i]) % mod
	else:
		imosy[i] = imosy[i - 1]
i = N
R = i
L = datax[i]
if R >= L:
	dpx[i] = (imosy[R - 1] - imosy[L - 2] * (L >= 2)) % mod
	imosx[i] = (imosx[i - 1] + dpx[i]) % mod
else:
	imosx[i] = imosx[i - 1]
R = i
L = datay[i]
if R >= L:
	dpy[i] = (imosx[R - 1] - imosx[L - 2] * (L >= 2)) % mod
	imosy[i] = (imosy[i - 1] + dpy[i]) % mod
else:
	imosy[i] = imosy[i - 1]
print((dpx[-1] + dpy[-1]) % mod)


from bisect import bisect_left
(N, A, B) = map(int, input().split())
(inf, mod) = (float('inf'), 10 ** 9 + 7)
S = [int(input()) for i in range(N)]
St_A = [0] * N
St_B = [0] * N
(J_A, J_B) = ([0], [0])
for i in range(N):
	St_A[i] = bisect_left(S, S[i] + A) - 1
	St_B[i] = bisect_left(S, S[i] + B) - 1
	J_A.append(J_A[-1] + int(St_A[i] != i))
	J_B.append(J_B[-1] + int(St_B[i] != i))
dp_A = [0] * N
dp_B = [0] * N
(dp_A[-1], dp_B[-1]) = (1, 1)
for i in range(N - 1)[::-1]:
	if St_A[i] == i:
		dp_A[i] = (dp_A[i + 1] + dp_B[i + 1]) % mod
	elif J_B[St_A[i]] - J_B[i + 1] == 0:
		dp_A[i] = dp_B[St_A[i]]
	else:
		dp_A[i] = 0
	if St_B[i] == i:
		dp_B[i] = (dp_A[i + 1] + dp_B[i + 1]) % mod
	elif J_A[St_B[i]] - J_A[i + 1] == 0:
		dp_B[i] = dp_A[St_B[i]]
	else:
		dp_B[i] = 0
print((dp_A[0] + dp_B[0]) % mod)