Amazon's development team is working on a feature for a new product, a smart array processor. A user has provided an integer array called arr of size n and a 2-dimensional array called pairs of size m x 2. Each pair in pairs represents the starting and ending indices of a subarray within arr.

For each subarray of arr represented by the array pairs, the goal is to merge and concatenate them into a new array called beautiful.

The beauty of an element at index i in arr is defined as follows: if the index i has not contributed to the formation of the array beautiful, the beauty is the count of integers in beautiful that have a value strictly smaller than arr[i]. If the index i has contributed to the formation of the array beautiful, its beauty is 0.

Find the sum of the beauties of all the elements in the array arr.

Example

n = 6
arr = [1, 2, 3, 2, 4, 5]
m = 4
pairs = [[0, 1], [3, 4], [0, 0], [3, 4]]

The subarrays represented by pairs are:

Pair	Start	End	Subarray
[0, 1]	0	1	[1, 2]
[3, 4]	3	4	[2, 4]
[0, 0]	0	0	[1]
[3, 4]	3	4	[2, 4]

On concatenating all the subarrays represented by pairs, we get beautiful = [1, 2, 2, 4, 1, 2, 4].

The indices 2 and 5 don't contribute to the formation of the array beautiful.

• For index 0, arr[0] = 1, the index has contributed to the formation of beautiful, hence its beauty is 0.
• For index 1, arr[1] = 2, the index has contributed to the formation of beautiful, hence its beauty is 0.
• For index 2, arr[2] = 3, the elements [1, 2, 2, 1, 2] in beautiful are smaller than 3, having count = 5, hence its beauty is 5.
• For index 3, arr[3] = 2, the index has contributed to the formation of beautiful, hence its beauty is 0.
• For index 4, arr[4] = 4, the index has contributed to the formation of beautiful, hence its beauty is 0.
• For index 5, arr[5] = 5, the elements [1, 2, 2, 4, 1, 2, 4] in beautiful are smaller than 5, having count = 7, hence its beauty is 7.

The sum of beauties of elements in arr is 0 + 0 + 5 + 0 + 0 + 7 = 12, hence the answer is 12.

Function Description

Complete the function findTotalBeauty in the editor below.

findTotalBeauty has the following parameters:

• int arr[n]: an array of integers.
• int pairs[m][2]: a 2-dimensional array of integers.

Returns

• long: the sum of beauties of elements in array arr.

Constraints

• 1 ≤ n, m ≤ 200,000
• 1 ≤ arr[i] ≤ 1,000,000,000
• 0 ≤ pairs[i][0] ≤ pairs[i][1] < n

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.