====== 나무 심기 ======

===== 풀이 =====
  * x번째 나무를 심는 비용은. i=0...x-1에 대해서 sum(|p[x] - p[i]|) 이다. x번째 나무보다 왼쪽에 있는 나무들만 따로 모아서 p_l이라 하면 이것들의 비용은 p[x]*len(p_l) - sum(p_l) 이고, 오른쪽에 있는 나무들에 대한 비용은 sum(p_r) - p[x]*len(p_r)이다. 둘을 합하면 p[x]*len(p_l) - sum(p_l) + sum(p_r) - p[x]*len(p_r) 이고, 바꿔쓰면 sum(p)-2*sum(p_l) + p[x]-(i-2*len(p_l)) 이 된다.
  * 이제 sum(p_l)과 len(p_l)을 빠르게 계산할수 있으면 해결된다. 좌표를 인덱스로 해서 count[pos] 와 dist[pos]를 저장하고 있으면 sum(dist[0:p[x])와 sum(count[0:p[x]) 의 [[ps:구간 쿼리#구간합 쿼리]]로 계산할수 있고, 이것은 펜윅트리를 이용해서 구현가능하다.
  * 나무 하나의 비용을 계산할때마다 O(1)번의 쿼리와 업데이트를 해주면 되므로, 총 시간복잡도는 O(n*logP)이다. (P는 좌표의 범위)
  
===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1280. 나무 심기".

- Problem link: https://www.acmicpc.net/problem/1280
- Solution link: http://www.teferi.net/ps/problems/boj/1280

Tags: [Fenwick tree]
"""

import sys
from teflib import fenwicktree

MOD = 1_000_000_007


def main():
    N = int(sys.stdin.readline())
    X = [int(sys.stdin.readline()) for _ in range(N)]

    count_fenwick_tree = fenwicktree.FenwickTree(max(X) + 1)
    dist_fenwick_tree = fenwicktree.FenwickTree(max(X) + 1)
    dist_sum = 0
    answer = 1
    for i, x_i in enumerate(X):
        if i > 0:
            dist_sum_left = dist_fenwick_tree.query(0, x_i)
            count_left = count_fenwick_tree.query(0, x_i)
            answer *= dist_sum - dist_sum_left * 2 - x_i * (i - count_left * 2)
            answer %= MOD
        count_fenwick_tree.update(x_i, 1)
        dist_fenwick_tree.update(x_i, x_i)
        dist_sum += x_i
        
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}