<p>A <strong>peak</strong> in an array <code>arr</code> is an element that is <strong>greater</strong> than its previous and next element in <code>arr</code>.</p>

<p>You are given an integer array <code>nums</code> and a 2D integer array <code>queries</code>.</p>

<p>You have to process queries of two types:</p>

<ul>
	<li><code>queries[i] = [1, l<sub>i</sub>, r<sub>i</sub>]</code>, determine the count of <strong>peak</strong> elements in the <span data-keyword="subarray">subarray</span> <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.<!-- notionvc: 73b20b7c-e1ab-4dac-86d0-13761094a9ae --></li>
	<li><code>queries[i] = [2, index<sub>i</sub>, val<sub>i</sub>]</code>, change <code>nums[index<sub>i</sub>]</code> to <code><font face="monospace">val<sub>i</sub></font></code>.</li>
</ul>

<p>Return an array <code>answer</code> containing the results of the queries of the first type in order.<!-- notionvc: a9ccef22-4061-4b5a-b4cc-a2b2a0e12f30 --></p>

<p><strong>Notes:</strong></p>

<ul>
	<li>The <strong>first</strong> and the <strong>last</strong> element of an array or a subarray<!-- notionvc: fcffef72-deb5-47cb-8719-3a3790102f73 --> <strong>cannot</strong> be a peak.</li>
</ul>

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

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

<p><strong>Output:</strong> <span class="example-io">[0]</span></p>

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

<p>First query: We change <code>nums[3]</code> to 4 and <code>nums</code> becomes <code>[3,1,4,4,5]</code>.</p>

<p>Second query: The number of peaks in the <code>[3,1,4,4,5]</code> is 0.</p>
</div>

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

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

<p><strong>Output:</strong> <span class="example-io">[0,1]</span></p>

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

<p>First query: <code>nums[2]</code> should become 4, but it is already set to 4.</p>

<p>Second query: The number of peaks in the <code>[4,1,4]</code> is 0.</p>

<p>Third query: The second 4 is a peak in the <code>[4,1,4,2,1]</code>.</p>
</div>

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

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i][0] == 1</code> or <code>queries[i][0] == 2</code></li>
	<li>For all <code>i</code> that:
	<ul>
		<li><code>queries[i][0] == 1</code>: <code>0 &lt;= queries[i][1] &lt;= queries[i][2] &lt;= nums.length - 1</code></li>
		<li><code>queries[i][0] == 2</code>: <code>0 &lt;= queries[i][1] &lt;= nums.length - 1</code>, <code>1 &lt;= queries[i][2] &lt;= 10<sup>5</sup></code></li>
	</ul>
	</li>
</ul>

class SegNode:
    def __init__(self, l, r, val, left, right):
        self.l, self.r, self.val = l, r, val
        self.left, self.right = left, right


class SegmentTree:
    def __init__(self, values):
        self.values = values
        self.root = self.build(0, len(values) - 1)
        self.cache = {}

    def build(self, l, r):
        if l == r:
            v = 0
            if 0 < l < len(self.values) - 1:
                v = int(self.values[l - 1] < self.values[l] > self.values[l + 1])
            return SegNode(l, r, v, None, None)
        m = (l + r) // 2
        left, right = self.build(l, m), self.build(m + 1, r)
        return SegNode(l, r, left.val + right.val, left, right)

    def get_val(self, l, r, node, is_root):
        if r < 0 or len(self.values) == l or node.r < l or r < node.l:
            return 0
        if is_root and (l, r) in self.cache:
            return self.cache[(l, r)]
        if l <= node.l and node.r <= r:
            return node.val
        a = self.get_val(l, r, node.left, False)
        b = self.get_val(l, r, node.right, False)
        if is_root:
            self.cache[(l, r)] = a + b
        return a + b

    def update(self, index, new_value):
        def _update(node, index):
            if not 0 <= index < len(self.values):
                return
            if node.l == node.r:
                node.val, i = 0, node.l
                if 0 < i < len(self.values) - 1:
                    node.val = int(
                        self.values[i - 1] < self.values[i] > self.values[i + 1]
                    )
                return node.val

            mid = (node.l + node.r) // 2
            if index <= mid:
                node.val = _update(node.left, index) + node.right.val
            else:
                node.val = node.left.val + _update(node.right, index)

            return node.val

        self.values[index] = new_value
        _update(self.root, index)
        _update(self.root, index - 1)
        _update(self.root, index + 1)
        self.cache = {}

class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:

        tree = SegmentTree(nums)
        ans = []
        for k, a, b in queries:
            if k == 1:
                q = tree.get_val(a + 1, b - 1, tree.root, True)
                ans.append(q)
            else:
                tree.update(a, b)

        return ans

89800