Solve in C++ in O(n) complexity Two players take turns alternatively in placing signs (+ or -) before them, and then they all are added. The sign can be placed before any element of the array that has...

Extracted text: Solve in C++ in O(n) complexity Two players take turns alternatively in placing signs (+ or -) before them, and then they all are added. The sign can be placed before any element of the array that has not been assigned a sign yet. All elements must be assigned a sign. Player 1 wins if the resulting sum is even, else player 2 wins. Find out who shall win if they both play optimally. (First line is size of array and second line have the elements of array) Input: 2 12 Output: 2nd Player Wins