Cable Connection Counting

On a straight road, there are \(N\) street lamps. The initial height of the \(i\)-th street lamp is \(A_i\) for \(1 \leq i \leq N\). Electrical cables will be strung between certain pairs of lamps under the following conditions:

• For lamps \(i\) and \(j\) with \(i < j\), the heights must be equal, i.e. \(A_i = A_j\).
• For all lamps \(k\) with \(i < k < j\), their height must be strictly less than \(A_i\); that is, \(A_k < A_i\).

Some lamp heights will be adjusted by management. Each adjustment is an operation of the form "change the height of the \(x\)-th lamp to \(h\)". After each modification, you need to immediately compute the number of valid pairs of lamps that satisfy the above conditions.

You are required to implement the following function without performing any input/output operations:

vector count_cable(vector<int> A, vector< pair<int, int> > C)

Here, the array A of length \(N\) represents the initial heights such that A[i] = Ai+1 for \(0 \leq i \leq N-1\). The array C contains \(Q\) pairs \((x, h)\) indicating that the height of the \(x\)-th lamp (1-indexed) should be changed to \(h\).

Your function must return an array of \(Q+1\) integers, where the first element is the number of valid cable connection pairs in the initial configuration, and each subsequent element is the result after each modification.

Note: All formulas are formatted in LaTeX.

inputFormat

The function receives two parameters:

• A: an array of integers of length \(N\) representing the initial heights of the street lamps. The element A[i] corresponds to \(A_{i+1}\) for \(0 \leq i \leq N-1\).
• C: an array of \(Q\) pairs of integers, where each pair \((x, h)\) indicates that the height of the \(x\)-th lamp (1-indexed) is modified to \(h\).

There is no input from standard input; you must implement the function as specified.

outputFormat

The function should return an array of \(Q+1\) integers. The first integer is the number of valid pairs in the initial state, and each of the following \(Q\) integers corresponds to the number of valid pairs after each respective modification.

sample

A = [3,2,3]
C = [(2,4), (2,3)]

[1,0,2]