Longest Contiguous Arithmetic Subsequence

Given a sequence of n integers, your task is to find the length of the longest contiguous subsequence that forms an arithmetic progression.

An arithmetic progression is defined as a sequence where the difference between consecutive elements is constant. Formally, a subsequence a[l], a[l+1], ..., a[r] (with r ≥ l) is an arithmetic progression if for every index i such that l ≤ i < r, we have:

$$a[i+1] - a[i] = d$$

where d is a constant.

The input is given in two lines. The first line consists of an integer n representing the number of elements in the sequence. The second line provides the n integers separated by spaces. Your output should be a single integer which is the length of the longest contiguous arithmetic subsequence.

inputFormat

The input consists of two lines:

1. The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the sequence.
2. The second line contains n space-separated integers, representing the sequence.

outputFormat

Output a single integer which is the length of the longest contiguous subsequence that forms an arithmetic progression.

## sample

5
1 3 5 7 9

5

</p>