Input
3
1 2 3
1 2
2 3
Output
333333338
Input
5
5 4 3 1 2
3 5
1 2
4 3
2 5
Output
8