WC 6.2 Hard Disks

Ravi has N hard disks. Each disk contains a of parity 0 or 1. The disks are numbered from 1 to N. If 2 disks with opposite parities are adjacent to each other, then both of them are destroyed. The destroyed disks are then removed and the total number of disks decreases by 2. If there are 4 disks A, B, C, D and ( B, C ) are destroyed, then they are removed thereby making A and D adjacent to each other. Only one destruction can occur at a time

Ravi wants to know how many disks will remain after the above process occurs several times until no further destruction is possible.

Help Ravi in finding the minimum number of hard disks that can survive.

Input

The first line of the input contains a single integer N , the number of hard disks. Next line contains N space-separated integers of array A[]

Output

Output an integer equal to the sum of number of hard disks that can survive for each test case provided

Example

N=5 A[]= 1 1 0 0 1 → Output=1
N=4 A[]= 0 0 0 1 → Output=2
N=5 A[]= 1 1 1 1 1 → Output=5

Explanation

In sample 1, this can be the destruction sequence : 1 1 0 0 1 → 1 (1 0) 0 1 →1 (x) 0 1 →1 0 1 → (1 0) 1 →(x) 1 → 1. Hence a single disk is left.

In sample 2, 0 0 0 1 → 0 0 (0 1) → 0 0 (x) → 0 0. Hence output is 2.

In sample 3, all the disks have the same parity. Hence output is 5.

Test case input 1
N=22 A[]= 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1
Test case input 2
N=200 A[]= 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1
Test case input 3

This challenge is worth 80 points.

You must be logged in to submit a solution

View ranklist for this challenge
About scoring and submission

Contact Us


Krish Shah : 9323115454

Kaustubh Khavnekar : 9769408039



Privacy Policy