All Tracks Basic Programming Implementation Basics of Implementation Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?