My submission for 283A - Cows and Sequence did not pass the system test because it was not efficient enough, in particular I had to update the first *a*_{i} elements by adding *x*_{i}. Later, Akshai told me how to avoid this.

**Example:**

Suppose you have the sequence 0,1,2,3,4,5 and you have to add *x* = 7 to the first *a* = 3 elements. What you do is you store an array "added_X" that keeps track of the added x values. added_X is initialized with 0. We will also keep a variable "sum" that keeps track of the total sum of elements in the sequence array.

```
sequence: 0,1,2,3,4,5
added_X: 0,0,0,0,0,0
sum=15
```

Now, we somehow have to add x=7 to the first a=3 elements. We could change the sequence array but instead we store that information in the added_X array by setting `added_X[a-1]+=x`

where added_X is 0-indexed:

```
sequence: 0,1,2,3,4,5 // not changed
[actual]: 7,8,9,3,4,5 // <-- not stored and only shown for illustration purposes
added_X: 0,0,7,0,0,0 // added_X[a-1]+=x, i.e. added_X[2]+=7
sum=sum+(x*a)=15+(7*3)=36 // change sum
```

Now, to illustrate why the array "added_X" is so useful, we will remove the last elements.

**1) Remove last element:** Perform the following operations:

```
sum = sum - sequence[last] - added_X[last] = 36-5-0 = 31
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0=0
```

With this last operation we carry the information about the added x values to the left because we know that all numbers to the left in the sequence have been increased by x.

Updated (last elements of sequence and added_X have been removed):

```
sequence: 0,1,2,3,4
[actual:] 7,8,9,3,4
added_X: 0,0,7,0,0
sum=31
```

**2) Remove last element:** Perform the following operations:

```
sum = sum - sequence[last] - added_X[last] = 31-4-0 = 27
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0 = 0
```

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

```
sequence: 0,1,2,3
[actual:] 7,8,9,3
added_X: 0,0,7,0
sum=27
```

**3) Remove last element:** Perform the following operations:

```
sum = sum - sequence[last] - added_X[last] = 27-3-0 = 24
added_X[last-1] = added_X[last-1] + added_X[last]
```

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

```
sequence: 0,1,2
[actual:] 7,8,9
added_X: 0,0,7
sum=24
```

**The next removal will make clear why the array added_X is so useful**

**4) Remove last element:** Perform the following operations:

```
sum = sum - sequence[last] - added_X[last] = 24-2-7 = 15
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7
```

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

```
sequence: 0,1
[actual:] 7,8
added_X: 0,7 // <--- Note how "information" is passed to the left
sum=15
```

**5) Remove last element:** Perform the following operations:

```
sum = sum - sequence[last] - added_X[last] = 15-1-7 = 7
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7
```

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

```
sequence: 0
[actual:] 7
added_X: 7 // <--- Note how "information" is passed to the left
sum=7
```

**Note:** The case where we have to append an element *k* to the sequence can be dealt as follows:

First, we just append

*k*to the sequence array.Second, we set sum=sum+k.

Third, we append 0 to the added_X array.

thnk u