using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using System.Text; using static System.Math; using static Solve.Methods; using static Solve.Input; using static Solve.Output; using pii = Solve.Pair; using pll = Solve.Pair; using pli = Solve.Pair; using pil = Solve.Pair; using pss = Solve.Pair; using psi = Solve.Pair; using lint = System.Collections.Generic.List; using llong = System.Collections.Generic.List; using lstr = System.Collections.Generic.List; using llint = System.Collections.Generic.List>; using llstr = System.Collections.Generic.List>; using lllong = System.Collections.Generic.List>; using lii = System.Collections.Generic.List>; using lll = System.Collections.Generic.List>; using lli = System.Collections.Generic.List>; using lil = System.Collections.Generic.List>; using ll = System.Int64; namespace Solve { public class Solver { private int[] A; private lint[] B; public void Main() { const int max = 300001; int N = ReadInt; A = IntArray(N); var l = new lint[max]; for (int i = 0; i < max; i++) { l[i] = new lint(); } for (int i = 0; i < N; i++) { for (int j = 1; (long)j * j <= A[i]; j++) { int rem; var div = DivRem(A[i], j, out rem); if (rem != 0) continue; if (j != 1 && j * j != A[i]) l[div].Add(i); l[j].Add(i); } } B = l; memo = new int[N]; int ans = 1; for (int i = 0; i < N; i++) chmax(ref ans, dfs(i)); dout = memo.JoinSpace(); cout = ans; } private int[] memo; int dfs(int index) { // index 番目から始めたときの答え if (memo[index] != 0) { return memo[index]; } var idx = B[A[index]].BinarySearch(index + 1); if (idx < 0) idx = ~idx; int ans = 1; for (int i = idx; i < B[A[index]].Count; i++) { chmax(ref ans, 1 + dfs(B[A[index]][i])); } return memo[index] = ans; } // ReSharper disable UnusedMember.Local private const int MOD = (int) 1e9 + 7, INF = 1000000010; private const long LINF = 1000000000000000100; } // ライブラリ置き場ここから [DebuggerDisplay("Value = {" + nameof(_value) + "}")] public struct ModInt : IEquatable, IComparable { private long _value; public const int MOD = (int) 1e9 + 7; public static readonly ModInt Zero = new ModInt(0); public static readonly ModInt One = new ModInt(1); public ModInt(long value) { _value = value % MOD; } private ModInt(int value) { _value = value; } public int Value => (int) _value; public ModInt Invert => ModPow(this, MOD - 2); public static ModInt operator -(ModInt value) { value._value = MOD - value._value; return value; } public static ModInt operator +(ModInt left, ModInt right) { left._value += right._value; if (left._value >= MOD) left._value -= MOD; return left; } public static ModInt operator -(ModInt left, ModInt right) { left._value -= right._value; if (left._value < 0) left._value += MOD; return left; } public static ModInt operator *(ModInt left, ModInt right) { left._value = left._value * right._value % MOD; return left; } public static ModInt operator /(ModInt left, ModInt right) => left * right.Invert; public static ModInt operator ++(ModInt value) { if (value._value == MOD - 1) value._value = 0; else value._value++; return value; } public static ModInt operator --(ModInt value) { if (value._value == 0) value._value = MOD - 1; else value._value--; return value; } public static bool operator ==(ModInt left, ModInt right) => left.Equals(right); public static bool operator !=(ModInt left, ModInt right) => !left.Equals(right); public static implicit operator ModInt(int value) => new ModInt(value); public static implicit operator ModInt(long value) => new ModInt(value); public static ModInt ModPow(ModInt value, long exponent) { var r = new ModInt(1); for (; exponent > 0; value *= value, exponent >>= 1) if ((exponent & 1) == 1) r *= value; return r; } public static ModInt ModFact(int value) { var r = new ModInt(1); for (var i = 2; i <= value; i++) r *= value; return r; } public bool Equals(ModInt other) => _value == other._value; public override bool Equals(object obj) { return obj != null && this.Equals((ModInt) obj); } public override int GetHashCode() => _value.GetHashCode(); public override string ToString() => _value.ToString(); public int CompareTo(ModInt other) { return _value.CompareTo(other._value); } } // ライブラリ置き場ここまで #region Templete #if !LOCAL namespace Library { } #endif public static class Methods { public static readonly int[] dx = {-1, 0, 0, 1}; public static readonly int[] dy = {0, 1, -1, 0}; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void Assert(bool b, string message = null) { if (!b) throw new Exception(message ?? "Assert failed."); } /* public static Comparison greater() where T : IComparable => (a, b) => b.CompareTo(a); */ public static string JoinSpace(this IEnumerable source) => source.Join(" "); public static string JoinEndline(this IEnumerable source) => source.Join("\n"); public static string Join(this IEnumerable source, string s) => string.Join(s, source); public static string Join(this IEnumerable source, char c) => string.Join(c.ToString(), source); /// /// クラスのインスタンスを作成します。 /// /// firstの型 /// secondの型 /// firstの値 /// secondの値 /// 作成した クラスのインスタンス public static Pair make_pair(T1 first, T2 second) where T1 : IComparable where T2 : IComparable => new Pair(first, second); /// aとbをスワップします。 public static void Swap(ref T a, ref T b) where T : struct { var tmp = b; b = a; a = tmp; } /// aとbの最大公約数を求めます。 /// aとbの最大公約数 public static long Gcd(long a, long b) { while (true) { if (a < b) Swap(ref a, ref b); if (a % b == 0) return b; var x = a; a = b; b = x % b; } } /// aとbの最小公倍数を求めます。 /// aとbの最小公倍数 public static long Lcm(long a, long b) => a / Gcd(a, b) * b; /// /// 指定した数値が素数であるかを判定します。 /// /// 計算量 (sqrt(value)) /// 判定する数値 /// value が素数であるか public static bool IsPrime(long value) { if (value <= 1) return false; for (long i = 2; i * i <= value; i++) if (value % i == 0) return false; return true; } /// /// ^ (mod ) を求める /// /// ^ (mod ) の値 public static long PowMod(long a, long b, long p) { long res = 1; while (b > 0) { if (b % 2 != 0) res = res * a % p; a = a * a % p; b >>= 1; } return res; } /// /// mod pにおけるaの逆元を求めます。 /// /// /// 法 /// public static long ModInv(long a, long p) => PowMod(a, p - 2, p); public static int DivCeil(int left, int right) => left / right + (left % right == 0 ? 0 : 1); public static long DivCeil(long left, long right) => left / right + (left % right == 0L ? 0L : 1L); /// /// src の順列を求めます。 /// /// /// 順列を求める配列 /// src の順列 public static IEnumerable Permutations(IEnumerable src) { var ret = new List(); Search(ret, new Stack(), src.ToArray()); return ret; } private static void Search(ICollection perms, Stack stack, T[] a) { int N = a.Length; if (N == 0) perms.Add(stack.Reverse().ToArray()); else { var b = new T[N - 1]; Array.Copy(a, 1, b, 0, N - 1); for (int i = 0; i < a.Length; ++i) { stack.Push(a[i]); Search(perms, stack, b); if (i < b.Length) b[i] = a[i]; stack.Pop(); } } } /// /// 指定した条件を満たす最小の数値を返します。 /// /// 検索する数値の最小値 /// 検索する数値の最大値 /// 条件 /// 条件を満たす最小の数値 public static long BinarySearch(long low, long high, Func expression) { while (low < high) { long middle = (high - low) / 2 + low; if (!expression(middle)) high = middle; else low = middle + 1; } return high; } /// /// 指定した値以上の先頭のインデクスを返します。 /// /// 比較する値の型 /// 対象の配列(※ソート済みであること) /// 開始インデクス [inclusive] /// 終了インデクス [exclusive] /// 検索する値 /// 比較関数(インターフェイス) /// 指定した値以上の先頭のインデクス public static int LowerBound(T[] arr, int start, int end, T value, IComparer comparer) { int low = start; int high = end; while (low < high) { var mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) < 0) low = mid + 1; else high = mid; } return low; } /// /// 指定した値以上の先頭のインデクスを返します。 /// /// 比較する値の型 /// 対象の配列(※ソート済みであること) /// 検索する値 /// 指定した値以上の先頭のインデクス public static int LowerBound(T[] arr, T value) where T : IComparable { return LowerBound(arr, 0, arr.Length, value, Comparer.Default); } /// /// 指定した値より大きい先頭のインデクスを返します。 /// /// 比較する値の型 /// 対象の配列(※ソート済みであること) /// 開始インデクス [inclusive] /// 終了インデクス [exclusive] /// 検索する値 /// 比較関数(インターフェイス) /// 指定した値より大きい先頭のインデクス public static int UpperBound(T[] arr, int start, int end, T value, IComparer comparer) { int low = start; int high = end; while (low < high) { var mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) <= 0) low = mid + 1; else high = mid; } return low; } /// /// 指定した値より大きい先頭のインデクスを返します。 /// Z /// 比較する値の型 /// 対象の配列(※ソート済みであること) /// 検索する値 /// 指定した値より大きい先頭のインデクス public static int UpperBound(T[] arr, T value) { return UpperBound(arr, 0, arr.Length, value, Comparer.Default); } public static IEnumerable SelectNotNull(this IEnumerable source, Func func) => source.Where(val => val != null).Select(func); public static IEnumerable WhereNotNull(this IEnumerable source) => source.Where(val => val != null); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] ArrayOf(params T[] arr) => arr; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static List ListOf(params T[] arr) => new List(arr); public static IEnumerable Repeat(TResult value) { while (true) yield return value; // ReSharper disable once IteratorNeverReturns } public static IEnumerable Repeat(TResult value, int count) => Enumerable.Repeat(value, count); [SuppressMessage("ReSharper", "PossibleMultipleEnumeration")] public static IEnumerable Repeat(this IEnumerable source, int count) { if (source == null) throw new ArgumentNullException(nameof(source)); if (count < 0) throw new ArgumentOutOfRangeException(nameof(count)); for (int i = 0; i < count; i++) foreach (var v in source) yield return v; } [SuppressMessage("ReSharper", "PossibleMultipleEnumeration")] public static IEnumerable Repeat(this IEnumerable source) { if (source == null) throw new ArgumentNullException(nameof(source)); while (true) foreach (var v in source) yield return v; } /// /// 文字の配列を文字列に変換します。 /// /// 文字の配列 /// 変換した文字列 public static string AsString(this IEnumerable source) => new string(source.ToArray()); /// /// の累積和を返します。 /// /// の累積和 public static IEnumerable CumSum(this IEnumerable source) { long sum = 0; foreach (var item in source) yield return sum += item; } /// /// の累積和を返します。 /// /// の累積和 public static IEnumerable CumSum(this IEnumerable source) { int sum = 0; foreach (var item in source) yield return sum += item; } /// /// が l以上 r未満の範囲に含まれているかを返します。 /// /// 要素の型 /// 判定する値 /// 下限の値 (含まれる) /// 上限の値 (含まれない) /// が指定した範囲に含まれているか public static bool IsIn(this T value, T l, T r) where T : IComparable { if (l.CompareTo(r) > 0) throw new ArgumentException(); return l.CompareTo(value) <= 0 && value.CompareTo(r) < 0; } /// /// 以上 未満の値を ずつ増やした結果を列挙します。 /// /// 値の下限 (含まれる) /// 値の上限 (含まれない) /// 1要素ごとに増やす値 /// 範囲の結果 public static IEnumerable Range(int start, int end, int step = 1) { for (var i = start; i < end; i += step) yield return i; } /// /// 0 以上 未満の値を 1 ずつ増やした結果を列挙します。 /// /// 値の上限 (含まれない) /// 範囲の結果 public static IEnumerable Range(int end) => Range(0, end); /// /// 以上 未満の値を ずつ増やした結果を逆順に列挙します。 /// /// 値の下限 (含まれる) /// 値の上限 (含まれない) /// 1要素ごとに増やす値 /// 範囲の結果 public static IEnumerable RangeReverse(int start, int end, int step = 1) { for (var i = end - 1; i >= start; i -= step) yield return i; } /// /// 0 以上 未満の値を 1 ずつ増やした結果を逆順に列挙します。 /// /// 値の上限 (含まれない) /// 範囲の結果 public static IEnumerable RangeReverse(int end) => RangeReverse(0, end); /// /// 指定した配列をコピーして昇順ソートします。(非破壊的) /// /// ソートする配列の型 /// ソートする配列 /// ソートされた配列 public static T[] Sort(this T[] arr) { var array = new T[arr.Length]; arr.CopyTo(array, 0); Array.Sort(array); return array; } /// /// 指定した配列をコピーして降順ソートします。(非破壊的) /// /// ソートする配列の型 /// ソートする配列 /// ソートされた配列 public static T[] SortDescending(this T[] arr) { var array = new T[arr.Length]; arr.CopyTo(array, 0); Array.Sort(array); Array.Reverse(array); return array; } public static double Log2(double x) => Log(x, 2); public static bool chmin(ref T a, T b) where T : IComparable { if (a.CompareTo(b) > 0) { a = b; return true; } return false; } public static bool chmax(ref T a, T b) where T : IComparable { if (a.CompareTo(b) < 0) { a = b; return true; } return false; } public static T Min(params T[] col) => col.Min(); public static T Max(params T[] col) => col.Max(); /// /// 要素数 (a, b) の、defaultValue で満たされたジャグ配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 指定した条件で初期化された配列 public static T[][] JaggedArray2D(int a, int b, T defaultValue = default(T)) { var ret = new T[a][]; for (int i = 0; i < a; i++) { ret[i] = Enumerable.Repeat(defaultValue, b).ToArray(); } return ret; } /// /// 要素数 (a, b) の,defaultValue で満たされた二次元配列を作成します。 /// /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 配列の型 public static T[,] Array2D(int a, int b, T defaultValue = default(T)) { var ret = new T[a, b]; for (int i = 0; i < a; i++) for (int j = 0; j < b; j++) ret[i, j] = defaultValue; return ret; } /// /// ジャグ配列を2次元配列に変換します。配列の各要素の長さがすべて同じである必要があります。 /// /// ジャグ配列 /// 二次元配列 public static T[,] To2DArray(this T[][] array) { if (!array.Any()) return new T[0, 0]; int len = array[0].Length; if (array.Any(x => x.Length != len)) throw new ArgumentException("array の各要素の長さが異なります。", nameof(array)); var ret = new T[array.Length, len]; for (int i = 0; i < array.Length; i++) { for (int j = 0; j < len; j++) { ret[i, j] = array[i][j]; } } return ret; } // public static vector ToVector(this IEnumerable source) => new vector(source); } public static class Input { private const char _separator = ' '; private static readonly Queue _input = new Queue(); private static readonly StreamReader sr = #if FILE new StreamReader("in.txt"); #else new StreamReader(Console.OpenStandardInput()); #endif public static string ReadLine => sr.ReadLine(); public static string ReadStr => Read; public static string Read { get { if (_input.Count != 0) return _input.Dequeue(); // ReSharper disable once PossibleNullReferenceException var tmp = sr.ReadLine().Split(_separator); foreach (var val in tmp) { _input.Enqueue(val); } return _input.Dequeue(); } } public static int ReadInt => int.Parse(Read); public static long ReadLong => long.Parse(Read); public static double ReadDouble => double.Parse(Read); public static string[] StrArray() => ReadLine.Split(' '); public static int[] IntArray() => ReadLine.Split(' ').Select(int.Parse).ToArray(); public static long[] LongArray() => ReadLine.Split(' ').Select(long.Parse).ToArray(); public static string[] StrArray(int n) { var ret = new string[n]; for (long i = 0; i < n; ++i) ret[i] = Read; return ret; } public static int[] IntArray(int n, int offset = 0, bool sorted = false) { var ret = StrArray(n).Select(x => int.Parse(x) + offset).ToArray(); if (sorted) Array.Sort(ret); return ret; } public static long[] LongArray(int n, long offset = 0, bool sorted = false) { var ret = StrArray(n).Select(x => long.Parse(x) + offset).ToArray(); if (sorted) Array.Sort(ret); return ret; } public static string[,] Str2DArray(int n, int m) { var ret = new string[n, m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ret[i, j] = ReadStr; return ret; } public static int[,] Int2DArray(int n, int m, int offset = 0) { var ret = new int[n, m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ret[i, j] = ReadInt + offset; return ret; } public static long[,] Long2DArray(int n, int m, long offset = 0) { var ret = new long[n, m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ret[i, j] = ReadLong + offset; return ret; } public static Tuple StrArrays2(int n) { var ret1 = new string[n]; var ret2 = new string[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadStr; ret2[i] = ReadStr; } return Tuple.Create(ret1, ret2); } public static Tuple IntArrays2(int n, int offset1 = 0, int offset2 = 0) { var ret1 = new int[n]; var ret2 = new int[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadInt + offset1; ret2[i] = ReadInt + offset2; } return Tuple.Create(ret1, ret2); } public static Tuple LongArrays2(int n, long offset1 = 0, long offset2 = 0) { var ret1 = new long[n]; var ret2 = new long[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadLong + offset1; ret2[i] = ReadLong + offset2; } return Tuple.Create(ret1, ret2); } public static Tuple StrArrays3(int n) { var ret1 = new string[n]; var ret2 = new string[n]; var ret3 = new string[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadStr; ret2[i] = ReadStr; } return Tuple.Create(ret1, ret2, ret3); } public static Tuple IntArrays3(int n, int offset1 = 0, int offset2 = 0, int offset3 = 0) { var ret1 = new int[n]; var ret2 = new int[n]; var ret3 = new int[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadInt + offset1; ret2[i] = ReadInt + offset2; ret3[i] = ReadInt + offset3; } return Tuple.Create(ret1, ret2, ret3); } public static Tuple LongArrays3(int n, long offset1 = 0, long offset2 = 0, long offset3 = 0) { var ret1 = new long[n]; var ret2 = new long[n]; var ret3 = new long[n]; for (int i = 0; i < n; i++) { ret1[i] = ReadLong + offset1; ret2[i] = ReadLong + offset2; ret3[i] = ReadLong + offset3; } return Tuple.Create(ret1, ret2, ret3); } private static bool TypeEquals() => typeof(T) == typeof(U); private static T ChangeType(U a) => (T) System.Convert.ChangeType(a, typeof(T)); private static T Convert(string s) => TypeEquals() ? ChangeType(int.Parse(s)) : TypeEquals() ? ChangeType(long.Parse(s)) : TypeEquals() ? ChangeType(double.Parse(s)) : TypeEquals() ? ChangeType(s[0]) : ChangeType(s); public static bool In(out T a) { try { a = Convert(Read); return true; } catch { a = default(T); return false; } } public static bool In(out T a, out U b) { try { var ar = StrArray(2); a = Convert(ar[0]); b = Convert(ar[1]); return true; } catch { a = default(T); b = default(U); return false; } } public static bool In(out T a, out U b, out V c) { try { var ar = StrArray(3); a = Convert(ar[0]); b = Convert(ar[1]); c = Convert(ar[2]); return true; } catch { a = default(T); b = default(U); c = default(V); return false; } } public static bool In(out T a, out U b, out V c, out W d) { try { var ar = StrArray(4); a = Convert(ar[0]); b = Convert(ar[1]); c = Convert(ar[2]); d = Convert(ar[3]); return true; } catch { a = default(T); b = default(U); c = default(V); d = default(W); return false; } } public static bool In(out T a, out U b, out V c, out W d, out X e) { try { var ar = StrArray(5); a = Convert(ar[0]); b = Convert(ar[1]); c = Convert(ar[2]); d = Convert(ar[3]); e = Convert(ar[4]); return true; } catch { a = default(T); b = default(U); c = default(V); d = default(W); e = default(X); return false; } } } public static class Output { public static void print(T t) => Console.WriteLine(t); public static void print(params object[] o) => Console.WriteLine(o.Join(" ")); public static void PrintBool(bool val, string yes = "Yes", string no = "No") => Console.WriteLine(val ? yes : no); public static void PrintYn(bool val) => PrintBool(val); public static void PrintYN(bool val) => PrintBool(val, "YES", "NO"); public static void PrintPossible(bool val) => PrintBool(val, "Possible", "Impossible"); public static void PrintYay(bool val) => PrintBool(val, "Yay!", ":("); public static void PrintDebug(params object[] args) => Console.Error.WriteLine(string.Join(" ", args)); /// /// setter で設定された値を標準出力に出力します。 /// public static object cout { set { Console.WriteLine(value); } } /// /// Local環境のみ,setter で設定された値を標準出力に出力します。 /// public static object dout { set { #if LOCAL Console.WriteLine(value); #endif } } /// /// setter で設定された値を標準エラー出力に出力します。 /// public static object cerr { set { Console.Error.WriteLine(value); } } public const string endl = "\n"; } public class Program { public static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; Console.SetOut(sw); new Solver().Main(); Console.Out.Flush(); Console.Read(); } } [DebuggerDisplay("({first}, {second})")] public class Pair : IComparable>, IEquatable> where T1 : IComparable where T2 : IComparable { public Pair(T1 first, T2 second) { this.first = first; this.second = second; } public T1 first; public T2 second; public int CompareTo(Pair other) { if (ReferenceEquals(this, other)) return 0; if (ReferenceEquals(null, other)) return 1; var firstComparison = first.CompareTo(other.first); return firstComparison != 0 ? firstComparison : second.CompareTo(other.second); } public override string ToString() => $"({first}, {second})"; public bool Equals(Pair other) { if (ReferenceEquals(null, other)) return false; if (ReferenceEquals(this, other)) return true; return EqualityComparer.Default.Equals(first, other.first) && EqualityComparer.Default.Equals(second, other.second); } public override bool Equals(object obj) { if (ReferenceEquals(null, obj)) return false; if (ReferenceEquals(this, obj)) return true; return obj.GetType() == GetType() && Equals((Pair) obj); } public override int GetHashCode() { unchecked { return (EqualityComparer.Default.GetHashCode(first) * 397) ^ EqualityComparer.Default.GetHashCode(second); } } } #endregion }