<p>You are given an array of <strong>positive</strong> integers <code>nums</code>.</p>

<p>Return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code>, where the <strong>first</strong> and the <strong>last</strong> elements of the subarray are <em>equal</em> to the <strong>largest</strong> element in the subarray.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,4,3,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:</p>

<ul>
	<li>subarray <code>[<strong><u>1</u></strong>,4,3,3,2]</code>, with its largest element 1. The first element is 1 and the last element is also 1.</li>
	<li>subarray <code>[1,<u><strong>4</strong></u>,3,3,2]</code>, with its largest element 4. The first element is 4 and the last element is also 4.</li>
	<li>subarray <code>[1,4,<u><strong>3</strong></u>,3,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,<u><strong>3</strong></u>,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,3,<u><strong>2</strong></u>]</code>, with its largest element 2. The first element is 2 and the last element is also 2.</li>
	<li>subarray <code>[1,4,<u><strong>3,3</strong></u>,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

<p>Hence, we return 6.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:</p>

<ul>
	<li>subarray <code>[<u><strong>3</strong></u>,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,<strong><u>3</u></strong>,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,<u><strong>3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[<strong><u>3,3</u></strong>,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,<u><strong>3,3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[<u><strong>3,3,3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

<p>Hence, we return 6.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p>There is a single subarray of <code>nums</code> which is <code>[<strong><u>1</u></strong>]</code>, with its largest element 1. The first element is 1 and the last element is also 1.</p>

<p>Hence, we return 1.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>


class segtree:
    def __init__(self, arr = None, f = lambda a, b : a + b):
        if type(arr) == int: 
            self.n = arr + 1
            arr = [0] * self.n
        self.n = len(arr)
        self.tree = [0] * 2 * self.n
        self.f = f
        self._build(arr)

    def _build(self, arr):
        self.tree[self.n : 2*self.n] = arr
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.f(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, index: int, val: int) -> None:
        index += self.n
        self.tree[index] = val
        while index > 1:
            self.tree[index // 2] = self.f(self.tree[index], self.tree[index ^ 1])
            index >>= 1
            
    def __setitem__(self, index: int, val: int) -> None:
        self.update(index, val)

    def query(self, left: int, right: int) -> int:
        left, right = max(0, left), min(right, self.n - 1)
        left, right = left + self.n, right + self.n
        res = 0 if self.f != min else inf

        while left <= right:
            if left & 1:
                res = self.f(res, self.tree[left])
                left += 1
            if not right & 1:
                res = self.f(res, self.tree[right])
                right -= 1
            left, right = left >> 1, right >> 1
        return res

    def clear(self):
        self.tree = [0] * self.n * 2
            
    def __getitem__(self, key: int | slice) -> int:
        if isinstance(key, slice):
            return self.query(0 if key.start is None else key.start, 
                self.n - 1 if key.stop is None else key.stop)
        return self.tree[key + self.n]
        
    def __str__(self):
        return f'Arr: {self.tree[self.n:]}' \
            # + f'\nNodes: {self.tree[:self.n]}'

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        st = segtree(n)

        store = defaultdict(list)
        for idx, i in enumerate(nums):
            store[i].append(idx)
        
        res = 0
        for k in sorted(store, reverse = True):
            c = 1
            for a, b in pairwise(store[k]):
                if st[a:b] == 0:
                    c += 1
                else:
                    res += c * (c + 1) // 2
                    c = 1
            res += c * (c + 1) // 2
            
            for v in store[k]:
                st[v] += 1
        
        return res
46700