На перемене Настя пришла в школьную столовую. Всего в школе \(n\) человек, пронумерованных от \(1\) до \(n\). К сожалению, Настя задержалась на уроках, поэтому стоит последней в очереди. Конечно, в столовой образовалась большая очередь, однако Настя не унывает, так как некоторые люди в очереди готовы пропускать каких-то других людей.
Формально, есть сколько-то пар \(u\), \(v\) таких, что если человек с номером \(u\) стоит непосредственно перед человеком с номером \(v\), то Настя может попросить их, и они поменяются местами. Так как людей очень много, Настя просит вас сказать, как близко к началу она сможет продвинуться.
Формально, она просит вас сказать максимальное количество мест в очереди, на которое она может продвинуться.
Выходные данные
Выведите одно целое число — максимальное количество мест в очереди, на которое она может продвинуться.
Примечание
В первом примере Настя просто может поменяться местами с первым человеком в очереди.
Во втором примере можно, чтобы сначала поменялись местами школьники с номерами \(1\) и \(3\), потом \(3\) и \(2\), потом \(1\) и \(2\). Очередь будет выглядеть как \([3, 1, 2]\), затем \([1, 3, 2]\), затем \([1, 2, 3]\) и наконец \([2, 1, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 2
1 2
|
1
|
|
2
|
3 3
3 1 2
1 2
3 1
3 2
|
2
|
|
3
|
5 2
3 1 5 4 2
5 2
5 4
|
1
|