Shubham and Subarrays
Tag(s):

## Data Structures, Easy-Medium, Hash table, Hash table

Problem
Editorial
Analytics

You are given an array consisting of n integer numbers $a_1,a_2..a_n$. Two subarrays $[l_1 \space r_1]$ ($1\le l_1\le r_1\le n$) and $[l_2 \space r_2]$ ($1\le l_2\le r_2\le n$) are considered the same if they have the same "special set" of numbers. Output the number of distinct subarrays.
Note: A "special set" of numbers is a set of unique numbers sorted in increasing order.For example,the "special set" corresponding to the numbers [$5,2,7,2,5,9$] is [$2,5,7,9$].

Input Format
First line contains n denoting the number of array elements.
Second line contains n integers denoting $a_1,a_2..a_n$

Output Format

Constraints
$1\le n\le 1000$
$1\le a_i\le 1000$

SAMPLE INPUT
3
1 1 2

SAMPLE OUTPUT
3

Explanation

Special Set of numbers in subarray [1 1]: {1}
Special Set of numbers in subarray [2 2]: {1}
Special Set of numbers in subarray [3 3]: {2}
Special Set of numbers in subarray [1 2]: {1}
Special Set of numbers in subarray [1 3]: {1,2}
Special Set of numbers in subarray [2 3]: {1,2}
Thus the number of distinct subarrays are 3.

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: 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

January Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming