As you must know, the maximum clique problem in an arbitrary graph is NP-hard. Nevertheless, for some graphs of specific kinds it can be solved effectively.

Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques.

Let's define a divisibility graph for a set of positive integers A = {a_1, a_2, ..., a_{n}} as follows. The vertices of the given graph are numbers from set A, and two numbers a_{i} and a_{j} (i ≠ j) are connected by an edge if and only if either a_{i} is divisible by a_{j}, or a_{j} is divisible by a_{i}.

You are given a set of non-negative integers A. Determine the size of a maximum clique in a divisibility graph for set A.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6), that sets the size of set A.

The second line contains n distinct positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — elements of subset A. The numbers in the line follow in the ascending order.


-----Output-----

Print a single number — the maximum size of a clique in a divisibility graph for set A.


-----Examples-----
Input
8
3 4 6 8 10 18 21 24

Output
3



-----Note-----

In the first sample test a clique of size 3 is, for example, a subset of vertexes {3, 6, 18}. A clique of a larger size doesn't exist in this graph.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
n = int(input())
base = list(map(int, input().split()))
stock = [0 for k in range(int(1000000.0 + 1))]
for zbi in base:
	stock[zbi] = 1
t = base[-1]
for k in range(2, n + 1):
	num = base[n - k]
	for i in range(2, t // num + 1):
		if stock[i * num] >= 1:
			stock[num] = max(stock[num], 1 + stock[i * num])
print(max(stock))


def clique_in_the_divisibility_graph(n, a):
	MAX = 10 ** 6 + 1
	L = [0] * MAX
	for v in a:
		L[v] = 1
	for i in range(n):
		if L[a[i]]:
			for x in range(a[i] * 2, MAX, a[i]):
				if L[x]:
					L[x] = max(L[x], L[a[i]] + 1)
	return max(L)

def __starting_point():
	n = int(input())
	a = list(map(int, input().split()))
	result = clique_in_the_divisibility_graph(n, a)
	print(result)
__starting_point()


import os
import sys
from io import BytesIO, IOBase

class FastO:

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(fd, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda b: stream.write(b.encode())

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
(sys.stdout, cout) = (FastO(), ostream())
(numbers, num, sign) = ([], 0, True)
for char in os.read(0, os.fstat(0).st_size):
	if char >= 48:
		num = num * 10 + char - 48
	elif char == 45:
		sign = False
	elif char != 13:
		numbers.append(num if sign else -num)
		(num, sign) = (0, True)
if char >= 48:
	numbers.append(num if sign else -num)
getnum = iter(numbers).__next__
n = getnum()
dp = [0] * (10 ** 6 + 1)
for _ in range(n):
	dp[getnum()] = 1
for i in reversed(range(10 ** 6 + 1)):
	dp[i] = max((dp[x] + 1 for x in range(2 * i, 10 ** 6 + 1, i) if dp[x]), default=1) if dp[i] else 0
cout << max(dp)


n = int(input())
a = [int(v) for v in input().split()]
MAX = 10 ** 6 + 1
L = [0] * MAX
for v in a:
	L[v] = 1
for i in range(n):
	if L[a[i]]:
		for x in range(a[i] * 2, MAX, a[i]):
			if L[x]:
				L[x] = max(L[x], L[a[i]] + 1)
print(max(L))


N = int(input())
List = [int(x) for x in input().split()]
MAX = 1000001
dp = [0] * MAX
for i in List:
	dp[i] += 1
for i in range(N):
	if dp[List[i]]:
		for j in range(List[i] * 2, MAX, List[i]):
			if dp[j]:
				dp[j] = max(dp[j], dp[List[i]] + 1)
print(max(dp))


for _ in range(1):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0] * (10 ** 6 + 1)
	for i in l:
		dp[i] = 1
	for i in l:
		if dp[i]:
			for x in range(i * 2, 10 ** 6 + 1, i):
				if dp[x]:
					dp[x] = max(dp[x], dp[i] + 1)
	print(max(dp))


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * (10 ** 6 + 1)
for i in range(n):
	dp[a[i]] = 1
for i in range(n):
	if dp[a[i]] > 0:
		for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
			if dp[j] > 0:
				dp[j] = max(dp[j], dp[a[i]] + 1)
print(max(dp))


R = lambda : map(int, input().split())
n = int(input())
dp = [0] * (10 ** 6 + 1)
for x in R():
	dp[x] = 1
for i in range(10 ** 6, -1, -1):
	if dp[i]:
		for x in range(i + i, 10 ** 6 + 1, i):
			if dp[x]:
				dp[i] = max(dp[i], dp[x] + 1)
print(max(dp))


n = int(input())
a = list(map(int, input().split()))
l = [0] * (10 ** 6 + 1)
for aa in a:
	l[aa] = 1
for i in range(n):
	if l[a[i]]:
		for x in range(a[i] * 2, 10 ** 6 + 1, a[i]):
			if l[x]:
				l[x] = max(l[x], l[a[i]] + 1)
print(max(l))