Hey guys!

Today I want to ask about this problem.

Given an array A size N and q queries. (|A[i]| <= 1e5, N <= 1e5, q <= 1e5)

Define F(B), B is a subarray (consecutive) of array A, is the number of distinct values of B. For example: F({1, 2, 3, 4}) = 4

For every query i x, change value A[i] to x, and calculate the sum of all F(B) in the new array A. For a query when A = {1, 1, 2}

• F({1}) = F({1}) = F({2}) = F({1, 1}) = 1;

• F({1, 2}) = F({1, 1, 2}) = 2;

The sum result is 1 * 4 + 2 * 2 = 8;

Test: Input

4

1 2 3 4

3

1 1

2 1

3 1

Output

20

17

13