TECHLN1 - The Invasion

An alien warship named ED.LN (we are assuming ED means Earth Destroyer) has invaded NSIT. The students of NSIT have assembled in Moksha ground to parley with the aliens. If we go to Moksha ground we can see many human chains. For this problem we imagine a straight line going through middle of Moksha ground. Each position on this line is marked from 1 to 100000 (both inclusive).

People are forming human chains along this line. Initially every position is empty. When someone stands in ith position he holds hand of people who are standing in his left and right (if there any) and join their group. If there is no one beside him he forms a new group.

When new people come your job is to mark his position and count currently how many groups are there in Moksha ground.

The ghissus have to attend their classes, so they will come and go as it suits them.

For example suppose:

  • A guy came first and stood on postion 2. Currently there is only 1 group.
  • Then another guy stood in position 4. Currently there are 2 groups.
  • Another guy stood in position 3. Now there are only 1 group.
  • Now the guy in position 3 left. Now there are 2 groups again.

Input

First line will contain an integer t, the number of test cases. Following this, each test cases begins with an integer n, the number of operations that are going to take place. Next n lines will contain integers pi which denotes position of i-th man that joined the chain. If a person is already present at position i, it means that he's leaving for his class.

Output

For each pi print number of groups currently in Koksha ground. In last line print the string "ED.LN destroyed". Don't print any extra spaces.

t <= 10

0 < All operations and positions <= 10^5

Please pay attention while printing new lines in the output as per the example!

Example

Input:
2
3
1
3
5
4
10
11
10
11

Output:
1
2
3

1
1
1
0

ED.LN destroyed

Added by:Tarun Gehlaut
Date:2013-04-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:CSI NSIT

hide comments
2018-06-27 12:58:44
Stupid time limit prevents AC in Python. Downvoting.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.