All Tracks Basic Programming Implementation Basics of Implementation Problem

Geometric sequence
/

Basic Programming, Basics of Implementation, Easy-Medium, Implementation

Problem
Editorial
Analytics

Given a sequence \(a_1{\dots}a_n\).
You need to find a subsequence \(a_{b_1},a_{b_2},\dots,a_{b_m}(b_1< b_2<\dots<b_m)\) and an integer k which satifies \(a_{b_{i+1}}=k\cdot a_{b_i}\) for all \(1\le i<m\).
Your goal is to maximize \(m\).

Input

First line contains an integer \(n\).

Second line contains \(n\) integers, representing the sequence \(a_1{\dots}a_n\).

Output

An integer representing the maximum value of \(m\).

Constraints

\(1\le n\le 10^5\)

\(-10^5\le a_i\le 10^5\)

SAMPLE INPUT
6
1 -2 3 4 0 0
SAMPLE OUTPUT
3
Explanation

\(1,-2,4\) and \(3,0,0\) are two possible subsequences.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?