## Introduction

### Problem statement

We are given an array having n elements; we have to answer Q queries. In each query, we are provided with A and B. Our task is to find the sum of all elements having a value lesser than A and greater than B.

### Sample Examples

**Example 1:**

```
Input: a[] = { 6, 2, 3, 8, 9 ,1 }, Q = 2
Query1: A = 4, B = 7
Query2: A = 2, B = 8
Output:
23
10
Explanation
Query1: Sum of elements having value lesser than 4 = 1+2+3 = 6, and greater than 7 = 8+9 = 17
Total sum = 6+17 = 23
Query2: Sum of elements having value lesser than 2 = 1, and greater than 8 = 9
Total sum = 1+9 = 10
```

**Example 2:**

```
Input: a[]={7, 5, 9, 3, 4}, Q = 1
Query1: A = 4, B = 6
Output: 19
Explanation
Query1: Sum of all the elements having value lesser than 4 = 3, and greater than 6 = 7+9 = 16
Total sum = 19
```

Recommended topic, __kth largest element in an array____ __and __Euclid GCD Algorithm__

## Brute force approach

The idea is simple, for every query, traverse the whole array. Include the element in the sum if any elementâ€™s value in the given array is less than A or greater than B. Else move to the next element. Finally, return the sum.

### Steps of algorithm

- Declare a sum variable and initialise with 0, sum = 0.
- For every query, run a for loop to traverse the array.
- Inside the loop, if the current elementâ€™s value is lesser than the value of A or greater than the value of B, include the current element in the sum, sum = sum + a[i].
- Finally, return the value of the sum.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int sum_A_B(int a[], int n, int A, int B)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
if (a[i] < A || a[i] > B)
sum += a[i];
}
return sum;
}
int main()
{
int a[] = { 6, 2, 3, 8, 9, 1 };
int Q;
cout << " No. of queries: ";
cin >> Q;
int n = sizeof(a) / sizeof(a[0]);
while (Q--)
{
int A, B;
cout << " Enter A and B: ";
cin >> A >> B;
cout << " sum: " << sum_A_B(a, n, A, B) << endl;
}
return 0;
}
```

**Input:**

```
No. of queries: 2
Enter A and B: 4 7
Enter A and B: 2 8
```

**Output:**

```
sum: 23
sum: 10
```

#### Complexity Analysis

**Time complexity:** We are traversing the whole array of size n for every query (Q). The time complexity is O(Q*n), where Q and n are the numbers of queries and the number of elements in the given array.

**Space complexity:** O(1) as we are using constant extra space.

Must Read __Lower Bound in C++__