Problem 3 In this problem, consider a treap with n nodes. The key values of these nodes are 1,2,,n. Suppose that instead of random priorities, the node with key i has either priority i or priority n+i with equal probability, for every i=1,2,,n. 1. (10\%) What is the expected depth of the node with key n ? Prove your answer formally. 2. (10\%) What is the expected depth of the node with key 1? Prove your answer formally. (Expected depth of a node is the distance from the root to this node.)