Smallest Increasing Subsequence

You are given an array of integers. A subsequence of the array is obtained by deleting some (or no) elements without changing the order of the remaining elements. The smallest possible strictly increasing subsequence has a length of (2). Your task is to determine whether there exists any strictly increasing subsequence in the array. If such a subsequence exists, output (2); otherwise, output (-1).

In other words, if there exist indices (i) and (j) with (i < j) such that (a_i < a_j), then the answer is (2). If no such pair exists (including the cases when the array has less than two elements), output (-1).

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer (n) ((0 \leq n \leq 200000)) representing the number of elements in the array.
• The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output a single integer via standard output (stdout):

• Output (2) if there exists a strictly increasing subsequence of length at least 2.
• Otherwise, output (-1).## sample

6
1 3 2 4 3 5

2