AtCoDeer y la permutación
Tenemos una permutación de números enteros , . Dados pares de números enteros entre 1 y (incluidos), representados como ( ) , ( ) , , ( ). AtCoDeer el venado va a realizar la siguiente operación sobre tantas veces como desee para que el número de () tal que = sea máximo:
- Elegir tal que () , e intercambiar con
Encuentra el máximo posible de números () tal que = después de las operaciones .
Constantes
- es una permutación de enteros de a .
- Si , {} {}
- Todos los valores de la entrada son enteros.
Entrada
- La primera línea de entrada contiene a y .
- La segunda línea de entrada contiene la permutacion .
- Las siguientes líneas describen los pares de enteros.
Salida
Imprima el número máximo posible de números tal que = después de las operaciones.
Ejemplo #1 de Entrada
5 2
5 3 1 4 2
1 3
5 4
Ejemplo #1 de Salida
2
Si realizamos una operación eligiendo = , se convierte en , lo cual es óptimo , la respuesta es 2.
Ejemplo #2 de Entrada
3 2
3 2 1
1 2
2 3
Ejemplo #2 de Salida
3
Si realizamos las operaciones eligiendo = 1 , = 2 , = 1 , en ese orden , se convierte en lo que obviamente es óptimo . Tenga en cuenta que es posible elegir el mismo par cualquier número de veces.
Ejemplo #3 de Entrada
10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9
Ejemplo #3 de Salida
8
Ejemplo #4 de Entrada
5 1
1 2 3 4 5
1 5
Ejemplo #4 de Salida
5
No hay que hacer operaciones.
Comments