All Tracks Algorithms Searching Linear Search Problem

The Normal Type
Tag(s):

Easy-Medium, Rolling Pointer, Set

Problem
Editorial
Analytics

There are a lot of Poke'mons who are jealous of the fact that they do NOT have any specialty, they're the... normal type of Poke'mon. But, what they fail to realize is that their power is their normalcy, the ability to think, rationalize and then act.

But, they do have an additional power... Poke'mons like Jigglypuff - which are normal, can figure out if a trainer is real or is a part of Team Rocket. And they need to use their power to a great extent.

In an array, which consists of $$N$$ elements, A1, A2, ..., AN, if a subarray has the total number of distinct elements as that of the original array, that determines the presence of Team Rocket.

You've to help the normal type Poke'mons in figuring out the total number of subarrays having total number of distinct elements same as that of the original array.

Input format:
The first line of the input will consist of a single integer $$N$$. The next line will consist of $$N$$ integers A1, A2, ... , AN.

Output format: Output the answer to the problem.

Constraints:
1 ≤ $$N$$ ≤ 2 * 105
1 ≤ $$A$$i ≤ 109

Reference:
enter image description here

SAMPLE INPUT
5
1 2 2 1 1 
SAMPLE OUTPUT
8
Explanation

All the possible subarrays are [1,2] , [1,3] , [1,4] , [1,5] , [2,4] , [2,5] , [3,4] , [3,5]

Time Limit: 1.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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications