Bantu temanmu belajar dengan menambahkan soal di Kujawab. Klik disini..

Olimpiade Sains Provinsi (OSP) 2018 - Komputer , Nomor 43

43

ANGKA SUBSEKUENS

Pak Dengklek memiliki array yang berisi N elemen, setiap elemen berada diantara 0 sampai 9 (inklusif). Pak Dengklek ingin mencari suatu subsekuens valid terpanjang dari array tersebut. Subsekuens dari suatu array adalah sekuens yang dapat diperoleh dengan menghapus beberapa elemen array tanpa mengubah urutan dari array tersebut. Sebagai contoh, array {1, 3, 3, 6, 7} memiliki subsekuens {1, 3, 6}, {1, 6, 7}, tetapi bukan {1, 7, 6} karena tidak mengubah urutan pada array asli.

Misalkan subsekuens yang dipilih adalah S. S disebut valid apabila dari 1 <= i < |S| (|S| adalah panjang dari array S), banyaknya i dimana Si  != Si + 1 tidak lebih dari 1. Sebagai contoh subsekuens {1, 3, 3} valid karena dua angka berurutan yang nilainya beda tidak lebih dari satu, sedangkan subsekuens {1, 6, 7} tidak valid karena jumlah dua angka berurutan yang nilainya beda ada dua. Bantu Pak Dengklek menentukan panjang S valid yang terpanjang!

Batasan:

1 <= N <= 100.000

Format Masukan:

Baris pertama berisi sebuah bilangan N.

Baris kedua berisi N bilangan, masing-masing menandakan elemen ke-i dari array pak Dengklek.

Format Keluaran:

Sebuah bilangan seperti deskripsi diatas.

Contoh Masukan dan Keluaran:

Contoh Masukan Contoh Keluaran

4

1 1 1 1

4

6

1 1 2 1 2 2

5

7

1 2 2 4 3 5 2

3