n개의 정수들로 이루어진 수열[a₁ a₂ ... a_n]이 있다.

여기에 정수 i를 주면서 '축소'라는 명령을 하면 a_i와 a_i+1이 없어지고 대신 두 수의 차가 들어간다.

즉 새로 들어간 수는 |a_i-a_i+1|이다.

바꿔 말하면 축소 연산 i는축소 ([a₁, a₂, ..., a_n], i) = [a₁ ... a_i-1|a_i-a_i+1|a_i+2 ... a_n] 이다.

단 1≤i≤n-1.

예를 들어,

수열 [12, 10, 4, 3, 5]에 축소 연산들 2, 3, 2, 1을 차례대로 적용하면

축소([12, 10, 4, 3, 5], 2) = [12, 6, 3, 5]

축소([12, 6, 3, 5], 3) = [12, 6, 2]

축소([12, 6, 2], 2) = [12, 4]

축소([12, 4], 1) = [8]이 되므로,

마지막에 8이 남는다.

같은 수열에 축소 연산 1, 1, 1, 1을 적용하며,

축소([12, 10, 4, 3, 5], 1) = [2, 4, 3, 5]

축소([2, 4, 3, 5], 1) = [2, 3, 5]

축소([2, 3, 5], 1) = [1, 5]

축소([1, 5], 1) = [4]가 되므로,

마지막에 4가 남는다.

입력으로 수열과 최종값이 주어질 때, n-1번의 축소 연산을 수행하여 최종값을 얻을수 있는가를 알아내는 프로그램을 작성하시오.

최종값을 얻을 수 있는 축소연산들이 여러개일 경우는 그 중 하나만 출력한다.

수열 축소 timer 1초 memory 64MB

수열 축소 1초 64MB