Simon has an array a_1, a_2, ..., a_{n}, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:  there is integer j (l ≤ j ≤ r), such that all integers a_{l}, a_{l} + 1, ..., a_{r} are divisible by a_{j};  value r - l takes the maximum value among all pairs for which condition 1 is true; 

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5).

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6).


-----Output-----

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.


-----Examples-----
Input
5
4 6 9 3 6

Output
1 3
2 

Input
5
1 3 5 7 9

Output
1 4
1 

Input
5
2 3 5 7 11

Output
5 0
1 2 3 4 5 



-----Note-----

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

Source: codeforces | Difficulty: HARD
Tags: Sorting

Amortized analysis

Complete search

Mathematics

Data structures


Solutions:
n = int(input()) + 1
t = [1] + list(map(int, input().split())) + [1]
p = [True] * n
(s, q) = (0, list(range(1, n)))
for i in range(1, n):
	if p[i]:
		a = b = i
		d = t[i]
		if d == 1:
			(s, q) = (n - 2, [1])
			break
		while t[a - 1] % d == 0:
			a -= 1
		while t[b + 1] % d == 0:
			b += 1
			p[b] = False
		d = b - a
		if d > s:
			(s, q) = (d, [a])
		elif d == s != 0:
			q.append(a)
print(len(q), s)
print(' '.join(map(str, q)))


import math

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=9999999999999999999999999999999, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
n = int(input())
l = list(map(int, input().split()))
s2 = SegmentTree(l)
s1 = SegmentTree1(l)
s = 0
e = 0
d = dict()
d1 = dict()
ed = [] + l[::-1]
s3 = SegmentTree(ed)
s4 = SegmentTree1(ed)
d2 = dict()
while s < n:
	if s in d1:
		d1[s] = e - s - 1
	else:
		d1.update({s: e - s - 1})
	if e == n:
		e -= 1
		s += 1
	if s2.query(s, e) == s1.query(s, e):
		e += 1
	else:
		s += 1
	if s > e:
		e += 1
	if e > n - 1:
		e = n
if s in d1:
	d1[s] = e - s - 1
else:
	d1.update({s: e - s - 1})
e = 0
s = 0
while s < n:
	if s in d2:
		d2[n - 1 - s] = e - s - 1
	else:
		d2.update({n - 1 - s: e - s - 1})
	if e == n:
		e -= 1
		s += 1
	if s3.query(s, e) == s4.query(s, e):
		e += 1
	else:
		s += 1
	if s > e:
		e += 1
	if e > n - 1:
		e = n
if s in d2:
	d2[n - 1 - s] = e - s - 1
else:
	d2.update({n - 1 - s: e - s - 1})
ans = 0
for j in d1:
	if j in d2:
		if 0 <= j + d1[j] < n and 0 <= j - d2[j] < n and (0 <= j < n) and (s2.query(j, j + d1[j]) == s2.query(j - d2[j], j)):
			d1[j] += d2[j]
	ans = max(ans, d1[j])
for j in d2:
	ans = max(ans, d2[j])
s = 0
e = s + ans
w = []
while e < n:
	if s2.query(s, e) == s1.query(s, e):
		w.append(s + 1)
	s += 1
	e += 1
print(len(w), ans)
print(*w, sep=' ')


import math

def prob():
	n = int(input())
	n += 1
	l = [1]
	l += [int(x) for x in input().split()]
	l += [1]
	p = [True] * n
	s = 0
	q = [i for i in range(1, n)]
	for i in range(1, n):
		if p[i]:
			a = i
			b = i
			d = l[i]
			if d == 1:
				(s, q) = (n - 2, [1])
				break
			while l[a - 1] % d == 0:
				a -= 1
			while l[b + 1] % d == 0:
				b += 1
				p[b] = False
			d = b - a
			if d > s:
				(s, q) = (d, [a])
			elif d == s and s != 0:
				q.append(a)
	print(len(q), s)
	print(*q)
t = 1
for _ in range(0, t):
	prob()


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=9999999999999999999999999999999, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
n = int(input())
l = list(map(int, input().split()))
s2 = SegmentTree(l)
s1 = SegmentTree1(l)
s = 0
e = 0
d = dict()
d1 = dict()
ed = [] + l[::-1]
s3 = SegmentTree(ed)
s4 = SegmentTree1(ed)
d2 = dict()
while s < n:
	if s in d1:
		d1[s] = e - s - 1
	else:
		d1.update({s: e - s - 1})
	if e == n:
		e -= 1
		s += 1
	if s2.query(s, e) == s1.query(s, e):
		e += 1
	else:
		s += 1
	if s > e:
		e += 1
	if e > n - 1:
		e = n
if s in d1:
	d1[s] = e - s - 1
else:
	d1.update({s: e - s - 1})
e = 0
s = 0
while s < n:
	if s in d2:
		d2[n - 1 - s] = e - s - 1
	else:
		d2.update({n - 1 - s: e - s - 1})
	if e == n:
		e -= 1
		s += 1
	if s3.query(s, e) == s4.query(s, e):
		e += 1
	else:
		s += 1
	if s > e:
		e += 1
	if e > n - 1:
		e = n
if s in d2:
	d2[n - 1 - s] = e - s - 1
else:
	d2.update({n - 1 - s: e - s - 1})
ans = 0
for j in d1:
	if j in d2:
		if 0 <= j + d1[j] < n and 0 <= j - d2[j] < n and (0 <= j < n) and (s2.query(j, j + d1[j]) == s2.query(j - d2[j], j)):
			d1[j] += d2[j]
	ans = max(ans, d1[j])
for j in d2:
	ans = max(ans, d2[j])
s = 0
e = s + ans
w = []
while e < n:
	if s2.query(s, e) == s1.query(s, e):
		w.append(s + 1)
	s += 1
	e += 1
print(len(w), ans)
print(*w, sep=' ')