Subsequence with the Largest Maximum-Minimum Difference

Interview

Time limit0.5sMemory limit256 MB

Summary

Given a sequence, find the shortest contiguous segment whose max minus min equals the largest such difference over all segments.

Level: Medium5 of 10
Topics: Two pointers, Array, Greedy, Implementation
Solved: No attempts yet

Problem

A subsequence of a sequence is a sequence obtained by taking some consecutive terms of the sequence and listing them in their original order. (This is not the usual definition of a subsequence.) Given a sequence $A$ of length $N$ , find the length of the shortest subsequence of $A$ whose value of (maximum in the subsequence) - (minimum in the subsequence) is the largest possible.

Input

The first line gives $N$ . ( $1 \le N \le 10^5$ )

The next line gives $N$ numbers separated by spaces, where the $i$ -th number is $A_i$ . ( $1 \le A_i \le 10^5$ )

Output

Print a single integer, the answer to the problem.

Examples2

Example 1
Input
```
5
1 1 1 1 1
```
Expected output
```
1
```
Example 2
Input
```
5
1 1 2 3 3
```
Expected output
```
3
```