Alex and Complicated Task

2000ms

262144K

Description:

After you have read all the problems, probably, you think Alex is genius person. That's true! One day he came up with the following task.

Given a sequence of integer numbers a₁, a₂, ..., a_n. You are to find a longest sequence b₁, b₂, ..., b_4m, that satisfies the following conditions:

b_4k + 1 = b_4k + 3 for all valid integer k;
b_4k + 2 = b_4k + 4 for all valid integer k;
sequence b is subsequence of a (not necessarily contiguous subsequence).

And finally... Alex had given this complicated task to George, and George gave it to you. Help George to cope with the task.

Input:

The first line contains a single integer n (1 ≤ n ≤ 5·10⁵). The next line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output:

In the first line print a single integer 4m — the maximal possible length of required sequence b. In the second line print 4m integers b₁, b₂, ..., b_4m, that is required sequence.

If there are multiple optimal answers you may print any of them.

Sample Input:

4
3 5 3 5

Sample Output:

4
3 5 3 5

Sample Input:

10
35 1 2 1 2 35 100 200 100 200

Sample Output:

8
1 2 1 2 100 200 100 200

Informação

Provedor Codeforces

Código CF467E