#!/usr/bin/env python3 # -*- coding: utf-8 -*- import array UNDETERMINED = -1 # based on http://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/ class Knapsack(object): def __init__(self, number, weights): # Number of the weights. self.number = number # Weights of the weights. self.weights = weights # Array for memoization. self.memo = [array.array("i", [UNDETERMINED] * (sum(weights) + 1)) for x in range(number + 1)] def rec_memo(self, i, j): m = self.memo[i][j] if m != UNDETERMINED: return m elif i >= self.number: # if no weight is left result = 0 elif j < self.weights[i]: # if the weight i cannot be on the pan result = self.rec_memo(i + 1, j) else: # the value of the weight: the weight of the weight result = max(self.rec_memo(i + 1, j), self.rec_memo(i + 1, j - self.weights[i]) + self.weights[i]) self.memo[i][j] = result return result def solve(self, weight_limit, start_number=0): return self.rec_memo(start_number, weight_limit) def main(): n = int(input()) ws = array.array("i", (int(w) for w in input().split())) (d, m) = divmod(sum(ws), 2) if m == 1: print("impossible") else: k = Knapsack(n, ws) if k.solve(d) == d: print("possible") else: print("impossible") if __name__ == "__main__": main()