Limits 1.5s, 512 MB

Let's get into the problem directly without much description this time :D .
You are given an array A of N integers. The elements of the array are A1, A2, A3 ... AN . You are also given Q queries to perform on this array A. In each query, you will be given three integers L, R, X where [L, R] denotes a sub-segment of the array A starting at AL and ending at AR. You have to find the minimum number of operations needed to make all values of the sub-segment, [L, R] of the array A equal to X i.e. AL = AL+1 = AL+2 = ... = AR = X. There are two types of operations. You can apply any of the two operations any number of times.
Two types of operations are described below-
Operation 1: you can choose any index i (1 ≤ i ≤ N) of the array A and then perform Ai = Ai + 1.
Operation 2: you can choose any index i (1 ≤ i ≤ N) of the array A and then perform Ai = Ai - 1.

Note: Every query is independent.

Input

First line contains an integer T(1 ≤ T ≤ 5), the number of test case.
Every test case starts with an integer N(1 ≤ N ≤ 105), the number of elements of the array A.
Next line will contain the elements of the array A1, A2, ..., AN (-109 ≤ Ai ≤ 109).
Next line will contain an integer Q(1 ≤ Q ≤ 105), the number of queries.
Next Q lines will contain three integers L, R(1 ≤ L ≤ R ≤ N) and X(-1012 ≤ X ≤ 1012).

Subtasks
Subtask #1 (10 points)
1 ≤ N, Q ≤ 103.
Subtask #2 (30 points)
1 ≤ N, Q ≤ 105.
There are at most 10 distinct values in the array A.
Subtask #3 (60 points)
Original Constraints.

Output

For each case, print the case number in a single line.
Then for every query print the minimum number of operations needed to make all values of the sub-segment, [L, R] of the array A equal to X.

Sample

InputOutput
1
3
4 5 6
2
1 3 6
1 3 4
Case 1:
3
3

In the 1st query, you have to apply "operation 1" in the 1st index two times and 2nd index one time. So, the answer is 3.

In the 2nd query, you have to apply "operation 2" in the 2nd index one time and 3rd index two times. So, the answer is 3.

Submit

Login to submit.

Statistics

48% Solution Ratio
prodip_bsmrstuEarliest, Aug '20
EgorKulikovFastest, 0.3s
user.536969Lightest, 9.2 MB
MursaleenShortest, 1682B
Toph uses cookies. By continuing you agree to our Cookie Policy.