Company: High radius_6aug
Difficulty: medium
Unfair Multiverse Problem Description One of most bizarre theories in modern era is of "Multiverse". It says that there exists not just a single Universe but multiple universes running parallelly! So for every possible outcome of an event, there exists a universe in which it is the ground truth! So maybe you have crush on someone in this universe but there exists another parallel universe where they have crush on you! Ok enough pretext, let's get to problem. You are God and you represent poverty of N people as an array of N integers. Event is breaking this array into a contagious subarray. For this event there will be N * (N+1) / 2 contagious subarrays possible each of which goes to a multiverse, so every multiverse has a unique subarray representing a population. Let's define unfairness of a subarray as difference between maximum integer and minimum integer. You need to find sum of unfairness of all multiverse. Constraints 1 <= N <= 1000000 0 <= ai < 1000000 Input First li