Misdelivered letters

Time limit60sMemory limit1024 MB

Summary

Dan must find one house that received its own bill by asking residents which bill they got, using as few visits as possible.

Level: Easy3 of 10
Topics: Array, Brute force
Solved: No attempts yet

Problem

Dan's career as a postman is not going well. Yesterday he had to deliver electricity bills to each of the $N$ houses in Brno. However, he mixed up the order of the bills again and delivered most of them to the wrong houses. Still, he is sure that he delivered at least one letter correctly. Can you help him find it?

The houses in Brno are numbered from 1 to $N$ . There are $N$ bills, and each is addressed to a different house. Every house received exactly one bill. Dan can go to any house, ring the bell, and ask the residents which house's letter they ended up with. Dan does not want to disturb too many people, so he wants to minimize the number of houses he checks.

Constraints

$N = 1000$
$T = 1000$
At least one letter was delivered to the correct house.

Examples1

Example 1
Input
```
1
1
1
```
Expected output
```
1
```