Sorted Turnstile Scan Distinct Count

EasyTwo-PointersSorted-ArraysDedupCounting5 hidden tests

A turnstile writes each successful badge scan to a log. The log is already sorted in non-decreasing order of badge ID, and the same badge may appear many times in a row. Report how many distinct badge IDs appear.

Input format

Line 1: an integer n. Line 2: n non-decreasing integers, the scanned badge IDs.

Output format

A single integer: the number of distinct badge IDs.

Constraints

1 ≤ n ≤ 100000
1 ≤ each badge ID ≤ 1000000000
The IDs are given in non-decreasing order.

Examples

Example 1

Input

7
1 1 2 2 2 5 8

Expected

Explanation

The distinct IDs are 1, 2, 5, and 8, so the answer is 4.

Example 2

Input

4
9 9 9 9

Expected

Explanation

Only one distinct badge ID (9) appears, so the answer is 1.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →