You are given n distinct integers. Starting from an empty binary search tree, insert them in the order given, using the standard BST rule: to insert a key x, walk down from the root, going left if x is smaller than the current node and right if x is larger, until an empty spot is reached, where a new node is created. No rebalancing is performed.
You are then given an integer target. Count the number of unordered pairs of distinct nodes (u, v) (u ≠ v) such that u's value plus v's value equals target. Each unordered pair should be counted once.
Input format
Line 1: an integer n.
Line 2: n space-separated distinct integers — the keys, in insertion order.
Line 3: an integer target.
Output format
A single integer: the number of unordered pairs of distinct node values summing to target.
Constraints
- 1 ≤ n ≤ 40
- -200 ≤ each key ≤ 200, all keys distinct
- -400 ≤ target ≤ 400