There are $4$ arrays of data. The arrays cat$/$n$]$ and cnt$[$n$]$ are each of n integers, and cat$[$i$]$ relates to cnti$].$ These represent a category and count at each index. There are also two arrays of integers that represent q queries. The arrays $[$q$]$ and

$[$q$]$ contain $1-$based indices for the left and right ends of subarrays to consider in cat and cnt$.$

Process the queries in order. Create an array of q values where answer i relates to query i$.$

For each query i:

$$Within the subarrays in cat and cnt$,$ determine the maximum cnt for each cat.

$$Store the sum of these maxima as the answer to the query.

$$Clear the cnt values in the range.

After all queries are processed, return the answer array.

Example:

n$=5$

q$=2$

cat $=[1,2,1,1,3]$

cnt $=[5,3,4,5,2]$

l$=[1,1]$

r $=[3,5]$

Category

$1$

$2$

$1$

$1$

$3$

Count

$5$

$3$

$4$

$5$

$2$

First Query $[1,3]$

category $1$ has two occurrences with a maximum count of $5$ category $2$ occurs once with a count of $3$ the answer to the first query is $5+3=8.$ delete the values within range and go to next query.

second query $[1,5],$

categories $1$ and $3$ occurs once with counts of $5$ and $2$ the answer to the second query is $5+2=7$ delete the values within range

there are no more queries so return the answer array $[8,7]$

Function Description

Complete the function segmentMax in the editor below.

segmentMax has the feilowing parameters: int cat$[$n$]$: categories int cnt$[$n$]$: counts

int $/[$q$]$: left indices of queries $(1-$based$)$ int r$[$q$]$: right indices of queries $(1-$based$)$

Return

int$[$q$]$: the sums of maxima by type for each query range

Constraints

$1<=$ n$,$ q $<=10^5$

$1<=$ cat$[$i$]<=10^4$

$1<=$ cntil $<=10^5$

$1<=$ l$[$i$]<=$ r$[$i$]<=$ n

Input Format For Custom Testing The first line contains an integer, n$,$ the number of elements in cat.

Each line i of the n subsequent lines $($where $0<=$ i $<$ n$)$ contains an integer, catf.

The next line contains an integer, n$,$ the number of elements in cnt$.$

Efch line i of the n subsequent lines $($where $0<=$ i $<$ n$)$ contains an integer, cnt$/.$

The first line contains an integer, q$,$ the number of elements in $/.$

Each line i of the q subsequent lines $($where $0<=$ i $<$ q$)$ contains an integer, I$[$i$].$

The next line contains an integer, q$,$ the number of elements in r$.$

Each line i of the q subsequent lines $($where $0<=$ i $<$ q$)$ contains an integer, r$[$i$].$

#$!/$bin$/$python$3"$

# Complete the 'segmentMax' function below.

#

# The function is expected to return an INTEGER$\_$ARRAY.

# The function accepts following parameters:

# $1.$ INTEGER$\_$ARRAY cat

# $2.$ INTEGER$\_$ARRAY cnt

# $3.$ INTEGER$\_$ARRAY L

#$4.$ INTEGER$\_$ARRAY r

#

def segmentMax $($cat$,$ cht$,$ Lem:

# Write your code here

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

fptr $=$ open $($os$.$ environ$[\text{'}$OUTPUT$\_$PATH'$],\text{'}$w$\text{'})$

cat$\_$count $=$ int$($input$().$ strip $())$

cat $=[]$

for $-$ in range $($cat$\_$count$)$ :

cat$\_$item $=$ int$($input $().$strip$())$

cat. append $($cat$\_$item$)$

cnt$\_$count $=$ int$($input$).$strip $())$

cnt $=[]$

for $-$ in range $($cnt$\_$counti$)$ :

cnt$\_$item $=$ int $($input$().$ strip $())$

cnt$.$ append $($ cnt$\_$item$)$

$1\_$count $=$ int$($input$().$strip$())$

$1=$

for

$-$ in range $($l$\_$count$)$ :

L$\_$item $=$ int$($input$().$strip $())$

l$.$ append $($l$\_$item$)$

r$\_$ count $=$ int $($input$().$ strip $())$

r $=[]$

for $-$ in range$($r$\_$count$)$ :

r$\_$item $=$ int$($input$().$ strip$())$

r$.$ append $($r$\_$item$)$

result $=$ segmentMax $($cat$,$ cnt$,$ l$,$ r$)$

fptr$.$ write$(\text{'}$

$\text{'}.$join$($map$($str$,$ result$)))$

fptr$.$ write$(\text{'}$

$\text{'})$

fptr$.$ close $()$