Binary Tree BST Subtree Count Query

Given a binary tree with \( n \) nodes and each node having a weight, with node 1 as the root. There are \( m \) operations, where in each operation, the weight of a node is modified. After each modification, you need to report the number of nodes whose subtree (including itself) forms a binary search tree (BST).

The BST is defined as follows:

• A tree with one node is a BST.
• A tree with more than one node is a BST if and only if:
  • The left subtree is empty or is a BST, and every node in the left subtree has a weight \( \leq \) the root's weight.
  • The right subtree is empty or is a BST, and every node in the right subtree has a weight \( \geq \) the root's weight.

inputFormat

The first line contains two integers \( n \) and \( m \): the number of nodes and the number of operations.

The second line contains \( n \) integers, where the \( i \)th integer represents the initial weight of node \( i \).

The next \( n \) lines describe the binary tree. The \( i \)th of these lines contains two integers representing the left and right child of node \( i \), respectively. A value of \( -1 \) indicates the absence of a child.

The following \( m \) lines each contain two integers \( u \) and \( w \), indicating that the weight of node \( u \) is updated to \( w \). After each update, output the number of nodes whose subtree is a BST.

outputFormat

For each update operation, output a single line containing an integer that represents the number of nodes whose subtree (rooted at that node) is a BST after the update.

sample

3 2
2 1 3
2 3
-1 -1
-1 -1
2 2
1 1

3
2