Mảng số đẹp

Submit solution
Points: 1 (partial)
Time limit: 1.0s
Memory limit: 537M
Problem type

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