### We Are Discuss About CODECHEF SOLUTION

Ball Sequence Codechef Solution

## Ball Sequence Codechef Solution

## Problem

There is an infinite line of people, with person numbered $(i+1)$ standing on the right of person numbered $i$. Chef can do $2$ types of operations to this line of people:

- Type $1$: Give a ball to the person number $1$.

If there exits a person with two balls, they drop one ball and give the other ball to the person on their right, and this repeats until everyone has at most $1$ ball. - Type $2$: Everyone gives their ball to the person on their left simultaneously. Since there is no one to the left of person $1$, they would drop their original ball if they have one.

Chef gives a total of $N$ instructions, out of which $K$ instructions are of type $2$.

Each instruction is numbered from $1$ to $N$. The indices of instructions of type $2$ are given by the array $A_{1},A_{2},…,A_{K}$. The rest operations are of type $1$.

Find the number of balls that have been dropped by the end of all the instructions.

### Input Format

- The first line of input will contain a single integer $T$, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers $N$ and $K$ — the total number of operations and number of operations of type $2$.
- The next line contains the array $K$ space-separated integers $A_{1},A_{2},…,A_{K}$ – the indices of instructions of type $2$.

### Output Format

For each test case, output on a new line the number of balls that have been dropped by the end of all the instructions.

### Constraints

- $1≤T≤100$
- $1≤N≤1_{9}$
- $1≤K≤1_{5}$
- $1≤A_{i}≤N$ for each $1≤i≤M$
- $A_{1}<A_{2}<⋯<A_{K}$
- The sum of $K$ over all test cases won’t exceed $1_{5}$.

### Sample 1:

3 5 2 3 4 1 1 1 1000000000 5 271832455 357062697 396505195 580082912 736850926

2 0 999999980

### Explanation:

**Test case $1$:** The operations are performed as follows:

- Type $1$: Only person $1$ has a ball. Till now, $0$ balls dropped.
- Type $1$: Person $1$ has $2$ balls. So he drops $1$ ball and passes $1$ to its right. Now, only person $2$ has a ball. Till now, $1$ ball dropped.
- Type $2$: Person $2$ passes the ball to its left. Now, only person $1$ has a ball. Till now, $1$ ball dropped.
- Type $2$: Person $1$ drops the ball. Till now, $2$ balls dropped.
- Type $1$: Only person $1$ has a ball. Till now, $2$ balls dropped.

In total, $2$ balls are dropped.

**Test case $2$:** Only one operation occurs which is of type $2$, so no balls are dropped.

## SOLUTION

## Ball Sequence Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here **JOIN NOW**