### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Shiplu Hawlader and Mahbubul Hasan

**Editorialist:** Lalit Kundu

### DIFFICULTY:

SIMPLE-EASY

### PREREQUISITES:

### PROBLEM:

Given N(<=10^5 ) digits (0<=each digit<=9), and M(<=10^5) queries, each consisting of one x(1<=x<=n). Print B1 - B2.

B1 = sum of all ( a_{x} - a_{y} ) such that x > y and a_{x} > a_{y}.

B2 = sum of all ( a_{x} - a_{y} ) such that x > y and a_{x} < a_{y}.

### EXPLANATION:

We define a new array A where A[i][j] is the number of times digit i occurs in a_{1},a_{2},…a_{j}.

Code:

```
for i=0 to 9: // calculate the row A[i] for each i=0 to 9.
for j=1 to n:
A[i][j]=A[i][j-1];
if a[j]==i: A[i][j]++; // if a[j]==i, current value one more than previous.
```

For each input query p, let q=a_{p}, we do:

```
B1=0
for i=0 to q-1: // sum of those where ax > ay
B1 += A[i][p-1]*(q-i) // difference is (x-i)
B2=0
for i=q+1 to 9: // sum of those where ax < ay
B2 += A[i][p-1]*(q-i) // difference is (x-i)
print B1-B2
```

Time Complexity: O( N * 10 ) [ Computation of A ] + M * 10 ( For M queries.)

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.