Geometric sequence
Tag(s):

## 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures