#K3066. Find Strictly Increasing Subsequence

    ID: 24876 Type: Default 1000ms 256MiB

Find Strictly Increasing Subsequence

Find Strictly Increasing Subsequence

You are given a sequence of n integers representing heights. Your task is to find a strictly increasing subsequence of length at least 3. If such a subsequence exists, output the first three elements of this subsequence. Otherwise, output "No such subsequence".

This problem can be formulated as follows: Given a sequence of integers \(a_1, a_2, \dots, a_n\), find a triple \((a_{i_1}, a_{i_2}, a_{i_3})\) with \(i_1 < i_2 < i_3\) such that \(a_{i_1} < a_{i_2} < a_{i_3}\). If there are multiple answers, output the earliest valid subsequence as encountered by a greedy strategy.

Note: The input is provided via standard input and the output should be printed to standard output.

inputFormat

The input consists of two lines:

  • The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of elements in the sequence.
  • The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

If a strictly increasing subsequence of length at least 3 exists, output the first three elements of the subsequence separated by a space. Otherwise, output the string "No such subsequence".

## sample
5
1 2 3 4 5
1 2 3

</p>