All Tracks Data Structures Arrays 1-D Problem

Unique Subarrays
Tag(s):

Data Structures, Hard, Implementation, Medium

Problem
Editorial
Analytics

A contiguous subarray is defined as unique if all the integers contained within it occur exactly once. There is a unique weight associated with each of the subarray. Unique weight for any subarray equals it's length if it's unique, 0 otherwise. Your task is to calculate the sum of unique weights of all the contiguous subarrays contained within a given array.

Input
First line of the input contains an integer $$T$$, denoting the number of testcases.
$$2*T$$ lines follow, where first line of each testcase contains an integer $$N$$ denoting the number of integers in the given array. Last line of each testcase then contains $$N$$ single space separated integers

Output
Print the summation of unique weights of all the subarrays for each testcase in a separate line.

Constraints

  • $$1 ≤ T, N ≤ 10^{5}$$
  • $$0 ≤ A_i ≤ 10^{9}$$
  • Summation of $$N$$ for all $$T$$ does not exceed $$10^{5}$$

SAMPLE INPUT
1
5
1 2 3 4 5

SAMPLE OUTPUT
35
Explanation

Sample Case 1: Since, all integers are distinct within any contiguous subarray, therefore the unique weight will be the summation of lengths of all subarrays. Hence, this sums upto $$5 + 4 * 2 + 3 * 3 + 2 * 4 + 1 * 5 = 35$$

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

HackerEarth Collegiate Cup - Qualifier

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications