За среќен број се смета секој ненегативен цел број помал од К, т.е. за дадено K среќни броеви се броевите 0, 1, 2, …, К-1. Една подниза се смета за среќна доколку секој среќен број се појавува точно 3 пати во оваа подниза.

Дадена е низа од N цели броеви. Пресметајте ја должината на најдолгата среќна подниза во низата за дадено K.

Забележете дека оваа задача е посложена верзија на претходната задача.

Влез

Во првиот ред дадени ви се броевите N и K (1 ≤ N, K ≤ 1 000 000) - должината на низата и бројот на среќни броеви, соодветно.
Во вториот ред се дадени N цели броеви A_i (0 ≤ A_i ≤ 1 000 000), елементите на низата.

Забелешка:
За 30% од поените ќе важи: 1 ≤ N, K ≤ 100
За дополнителни 20% од поените ќе важи: 1 ≤ N ≤ 1 000
За дополнителни 20% од поените ќе важи: 1 ≤ K ≤ 2

Излез

Во првиот и единствен ред отпечатете го одговорот - должината на најдолгата среќна подниза. Доколку не постои среќна подниза, да се отпечати 0.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
10 2
1 0 0 0 1 1 0 3 5 1

излез
8

Oбјаснување за првиот пример: K e 2 па среќни броеви се броевите 0 и 1. Поднизата од третиот до десетиот елемент го содржи бројот 0 точно 3 пати и бројот 1 точно 3 пати и има должина 8.