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.