A1~AN으로 N개의 숫자로 이루어진 집합이 있을 때, 이 집합에서 증가하다가 감소하는

가장 긴 길이의 수의 나열을 찾고, 그 때 수의 개수를 구하여라.

(수의 나열을 연속되지 않아도 좋지만, 순서는 바뀌면 안된다.

예시)1 5 2 1 4 3 4 5 2 4 1

예시 답) 7

조건을 만족하는 가장 긴 수의 나열은 1 2 3 4 5 2 1 로 개수는 7이다.

테스트케이스 개수 T = 5

테스트케이스 입력

74 67 78 100

51 37 70 79 54 93 24 43

42 61 64 34 89 83 90 78 37 42 13 86 40

32 89 78 51 55 53 86 93 17 18 51 84 20 62 38 85 98 48 13 40

84 23 79 47 13 41 32 31 46 34 57 46 47 37 89 63 100 18 96 3 37 85 6 34 91 6 76 81 72 94

N개의 전구 상태가 0과 1로 주어진다.

1회의 전구 on/off행동을 i번째, i-1번째, i+1번째 전구가 있다면 함께 상태가 반전된다.

즉, 인접한 전구가 함께 on/off가 될 때,

모든 전구의 상태를 0으로 만들 수 있는 최소 횟수를 구하여라.

단, 불가능한 경우는 없다.

예시) 0 01 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

예시 답)

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 (입력)

0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

테스트케이스 T = 5

테스트케이스 입력

0 0 0 1 0 0

0 0 1 1 0 0 1 0 0

1 0 1 1 0 0 0 0 0 1 0 0 0

0 10 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1

0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0

일차원 직선 상에 여러 사람의 집이 있고, 집의 위치는 정수로 표현된다.

이 사람들이 회의를 위해 한 위치(그 곳에 집이 없어도 된다)에 모이고자 할 때,

모든 사람의 이동거리 합의 최소를 구하여라.

예시)1 6

예시 답) 5

테스트케이스 개수 T = 5

테스트케이스

1 10

10 7 6

17 17 10 11

73 17 68 84 70 96 36 19

180 487 577 508 796 3 441 50 153 48