406478: GYM102419 K The Dragon and the Kingdom of Trees

K. The Dragon and the Kingdom of Treestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees.

King Mahmoud started a new plan to plant $$$n$$$ trees, so he planted $$$n$$$ seeds in $$$n$$$ consecutive places. Initially, the height of every tree is $$$0$$$ units.

Every year the height of every tree increases by one unit, but in some years Ayoub comes and chooses exactly $$$k$$$ non-intersecting sub-arrays of trees and attack them with his dragon.

When a tree is attacked the seed won't be affected, so it can grow again, but its height becomes "0".

King Mahmoud came after $$$m$$$ years and found that the height of the $$$i_{th}$$$ tree is $$$h_i$$$ units.

King Mahmoud noticed that in some years Ayoub's dragon came and attacked the plants. King Mahmoud became very angry and decided to attack Ayoub with his army.

Ayoub is very powerful with his dragon but King Mahmoud has a strategy to take down Ayoub, but he needs to know the minimum possible $$$k$$$ so that the heights of the trees are correct.

King Mahmoud knows that Ayoub attacked at least once, it can also happen that Ayoub attacked immediately after they planted the seeds in the first year.

It can happen that there is no possible $$$k$$$, in that case, Ayoub has cheated and used a different way to attack King Mahmoud's plants, in this case, King's Mahmoud strategy will fail so he won't attack Ayoub.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10 ^ {6})$$$ $$$(1 \leq m \leq 10 ^ {9})$$$.

The second line contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$h_i$$$ which is the height of the $$$i_{th}$$$ $$$(0 \leq h_i \leq m)$$$ plant after $$$m$$$ years.

Output

If there is no possible $$$k$$$ print -1, otherwise print the minimum possible $$$k$$$ on a line.

ExamplesInput

4 3
3 3 3 3

Output

1

Input

4 3
0 0 0 0

Output

1

Input

4 2
2 1 1 2

Output

1

Input

4 2
2 1 2 1

Output

2