### PROBLEM LINKS

### DIFFICULTY

CAKEWALK

### PREREQUISITES

Ad Hoc

### PROBLEM

**N** cups are arranged in a line. There is a ball under one of the cups. You know initially which cup it was under.

Several operations of the following type are performed

**Flip the order of the cups starting from L ^{th} position and ending at R^{th} position, inclusive**

Output the position of the ball after all the operations.

### QUICK EXPLANATION

The cups are numbered **1 to N** from left to right. For some given L and R, if the ball is currently at position x, such that

L ≤ x ≤ R

Then the new position of the ball is going to be

L + R - x

We will see why this is so below. The problem can thus be solved by the following snippet of code

Let x be the initial position of the ball for each operation [L, R] if L ≤ x ≤ R x = L + R - x

### EXPLANATION

If **x** lies between **L** and **R**, let us derive the expression for the new position of **x**.

For this, we will imagine that we have a number line and each one of **L**, **R** and **x** are points on this number line. We will mark these points as **‘L’**, **‘R’** and **‘x’** respectively.

L R <----------0-------L--------x---R---------------> x

**Step 1: Shift everything to the range [0, R-L]**

This can be performed by subtracting **L** from all the positions.

L R <----------0--------(x-L)---(R-L)---------------> x

**Step 2: Flip all positions to the range [-R+L, 0]**

This can be performed by multiplying all the positions with **-1**.

R L <-----------(L-R)---(L-x)--------0--------------> x

**Step 3: Shift back to the range [0, R-L]**

This can be performed by adding **R-L** to all the positions.

R L <----------0--------(R-x)---(R-L)---------------> x

**Step 4: Shift back to the range [L, R]**

This can be performed by adding **L** to all the positions.

R L <----------0-------L--------(L+R-x)---R---------> x

Hence, we can solve the problem by finding the new position after each operation. Note that we do not need to perform any change if **x** does not fall within the boundaries of an operation.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.