Mảng số đẹp
Cho một mảng A gồm \(N\) phần tử \((1 \leq N \leq 10^6)\), \(1 \leq A_i \leq 10^9\), \(1 \leq i \leq N)\). Các phần tử gọi là đẹp nếu hai phần tử liền nhau trong mảng được lấy từ mảng \(A\) ban đầu ở vị trí \(i\), \(j\): \(1 \leq i < j \leq N\), \(j\) chia hết cho \(i\), \(a[i] < a[j]\).
Ví dụ mảng 6 phần tử \(A = {1, 2, 7, 7, 7, 7}\) ta tìm được các phần tử đẹp ở vị trí 1, 2, 4 có giá trị là 1, 2, 7 vì vị trí thứ 2 chia hết cho vị trí thứ 1, giá trị \(a[2]=2 > a[1]= 1\) tương tự 6 chia hết cho 2, 7 > 2 vậy mảng đẹp tìm được là {1, 2, 7}.
Hãy tìm độ dài mảng đẹp lớn nhất có thể lấy được từ dãy ban đầu.
Đầu vào:
Dòng đầu tiên gồm một số N (1 <= N <= 10^6)
Dòng thứ hai bao gồm mảng A có N phần tử (1 <= Ai <= 10^9, 1 <= i <=N)
Đầu ra:
In ra một số duy nhất là độ dài mảng đẹp lớn nhất có thể lấy được từ mảng A.
Ví dụ
Input 1
4
5 3 4 6
Output 1
2
Input 2
7
1 4 2 3 6 4 9
Output 2
3
Input 3
5
5 4 3 2 1
Output 3
1
Input 4
1
9
Output 4
1
Chú thích:
Ở ví dụ 1, ta có thể lấy các phần tử ở vị trí 2 và 4, 4 chia hết cho 2 và 6 > 3.
Ở ví dụ 2, ta có thể lấy các phần tử ở vị trí 1, 3, 6.
Comments
Bài này test case 7-8 bị sai đúng không admin ơi Test case 7-8 đáp án phải ra 5 chứ