Problem Description

Consider a road that is 20 meters long with tree pits located every 1 meter. The tree pits are numbered from left to right as 0, 1, 2, ..., 20. Some of these pits contain trees, with each pit holding at most one tree.

A person is standing at a window with a telsecope and can observe exactly 4 consecutive tree pits at a time (and any trees within those pits). Given the positions of n trees on the road, determine the maximum number of trees that can be seen simultaneously through the telescope window.

Input Format

• First line: A positive integer n (1 ≤ n ≤ 21), representing the number of trees on the road.
• Second line: n distinct integers in ascending order (each between 0 and 20), separated by spaces, indicating the positions of tree pits containing trees.

Output Format

A single positive integer representing the maximum number of trees visible through the telescope at any given position.

Example

Input:
9
0 2 5 6 11 13 15 16 20

Output:
3

Solution Approach 1: Array-Based Method

Create a array representing each tree pit. Mark positions that contain trees with 1 and empty positions with 0. Then examine every possible 4-position window and find the maximum sum.

n = int(input())
positions = input().split()
tree_array = [0] * 21

for p in positions:
    tree_array[int(p)] = 1

max_visible = 0
for i in range(18):
    window_sum = sum(tree_array[i:i+4])
    max_visible = max(max_visible, window_sum)

print(max_visible)

Solution Approach 2: Sliding Window on Sorted Positions

Since the tree positions are already sorted, use two pointers to count how many trees fall within a window starting from each tree position. Expand the window while the distance between the first and current tree is less than 4.

n = int(input())
positions = [int(x) for x in input().split()]

max_visible = 0
for start in range(n):
    end = start
    while end < n and positions[end] - positions[start] < 4:
        end += 1
    max_visible = max(max_visible, end - start)

print(max_visible)

Explanation

Both approaches acheive O(21) time complexity. The first method uses a direct array representation, while the second method leverages the sorted nature of input positions to use a sliding window technique. Either solution efficiently determines the maximum number of trees visible through a 4-unit telescope window.