# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*satyam_343*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1172

# PREREQUISITES:

None

# PROBLEM:

You’re given a sequence of N swipe-ins and swipe-outs to a building.

Find the maximum number of people in it, at any point of time.

# EXPLANATION:

Let \texttt{cur} denote the number of people currently in the building.

Initially, \texttt{cur} = 0.

Then, for each 1 \leq i \leq N:

- If A_i is not inside the building, this is an in-swipe.

So, \texttt{cur} will increase by 1. - Otherwise, A_i was already inside the building, and this is an out-swipe.

\texttt{cur} will decrease by 1.

The final answer is the maximum value of \texttt{cur} across the entire process.

We only need to quickly check whether A_i is already inside the building or not.

This can be done, for example, with a `mark`

array.

That is, keep an array `mark`

of length N, where `mark[x] = 1`

means person x is inside the building, and `mark[x] = 0`

otherwise.

Then,

- When person A_i enters, set
`mark[a[i]] = 1`

. - When person A_i exits, set
`mark[a[i]] = 0`

.

Each enter/exit is handled in \mathcal{O}(1) time, for a solution in \mathcal{O}(N) overall.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = [0]*(n + 1)
inside, ans = 0, 0
for x in map(int, input().split()):
if a[x] == 1: inside -= 1
a[x] ^= 1
if a[x] == 1: inside += 1
ans = max(ans, inside)
print(ans)
```