1
class Solution {
2
  class Node {
3
    long val, displace;
4

5
    Node(long val, long displace) {
6
      this.val = val;
7
      this.displace = displace;
8
    }
9
  }
10

11
  public long subArrayRanges(int[] nums) {
12

13
    // lesser than current element
14
    Stack<Node> stack = new Stack<>();
15
    // from left
16
    long[] lesserLeft = new long[nums.length];
17
    for (int i = 0; i < nums.length; i++) {
18
      long count = 1;
19
      while (stack.size() > 0 && stack.peek().val <= nums[i]) {
20
        count += stack.pop().displace;
21
      }
22
      stack.add(new Node(nums[i], count));
23
      lesserLeft[i] = count;
24
    }
25
    stack.clear();
26
    // from right
27
    long[] lesserRight = new long[nums.length];
28
    for (int i = nums.length - 1; i >= 0; i--) {
29
      long count = 1;
30
      while (stack.size() > 0 && stack.peek().val < nums[i]) {
31
        count += stack.pop().displace;
32
      }
33
      stack.add(new Node(nums[i], count));
34
      lesserRight[i] = count;
35
    }
36

37
    // greater than current element
38
    stack.clear();
39
    // from left
40
    long[] greaterLeft = new long[nums.length];
41
    for (int i = 0; i < nums.length; i++) {
42
      long count = 1;
43
      while (stack.size() > 0 && stack.peek().val >= nums[i]) {
44
        count += stack.pop().displace;
45
      }
46
      stack.add(new Node(nums[i], count));
47
      greaterLeft[i] = count;
48
    }
49
    stack.clear();
50
    // from right
51
    long[] greaterRight = new long[nums.length];
52
    for (int i = nums.length - 1; i >= 0; i--) {
53
      long count = 1;
54
      while (stack.size() > 0 && stack.peek().val > nums[i]) {
55
        count += stack.pop().displace;
56
      }
57
      stack.add(new Node(nums[i], count));
58
      greaterRight[i] = count;
59
    }
60

61
    long ans = 0;
62
    // Now we subtract the count of minimum occurrences from the count of maximum occurrences
63

64
    for (int i = 0; i < nums.length; i++) {
65
      ans += ((lesserLeft[i] * lesserRight[i]) - (greaterLeft[i] * greaterRight[i])) * nums[i];
66
    }
67
    return ans;
68
  }
69
}