L. Luana's Album
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Luana has a sticker album. The album has $$$M$$$ slots for stickers, all in a row. The slots are numbered from $$$1$$$ to $$$M$$$ from left to right. Each sticker also contains a number between $$$1$$$ and $$$M$$$. There may be multiple stickers with the same number. On the $$$i$$$-th slot, only stickers containing number $$$i$$$ can be pasted.

Unfortunately, the album has a very strong restriction for filling it: a sticker can only be pasted if it is to the right of all the stickers already pasted.

Luana buys sticker packs one at a time. Each time she buys a pack, Luana looks at the stickers in the pack in order and, for each one, decides whether to paste it in the album or destroy it forever, always respecting the filling condition. Luana never buys a new pack until she has pasted or destroyed all the stickers from the previous pack.

Unfortunately, all the packs sold by the store are identical: they always contain the same stickers, in the same order. To try to complete the album faster, Luana may turn some packs over before opening them, thus reversing the order in which she looks at the stickers in those packs.

Your task is to tell Luana the maximum number of stickers she can paste in the album and the minimum number of packs she has to buy to paste that many stickers.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 2 \times 10^{5}$$$), the number of stickers in each pack and the number of slots in the album.

The second line contains $$$N$$$ integers $$$A_1, \ldots, A_N$$$ ($$$1 \leq A_i \leq M$$$), which indicate the numbers contained in the stickers in the order they appear. The $$$i$$$-th sticker in the pack can only be pasted in the $$$A_i$$$-th slot of the album.

Output

A line with two integers, the first one must be the maximum number of stickers that can be pasted in the album and the second one must be the minimum number of packs Luana has to buy to achieve that.

Examples
Input
6 10
2 8 4 7 5 4
Output
5 2
Input
3 3
3 2 1
Output
3 1
Note

In the first example, Luana should buy two packs in order to maximize the number of stickers she pastes in the album:

  • First pack: without turning it over, she gets stickers 2, 4 and 5 (discarding stickers 8, 7 and 4, in that order)
  • Second pack: she must turn it over, and she gets stickers 7 and 8 (discarding stickers 4, 5, 4 and 2, in that order)

For the second example, Luana buys a single pack and opens it after turning it over.